Submission #20074

#	Time	Username	Problem	Language	Result	Execution time	Memory
20074		gs12117	비트 (kriii4_Q)	C++98	100 / 100	1172 ms	1192 KiB

Q

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

• Subtask 1: 9 / 9
• Subtask 2: 91 / 91