P8432 「WHOI-2」ぽかぽかの星

题目背景

你在雪洞里喝着热可可数星星。但这次，星星换成了数列，不过聪明的你一定能数清楚数列的吧。

题目描述

有多少个长度为 $n$ 的正整数数列 $a_i$ 满足：

• $0<a_1\le a_2\le a_3\cdots \le a_n\le k$。
• $\forall i\ne j,a_i+a_j\ne k+1$。

答案对 $10^9+7$ 取模。

输入格式

本题多测

第一行一个正整数表示 $T$。

接下来 $T$ 行，每行两个正整数表示 $n,k$。

输出格式

$T$ 行，每行一个正整数表示答案。

输入输出样例 #1

输入 #1

3
2 2
1145 1419
19198 12321

输出 #1

2
66937457
949924930

说明/提示

本题采用捆绑测试

• $\text{subtask1(20pts)}:T=5,1\le n,k\le 5$。
• $\text{subtask2(80pts)}:$ 无特殊限制。

对于 $100\%$ 的数据，$T\le 100,1\le n,k\le 5\times 10^6,1\le \sum n,\sum k\le 6\times 10^7$。

C++实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
const long long p=1e9+7;
int jc[5000001],jcp[5000001],p2[5000001];
inline long long poww(long long a,long long b){
    long long ss=1;
    while(b)    {
        if(b&1)
            ss=ss*a%p;
        a=a*a%p;
        b>>=1;  
    }
    return ss;
}
signed main(){
	ios::sync_with_stdio(false);
	jc[0]=1,p2[0]=1,jcp[0]=1;
	for(int i=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;
	int t;
	cin>>t;
	while(t--)	{
		int n,k,s=0;
		cin>>n>>k;
		if(n==1)		{
			cout<<k<<"\n";
			continue;
		}
		int kk=k/2;
		int c=min(n,kk);
		for(int i=1;i<=c;i++)		{
			int a=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(int i=1;i<=c;i++)		{
			int a=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";		
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容