Submit Info #19525

Problem Lang User Status Time Memory
Partition Function cpp Naimss AC 2124 ms 9.21 MiB

ケース詳細
Name Status Time Memory
0_00 AC 3 ms 0.67 MiB
100000_00 AC 165 ms 2.30 MiB
10000_00 AC 9 ms 0.84 MiB
1000_00 AC 1 ms 0.66 MiB
100_00 AC 3 ms 0.67 MiB
1_00 AC 2 ms 0.67 MiB
200000_00 AC 498 ms 4.06 MiB
300000_00 AC 940 ms 5.80 MiB
400000_00 AC 1474 ms 7.42 MiB
500000_00 AC 2124 ms 9.21 MiB
example_00 AC 1 ms 0.67 MiB

#include <bits/stdc++.h> #define ld long double #define endl "\n" #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb(x) push_back(x) #define mp(a,b) make_pair(a,b) #define ms(v,x) memset(v,x,sizeof(v)) #define all(v) v.begin(),v.end() #define ff first #define ss second #define rep(i, a, b) for(int i = a; i < (b); ++i) #define per(i, a, b) for(int i = b-1; i>=a ; i--) #define trav(a, x) for(auto& a : x) #define allin(a , x) for(auto a : x) #define td(v) v.begin(),v.end() #define sz(v) (int)v.size() //#define int long long using namespace std; typedef vector<int> vi; #define y1 abacaba #define left sefude #define db(x) cerr << #x <<" == "<<x << endl; #define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl; #define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl; typedef long long ll; typedef pair<ll,ll> pll; typedef pair<int,int> pii; inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; } ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));} ll exp(ll a,ll b,ll m){ if(b==0LL) return 1LL; if(b==1LL) return mod(a,m); ll k = mod(exp(a,b/2,m),m); if(b&1LL){ return mod(a*mod(k*k,m),m); } else return mod(k*k,m); } const int N = 5e5 + 100; const int M = 998244353; ll p[N]; int32_t main(){ fastio; p[0] = 1; int n; cin >> n; for(int i=1;i<=n;i++){ p[i] = 0; for(int it=-1;it<=1;it+=2){ for(int K=1;;K ++){ int k = K*it; if(k*(3*k-1)/2 > i)break; ll cur = p[i - (k*(3*k-1)/2)]; if((k-1)%2)cur = -cur; p[i] = p[i] + cur; if(p[i]<0)p[i]+=M; if(p[i]>=M)p[i]-=M; } } } for(int i=0;i<=n;i++){ cout << p[i]<<" \n"[i==n]; } // math -> gcd it all // Did u check N=1? Did you switch N,M? }