Submit Info #1234

Problem Lang User Status Time Memory
Partition Function cpp chocorusk AC 2831 ms 14.91 MiB

ケース詳細
Name Status Time Memory
0_00 AC 2 ms 0.72 MiB
100000_00 AC 550 ms 3.55 MiB
10000_00 AC 57 ms 0.91 MiB
1000_00 AC 6 ms 0.71 MiB
100_00 AC 2 ms 0.68 MiB
1_00 AC 0 ms 0.67 MiB
200000_00 AC 1111 ms 6.37 MiB
300000_00 AC 1670 ms 9.18 MiB
400000_00 AC 2243 ms 12.05 MiB
500000_00 AC 2831 ms 14.91 MiB
example_00 AC 1 ms 0.72 MiB

#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; const int MOD=998244353; const int b=710; int dp[2][500050]; int s[2][500050]; int t[500050]; int main() { int n; scanf("%d", &n); dp[0][0]=1; t[0]=1; for(int i=1; i<b; i++){ dp[i&1][0]=0; for(int j=1; j<=n; j++){ dp[i&1][j]=dp[(i&1)^1][j-1]; if(j>=i){ dp[i&1][j]+=dp[i&1][j-i]; if(dp[i&1][j]>=MOD) dp[i&1][j]-=MOD; } t[j]+=dp[i&1][j]; if(t[j]>=MOD) t[j]-=MOD; } } for(int i=b-1; i>=0; i--){ for(int j=0; j<=n; j++){ s[i&1][j]=s[(i&1)^1][j]; if(j-1-i*b>=0){ s[i&1][j]+=dp[(b-1)&1][j-1-i*b]; if(s[i&1][j]>=MOD) s[i&1][j]-=MOD; } if(j-1-i>=0){ s[i&1][j]+=s[i&1][j-1-i]; if(s[i&1][j]>=MOD) s[i&1][j]-=MOD; } } } for(int i=0; i<=n; i++){ t[i]+=s[0][i]; if(t[i]>=MOD) t[i]-=MOD; } for(int i=0; i<=n; i++) printf("%d ", t[i]); printf("\n"); return 0; }