Submit Info #48145

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 1253 ms 7.30 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.68 MiB
100000_00 AC 111 ms 2.02 MiB
10000_00 AC 5 ms 0.74 MiB
1000_00 AC 1 ms 0.70 MiB
100_00 AC 1 ms 0.68 MiB
1_00 AC 1 ms 0.66 MiB
200000_00 AC 309 ms 3.29 MiB
300000_00 AC 562 ms 4.59 MiB
400000_00 AC 882 ms 5.93 MiB
500000_00 AC 1253 ms 7.30 MiB
example_00 AC 2 ms 0.68 MiB

#include<bits/stdc++.h> using namespace std; #define MOD 998244353 int N; int P[500001]; int main() { scanf("%d", &N); P[0] = 1; for(int i=1; i<=N; i++) { for(int j=1; j*(3*j-1)/2<=i; j++) P[i] += (j%2?1:-1)*P[i-j*(3*j-1)/2], P[i] %= MOD; for(int j=1; j*(3*j+1)/2<=i; j++) P[i] += (j%2?1:-1)*P[i-j*(3*j+1)/2], P[i] %= MOD; P[i] += MOD, P[i] %= MOD; } for(int i=0; i<=N; i++) printf("%d ", P[i]); return 0; }