結果

問題 No.1667 Forest
ユーザー publflpublfl
提出日時 2021-09-03 22:29:41
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,505 bytes
コンパイル時間 471 ms
コンパイル使用メモリ 33,280 KB
実行使用メモリ 21,888 KB
最終ジャッジ日時 2024-05-09 05:11:26
合計ジャッジ時間 9,243 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
権限があれば一括ダウンロードができます

ソースコード

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]) return check[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;
		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);
	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