Submit Info #249

Problem Lang User Status Time Memory
Partition Function cpp hos AC 353 ms 9.05 MiB

ケース詳細
Name Status Time Memory
0_00 AC 0 ms 0.67 MiB
100000_00 AC 29 ms 2.30 MiB
10000_00 AC 4 ms 0.71 MiB
1000_00 AC 1 ms 0.68 MiB
100_00 AC 4 ms 0.67 MiB
1_00 AC 1 ms 0.68 MiB
200000_00 AC 86 ms 3.92 MiB
300000_00 AC 160 ms 5.67 MiB
400000_00 AC 249 ms 7.42 MiB
500000_00 AC 353 ms 9.05 MiB
example_00 AC 1 ms 0.61 MiB

#pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx") #include <stdio.h> using Int = long long; constexpr Int MO = 998244353; constexpr int LIM = 500010; /* 1 / (\sum_i (X^(6i^2+i) - X^(6i^2+5i+1) - X^(6i^2+7i+2) + X^(6i^2+11i+5))) */ Int partition[LIM]; void preparePartition(int lim) { partition[0] = 1; for (int n = 1; n < lim; ++n) { Int sum = 0; for (int k = 0, l = 1, m = n - 1; ; ) { sum += partition[m]; if ((m -= (k += 1)) < 0) break; sum += partition[m]; if ((m -= (l += 2)) < 0) break; sum -= partition[m]; if ((m -= (k += 1)) < 0) break; sum -= partition[m]; if ((m -= (l += 2)) < 0) break; } if ((sum %= MO) < 0) sum += MO; partition[n] = sum; } } int main() { int N; scanf("%d", &N); preparePartition(N + 1); for (int n = 0; n <= N; ++n) { if (n > 0) printf(" "); printf("%lld", partition[n]); } puts(""); return 0; }