結果

問題 No.1667 Forest
ユーザー publflpublfl
提出日時 2021-09-03 22:26:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,332 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 33,792 KB
実行使用メモリ 21,776 KB
最終ジャッジ日時 2024-12-15 14:35:17
合計ジャッジ時間 53,118 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

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

ソースコード

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];
long long int comb(int a, int b)
{
	long long int ans = fact[a];
	ans *= inv(fact[b]), ans %= MOD;
	ans *= inv(fact[a-b]), ans %= MOD;
	return 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;
	for(int i=1;;i++)
	{
		if(s-i*limit<0) break;
		val *= power(limit,limit-2), 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 *= inv(fact[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=0;i<=a-1;i++) printf("%lld\n",func(a,i,1));
}
0