| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20074 |
2016-02-25T09:32:32 Z |
gs12117 |
비트 (kriii4_Q) |
C++ |
|
1172 ms |
1192 KB |
#include<stdio.h>
int n,m;
int mod=1000000007;
long long int fct[110];
long long int ift[110];
long long int mtrx[110][110];
long long int r[110];
int mpow(int x,int y){
if(y==0)return 1;
long long int r=mpow(x,y/2);
r*=r;
r%=mod;
if(y%2==1){
r*=x;
r%=mod;
}
return r;
}
long long int minv(int x){
return mpow(x,mod-2);
}
struct node{
long long int x[110];
node operator+(node z){
node res;
int i,j,k;
for(i=0;i<=n;i++){
res.x[i]=0;
}
for(i=0;i<=n;i++){
if(x[i]==0)continue;
for(j=0;j<=n;j++){
for(k=0;k<=i&&k<=j;k++){
if(i+j-k-k>n)continue;
res.x[i+j-k-k]+=x[i]*z.x[j]%mod*fct[i]%mod*fct[j]%mod*fct[n-i]%mod*fct[n-j]%mod*ift[k]%mod*ift[i-k]%mod*ift[j-k]%mod*ift[n+k-i-j]%mod*ift[n]%mod;
res.x[i+j-k-k]%=mod;
}
}
}
return res;
}
};
node p;
node find(int x){
if(x==1)return p;
node res=find(x/2);
res=res+res;
if(x%2==1)res=res+p;
return res;
}
int main(){
int i,j,k;
long long int t;
scanf("%d%d",&n,&m);
fct[0]=1;
for(i=0;i<=n;i++){
ift[i]=minv(fct[i]);
fct[i+1]=fct[i]*(i+1);
fct[i+1]%=mod;
}
for(i=0;i<=n;i++)p.x[i]=0;
p.x[1]=1;
node res=find(m);
node s;
long long int ans;
for(i=1;i<=n;i++){
for(j=0;j<=n;j++)s.x[j]=0;
s.x[i]=1;
s=s+res;
for(j=0;j<=n;j++)mtrx[i][j]=(mod-s.x[j])%mod;
mtrx[i][i]++;
r[i]=1;
}
r[0]=0;
mtrx[0][0]=1;
for(i=0;i<=n;i++){
for(j=i;j<=n;j++){
if(mtrx[j]!=0)break;
}
for(k=0;k<n;k++){
t=mtrx[i][k];
mtrx[i][k]=mtrx[j][k];
mtrx[j][k]=t;
}
t=r[i];
r[i]=r[j];
r[j]=t;
t=minv(mtrx[i][i]);
r[i]*=t;
r[i]%=mod;
for(j=i;j<=n;j++){
mtrx[i][j]*=t;
mtrx[i][j]%=mod;
}
for(j=i+1;j<=n;j++){
t=(mod-mtrx[j][i])%mod;
r[j]+=r[i]*t;
r[j]%=mod;
for(k=i;k<=n;k++){
mtrx[j][k]+=mtrx[i][k]*t;
mtrx[j][k]%=mod;
}
}
}
for(i=n;i>=0;i--){
for(j=0;j<i;j++){
r[j]+=r[i]*(mod-mtrx[j][i]);
r[j]%=mod;
}
}
for(i=1;i<=n;i++){
printf("%lld\n",r[i]);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
1180 KB |
Output is correct |
| 2 |
Correct |
37 ms |
1180 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1180 KB |
Output is correct |
| 5 |
Correct |
55 ms |
1180 KB |
Output is correct |
| 6 |
Correct |
1 ms |
1180 KB |
Output is correct |
| 7 |
Correct |
8 ms |
1180 KB |
Output is correct |
| 8 |
Correct |
29 ms |
1180 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 10 |
Correct |
2 ms |
1180 KB |
Output is correct |
| 11 |
Correct |
12 ms |
1180 KB |
Output is correct |
| 12 |
Correct |
37 ms |
1180 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 14 |
Correct |
17 ms |
1180 KB |
Output is correct |
| 15 |
Correct |
54 ms |
1180 KB |
Output is correct |
| 16 |
Correct |
1 ms |
1180 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1180 KB |
Output is correct |
| 18 |
Correct |
23 ms |
1180 KB |
Output is correct |
| 19 |
Correct |
59 ms |
1180 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
1180 KB |
Output is correct |
| 2 |
Correct |
818 ms |
1180 KB |
Output is correct |
| 3 |
Correct |
19 ms |
1180 KB |
Output is correct |
| 4 |
Correct |
140 ms |
1180 KB |
Output is correct |
| 5 |
Correct |
499 ms |
1180 KB |
Output is correct |
| 6 |
Correct |
885 ms |
1180 KB |
Output is correct |
| 7 |
Correct |
46 ms |
1184 KB |
Output is correct |
| 8 |
Correct |
234 ms |
1184 KB |
Output is correct |
| 9 |
Correct |
566 ms |
1180 KB |
Output is correct |
| 10 |
Correct |
99 ms |
1188 KB |
Output is correct |
| 11 |
Correct |
362 ms |
1188 KB |
Output is correct |
| 12 |
Correct |
1025 ms |
1188 KB |
Output is correct |
| 13 |
Correct |
20 ms |
1192 KB |
Output is correct |
| 14 |
Correct |
143 ms |
1184 KB |
Output is correct |
| 15 |
Correct |
387 ms |
1180 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1180 KB |
Output is correct |
| 17 |
Correct |
36 ms |
1180 KB |
Output is correct |
| 18 |
Correct |
666 ms |
1180 KB |
Output is correct |
| 19 |
Correct |
7 ms |
1180 KB |
Output is correct |
| 20 |
Correct |
1172 ms |
1184 KB |
Output is correct |
