超能粒子炮·改"/>
【BZOJ4591/SHOI2015】超能粒子炮·改
4591: [Shoi2015]超能粒子炮·改
Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1144 Solved: 446
Description
曾经发明了脑洞治疗仪&超能粒子炮的发明家SHTSC又公开了他的新发明:超能粒子炮·改--一种可以发射威力更加
强大的粒子流的神秘装置。超能粒子炮·改相比超能粒子炮,在威力上有了本质的提升。它有三个参数n,k。它会
向编号为0到k的位置发射威力为C(n,k) mod 2333的粒子流。现在SHTSC给出了他的超能粒子炮·改的参数,让你求
其发射的粒子流的威力之和模2333。
Input
第一行一个整数t。表示数据组数。
之后t行,每行二个整数n,k。含义如题面描述。
k<=n<=10^18,t<=10^5
Output
t行每行一个整数,表示其粒子流的威力之和模2333的值。
Sample Input
1
5 5
Sample Output
32
解析:
深刻感受到自己数学是有多弱。。。
由Lucas定理C(n,k)=C(n/2333,k/2333)*C(n%2333,k%2333)%2333
则ans=ΣC(n,i),(i<=k)
=C(n/2333,0)*C(n%2333,0)+C(n/2333,0)*C(n%2333,1)+...+C(n/2333,0)*C(n%2333,2332)
+C(n/2333,1)*C(n%2333,0)+C(n/2333,1)*C(n%2333,1)+...+C(n/2333,1)*C(n%2333,2332)
+.....
+C(n/2333,k/2333)*C(n%2333,0)+....+C(n/2333,k/2333)*C(n%2333,k%2333)
=∑C(n/2333,j)*sum[n%2333][2332]+C(n/2333,k/2333)*sum[n%2333][k%2333],(0<=j<k/2333)
cal(n,k)=cal(n/2333,k/2333-1)*sum[n%2333][2332]+Lucas(n/2333,k/2333)*sum[n%2333][k%2333]
代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;const int Max=2335;
const int mod=2333;
int n,k,t,ans;
int sum[Max][Max],c[Max][Max];inline int get_int()
{int x=0,f=1;char c;for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());if(c=='-') {f=-1;c=getchar();}for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';return x*f;
}inline void pre()
{c[0][0]=1;sum[0][0]=1; for(int i=1;i<mod;i++) c[i][0] = c[i][i] = 1;for(int i=1;i<mod;i++) for(int j=1;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;for(int i=0;i<mod;i++){sum[i][0]=1;for(int j=1;j<mod;j++) sum[i][j]=(sum[i][j-1]+c[i][j])%mod;}
}inline int Lucas(int n,int m)
{if(!m) return 1;return Lucas(n/mod,m/mod) * c[n%mod][m%mod] % mod;
}inline int solve(int n,int k)
{if(k<0) return 0;return (solve(n/mod,k/mod-1)*sum[n%mod][mod-1]+Lucas(n/mod,k/mod)*sum[n%mod][k%mod])%mod;
}signed main()
{pre();t=get_int();while(t--){n=get_int(),k=get_int();cout<<solve(n,k)<<"\n";}return 0;
}
更多推荐
【BZOJ4591/SHOI2015】超能粒子炮·改
发布评论