Submit Info #67909

Problem Lang User Status Time Memory
Partition Function cpp (anonymous) AC 804 ms 8.89 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.45 MiB
100000_00 AC 79 ms 2.07 MiB
10000_00 AC 4 ms 0.57 MiB
1000_00 AC 1 ms 0.45 MiB
100_00 AC 1 ms 0.45 MiB
1_00 AC 1 ms 0.45 MiB
200000_00 AC 212 ms 3.80 MiB
300000_00 AC 385 ms 5.48 MiB
400000_00 AC 584 ms 7.20 MiB
500000_00 AC 804 ms 8.89 MiB
example_00 AC 1 ms 0.45 MiB

#include<bits/stdc++.h> #define maxn 567890 int ans[maxn], tmp[maxn]; using namespace std; const int mod = 998244353; void modadd(int &x, int y) { x += y; x %= mod; } int main() { int n; cin >> n; int b = sqrt(n); ans[0] = tmp[0] = 1; for (int i = 1; i <= b; i++) { for (int rep = 0; rep < 2; rep++) { for (int j = i; j <= n - i * i; j++) { modadd(tmp[j], tmp[j-i]); } } for (int j = i * i; j <= n; j++) { modadd(ans[j], tmp[j - i * i]); } } for (int i = 0; i <= n; ++i) cout << ans[i] << " \n"[i == n]; }