【BZOJ4591/SHOI2015】超能粒子炮·改

超能粒子炮·改"/>

【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;
}