Submit Info #48144

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 1251 ms 7.21 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1223 ms 2.55 MiB
100000_00 AC 1230 ms 3.55 MiB
10000_00 AC 1222 ms 2.57 MiB
1000_00 AC 1225 ms 2.55 MiB
100_00 AC 1223 ms 2.60 MiB
1_00 AC 1223 ms 2.58 MiB
200000_00 AC 1234 ms 4.49 MiB
300000_00 AC 1241 ms 5.34 MiB
400000_00 AC 1251 ms 6.34 MiB
500000_00 AC 1251 ms 7.21 MiB
example_00 AC 1223 ms 2.58 MiB

#include<bits/stdc++.h> using namespace std; #define MOD 998244353 int N; int P[500001]; int main() { P[0] = 1; for(int i=1; i<=500000; 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; } scanf("%d", &N); for(int i=0; i<=N; i++) printf("%d ", P[i]); return 0; }