結果
| 問題 | No.1667 Forest |
| ユーザー |
 publfl
|
| 提出日時 | 2021-09-03 22:37:13 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,665 bytes |
| コンパイル時間 | 435 ms |
| コンパイル使用メモリ | 33,792 KB |
| 実行使用メモリ | 235,008 KB |
| 最終ジャッジ日時 | 2024-05-09 05:29:19 |
| 合計ジャッジ時間 | 8,815 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | -- | - |
ソースコード
#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));
}