Submit Info #247

Problem Lang User Status Time Memory
Partition Function cpp hos AC 326 ms 9.03 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.71 MiB
100000_00 AC 35 ms 2.19 MiB
10000_00 AC 4 ms 0.67 MiB
1000_00 AC 1 ms 0.68 MiB
100_00 AC 0 ms 0.67 MiB
1_00 AC 0 ms 0.68 MiB
200000_00 AC 81 ms 3.91 MiB
300000_00 AC 152 ms 5.61 MiB
400000_00 AC 234 ms 7.30 MiB
500000_00 AC 326 ms 9.03 MiB
example_00 AC 1 ms 0.72 MiB

#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, m = n; ; k += 2) { sum -= partition[m]; if ((m -= 2 * k + 1) < 0) break; sum += partition[m]; if ((m -= k + 1) < 0) break; sum += partition[m]; if ((m -= 2 * k + 3) < 0) break; sum -= partition[m]; if ((m -= k + 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; }