Submit Info #48147

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 1700 ms 14.97 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1672 ms 10.18 MiB
100000_00 AC 1675 ms 11.18 MiB
10000_00 AC 1673 ms 10.30 MiB
1000_00 AC 1671 ms 10.18 MiB
100_00 AC 1672 ms 10.17 MiB
1_00 AC 1668 ms 10.18 MiB
200000_00 AC 1683 ms 12.05 MiB
300000_00 AC 1687 ms 13.05 MiB
400000_00 AC 1695 ms 13.93 MiB
500000_00 AC 1700 ms 14.97 MiB
example_00 AC 1670 ms 10.18 MiB

#include<bits/stdc++.h> using namespace std; #define MOD 998244353 const int N = 500000, SQRT_N = 707; int P[2][500001], D[2][500001], res[500001]; int main() { res[0] = 1; // P[k][n] 계산 for(int k=1; k<SQRT_N; k++) { P[0][0] = (k == 1); for(int n=1; n<=N; n++) { int &ret = P[k&1][n]; ret = P[k-1&1][n-1]; if (n-k >= 0) ret += P[k&1][n-k], ret %= MOD; res[n] += ret, res[n] %= MOD; } } // D[a][b] 계산 for(int a=SQRT_N; a>=0; a--) for(int b=SQRT_N; b<=N; b++) { int &ret = D[a&1][b]; ret = 0; if (b-a-1 >= 0) ret += D[a&1][b-a-1]; ret += D[a+1&1][b-SQRT_N], ret %= MOD; ret += P[SQRT_N-1&1][b-1], ret %= MOD; if (a == 0) res[b] += ret, res[b] %= MOD; } int n; scanf("%d", &n); for(int i=0; i<=n; i++) printf("%d ", res[i]); return 0; }