結果

問題 No.1667 Forest
コンテスト
ユーザー publfl
提出日時 2021-09-03 22:37:13
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,665 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 33,664 KB
実行使用メモリ 234,880 KB
最終ジャッジ日時 2024-12-15 15:22:20
合計ジャッジ時間 29,704 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

long long int MOD;
long long int power(long long int a, long long int b)
{
	if(b<0) return 1;
	long long int ans = 1;
	long long int k = a;
	while(b)
	{
		if(b%2==1) ans*=k, ans%=MOD;
		k*=k, k%=MOD;
		b/=2;
	}
	return ans;
}
long long int inv(long long int k)
{
	return power(k,MOD-2);
}
long long int fact[1010],invFact[1010];
long long int check2[310][310];
long long int comb(int a, int b)
{
	if(check2[a][b]) return check2[a][b];
	long long int ans = fact[a];
	ans *= inv(fact[b]), ans %= MOD;
	ans *= inv(fact[a-b]), ans %= MOD;
	return check2[a][b] = ans;
}

long long int check[310][310][310];
long long int func(int s, int t, int limit)
{
	if(s<0) return 0;
	if(t<0) return 0;
	if(s==0)
	{
		if(t==0) return 1;
		else return 0;
	}
	if(limit>s) return 0;
	if(check[s][t][limit]!=-1) return check[s][t][limit];
	//printf("%d %d %d??\n",s,t,limit);
	
	long long int s1 = func(s,t,limit+1);
	long long int s2 = 0;
	long long int val = 1;
	long long int m = power(limit,limit-2);
	for(int i=1;;i++)
	{
		if(s-i*limit<0) break;
		if(t-i*(limit-1)<0) break;
		val *= m, val %= MOD;
		val *= comb(s-(i-1)*limit,limit), val %= MOD;
		long long int val2 = func(s-i*limit,t-i*(limit-1),limit+1);
		val2 *= val, val2 %= MOD;
		val2 *= invFact[i], val2 %= MOD;
		s2 += val2, s2 %= MOD;
	}
	return check[s][t][limit] = (s1+s2)%MOD;
}

int main()
{
	int a;
	scanf("%d%lld",&a,&MOD);
	for(int i=0;i<=a;i++) for(int j=0;j<=a;j++) for(int k=0;k<=a;k++) check[i][j][k] = -1;
	
	fact[0] = 1;
	for(int i=1;i<=1000;i++) fact[i] = (i*fact[i-1])%MOD;
	for(int i=1;i<=1000;i++) invFact[i] = inv(fact[i]);
	for(int i=0;i<=a-1;i++) printf("%lld\n",func(a,i,1));
}
0