P8432 「WHOI-2」ぽかぽかの星
题目背景
你在雪洞里喝着热可可数星星。但这次，星星换成了数列，不过聪明的你一定能数清楚数列的吧。
题目描述
有多少个长度为nnn的正整数数列aia_iai满足：
- 0<a1≤a2≤a3⋯≤an≤k0<a_1\leq a_2\leq a_3\dots \leq a_n\leq k0<a1≤a2≤a3⋯≤an≤k。
- ∀i≠j,ai+aj≠k+1\forall i\not = j,a_i+a_j\not = k+1∀i=j,ai+aj=k+1。
答案对109+710^9+7109+7取模。
输入格式
本题多测
第一行一个正整数表示TTT。
接下来TTT行，每行两个正整数表示n,kn,kn,k。
输出格式
TTT行，每行一个正整数表示答案。
输入输出样例 #1
输入 #1
3 2 2 1145 1419 19198 12321输出 #1
2 66937457 949924930说明/提示
本题采用捆绑测试
- subtask1(20pts):T=5,1≤n,k≤5\text{subtask1(20pts)}:T=5,1\leq n,k\le5subtask1(20pts):T=5,1≤n,k≤5。
- subtask2(80pts):\text{subtask2(80pts)}:subtask2(80pts):无特殊限制。
对于100%100\%100%的数据，T≤100,1≤n,k≤5×106,1≤∑n,∑k≤6×107T\leq100,1\le n,k\le 5\times 10^6,1\leq \sum n, \sum k\le6\times 10^7T≤100,1≤n,k≤5×106,1≤∑n,∑k≤6×107。
C++实现
#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstlonglongp=1e9+7;intjc[5000001],jcp[5000001],p2[5000001];inlinelonglongpoww(longlonga,longlongb){longlongss=1;while(b){if(b&1)ss=ss*a%p;a=a*a%p;b>>=1;}returnss;}signedmain(){ios::sync_with_stdio(false);jc[0]=1,p2[0]=1,jcp[0]=1;for(inti=1;i<=5000000;i++)jc[i]=jc[i-1]*i%p,jcp[i]=poww(jc[i],p-2),p2[i]=p2[i-1]*2%p;intt;cin>>t;while(t--){intn,k,s=0;cin>>n>>k;if(n==1){cout<<k<<"\n";continue;}intkk=k/2;intc=min(n,kk);for(inti=1;i<=c;i++){inta=jcp[i]*jcp[kk-i]%p*jc[kk]%p,b=jc[n-1]*jcp[n-i]%p*jcp[i-1]%p;if(i-1==0)b=1;s=(s+a*b%p*p2[i]%p)%p;}if(k%2==0){cout<<s<<"\n";continue;}c=min(n-1,kk);for(inti=1;i<=c;i++){inta=jc[kk]*jcp[kk-i]%p*jcp[i]%p,b=jc[n-2]*jcp[n-1-i]%p*jcp[i-1]%p;if(i-1==0)b=1;s=(s+a*b%p*p2[i]%p)%p;}cout<<s<<"\n";}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
