Submit Info #49942

Problem Lang User Status Time Memory
Partition Function cpp Emaneru AC 1394 ms 7.34 MiB

ケース詳細
Name Status Time Memory
0_00 AC 1 ms 0.70 MiB
100000_00 AC 126 ms 1.96 MiB
10000_00 AC 5 ms 0.84 MiB
1000_00 AC 1 ms 0.71 MiB
100_00 AC 1 ms 0.61 MiB
1_00 AC 1 ms 0.71 MiB
200000_00 AC 350 ms 3.33 MiB
300000_00 AC 642 ms 4.71 MiB
400000_00 AC 992 ms 5.96 MiB
500000_00 AC 1394 ms 7.34 MiB
example_00 AC 1 ms 0.61 MiB

#include <bits/stdc++.h> using namespace std; #define _ ios_base::sync_with_stdio(0);cin.tie(0); #define endl '\n' #define f first #define s second #define pb push_back typedef long long ll; typedef pair<int, int> ii; const int INF = 0x3f3f3f3f; // pentagon numbers = n(3n - 1)/2 const int MAX = 5e5+10; const int MOD = 998244353; int part[MAX]; void partition(int n){ vector<int> p; for(int i=1; i*i<=n; i++) p.pb(i*(3*i - 1)/2), p.pb(i*(3*i + 1)/2); part[0] = 1; for(int i=1; i<=n; i++) for(int j=0; p[j]<=i; j++){ if(j%4 < 2) part[i] = (part[i] + part[i-p[j]])%MOD; else part[i] = (part[i] - part[i-p[j]] + MOD)%MOD; } } int main(){ _ int n; cin >> n; partition(n); for(int i=0; i<=n;i++){ cout << part[i] << " "; } cout << endl; exit(0); }