C++(g++ 7.5.0) 解法, 执行用时: 264ms, 内存消耗: 1752K, 提交时间: 2022-10-12 13:44:22

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll P = 998244353;
const int maxn = 1e5 + 5;

int dp[maxn];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

    int n; cin >> n;
    dp[0] = 1;
    for(int i = 1 ; i <= n ; i ++){
    	for(int j = 1, flag = 1; ; j ++, flag = -flag){
    		int a = i-(3*j*j-j)/2;
    		if(a>=0){
    			dp[i] += flag * dp[a];
    			if(dp[i]<0) dp[i] += P;
    			if(dp[i]>=P) dp[i] -= P;
    		}
    		else break;
    	}
    	for(int j = 1, flag = 1; ; j ++, flag = -flag){
    		int a = i-(3*j*j+j)/2;
    		if(a>=0){
    			dp[i] += flag * dp[a];
    			if(dp[i]<0) dp[i] += P;
    			if(dp[i]>=P) dp[i] -= P;
    		}
    		else break;
    	}
    }

    for(int i = 1 ; i <= n ; i ++) cout << dp[i] << '\n';

	return 0;
}

C++ 解法, 执行用时: 159ms, 内存消耗: 2048K, 提交时间: 2022-03-23 12:56:50

#include<bits/stdc++.h>
using namespace std;
#define int long long

#ifdef _KHORAY
#include<debughr.h>
#else
#define out(args...) 42
#endif
const int mod = 998244353;

void solve(int testcase) {
	int n;
	cin >> n;
	vector<int> p(n + 1);
	p[0] = 1;
	p[1] = 1;
	cout << "1\n";
	for(int i = 2; i <= n; i++) {
		for(int k = 1; (3 * k + 1) * k / 2 <= i; k++) {
			int now = (k & 1) ? 1 : -1;
			p[i] = (p[i] + now * p[i - (3 * k + 1) * k / 2] + mod) % mod;
		}
		for(int k = 1; (3 * k - 1) * k / 2 <= i; k++) {
			int now = (k & 1) ? 1 : -1;
			p[i] = (p[i] + now * p[i - (3 * k - 1) * k / 2] + mod) % mod;
		}
		cout << p[i] << '\n';
	}

}

signed main() {
	int t = 1;
	for(int i = 1; i <= t; i++) {
		solve(i);
	}
	return 0;
}