昨晚苦恼了一晚，因为即将大三了，必须要准备实习什么的事了。一般都会去公司实习吧，但是看看自己的简历，实在拿不出手，因为大一大二都在搞ACM（虽然真正搞的只有大二一年）,但却没有什么成绩，又不愿意做项目，因为只想一心搞ACM。可到了现在，如果真的没点什么的话，可能就去不了做实习生了。
但是，想想自己，这个暑假几乎没回家，因为要多练习，多做题，终于是把计算几何和数论的题算是完整的做了吧，过程很痛苦，但因为心里面有一个理想，那就是在省赛摘金，改写学校的历史，也并不觉累。假若现在放弃，我实在会后悔死，即便以后，也会痛恨自己的。思索过一晚上，还是下定决心，要把ACM进行到底，无论是出于兴趣或是功利的目的，我实在不愿放弃。至于项目，却也是必须要搞的，因为学校规定，每人至少参与一个项目开发。我知道自己在学校的时间不会多了，所以，必须更加的努力，更加的更加的努力，既要做项目，更要把ACM搞好，多做题，多做题，因为这是我好不容易才得到的机会，我不想就此放弃。我相信，勤奋是会有回报的。
-----------------------------------------------------------------
这道题，假如不知道公式什么的，实在是做不出来。
百度一下，有了两条公式
对于第二条公式，查一下stirling数是怎么计算的，对于第二条，就把那个大的模数分解成小的素数相乘，求出对于每个素数的余，然后运用中国剩余定理写就可以了。
由递推式，可以构造一个b(n),b(n+1),b(n+2)....b(n+p-1)的1*p的矩阵，至于p*p的，你就会构造了。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std; int Mod=95041567;
int m[5]={ 31 , 37 , 41 , 43 , 47};
int at[5]; int data[62][62]; void stirling()
{
int min, i, j,s=60,n=60;
memset(data,0,sizeof(data));
data[0][0] = 1;
for( i = 1; i <= s; ++i ){
if( i < n ) min = i;
else min = n;
for( j = 1; j <= min; ++j ){
data[i][j] = ((int)(((__int64)j*(__int64)data[i-1][j])%(__int64)Mod)+ data[i-1][j-1])% Mod;
}
}
}
int bell[62];
int ans[62];
struct Matrax {
int m[62][62];
};
Matrax per,a; Matrax multi(Matrax a,Matrax b,int M){
Matrax c;
for(int i=0;i<M;i++){
for(int j=0;j<M;j++){
c.m[i][j]=0;
for(int k=0;k<M;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;
}
}
return c;
} Matrax Power(int k,int M){
Matrax ans=per,p=a;
while(k){
if(k&1){
ans=multi(ans,p,M);
}
k>>=1;
p=multi(p,p,M);
}
return ans;
} void initial(int l){
memset(a.m,0,sizeof(a.m));
memset(per.m,0,sizeof(per.m));
a.m[l][0]=1;
for(int i=1;i<=l;i++)
a.m[i][i]=a.m[i-1][i]=1;
for(int i=0;i<62;i++)
per.m[i][i]=1;
} int work(int n,int M){
initial(M-1);
Matrax ps=Power(n/(M-1),M);
/* for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
cout<<ps.m[i][j]<<' ';
cout<<endl;
}*/
for(int i=0;i<M;i++){
ans[i]=0;
for(int k=0;k<M;k++){
ans[i]=(ans[i]+bell[k]*ps.m[k][i])%M;
}
}
return ans[n%(M-1)];
} void exgcd(int a,int b,int &d,int &x,int &y){
if(b==0){
x=1; y=0;
d=a;
return ;
}
else{
exgcd(b,a%b,d,x,y);
int tmp=x;
x=y;
y=tmp-(a/b)*y;
}
} int China(int r){
int Mc=1;
int i,Mi,x,y,d,as=0;
for(i=0;i<r;i++)
Mc*=m[i];
for(i=0;i<r;i++){
Mi=Mc/m[i];
exgcd(Mi,m[i],d,x,y);
as=(as+Mi*x*at[i])%Mc;
}
if(as<0)
as+=Mc;
return as;
} int main(){
int T,n,M;
stirling();
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<5;i++){
M=m[i];
for(int k=0;k<M;k++){
if(k==0){
bell[k]=1;
}
else{
bell[k]=0;
for(int p=1;p<=k;p++){
bell[k]=(bell[k]+data[k][p])%M;
}
}
// cout<<bell[k]<<' '<<k<<endl;
}
at[i]=work(n,M);
// cout<<at[i]<<endl;
// system("pause");
}
int ats=China(5);
printf("%d\n",ats);
}
return 0;
}