LOJ6268拆分数

/*相当于每种物品都有无限个的背包毕竟考场上写exp是个比较危险的行为对数据进行根号分治是个比较好的方法对于小于等于根号的部分暴力背包转移
对于大于根号的 最多只会拿根号个 dp一下就好了*/
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<cmath>
#define ll long long
#define M 100010
#define mmp make_pair
using namespace std;
const int mod = 998244353, g = 3;
void add(int &a, int b) {a += b;a -= a >= mod ? mod : 0;a += a < 0  ? mod : 0;}int poww(int a, int b) {int tmp = a, ans = 1;for(; b; b >>= 1, tmp = 1ll * tmp * tmp % mod) if(b & 1) ans = 1ll * ans * tmp % mod;return ans;
}int read() {int nm = 0, f = 1;char c = getchar();for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';return nm * f;
}
int a[M * 4], b[M * 4], biao, f[350][M], n, pw[M * 4], iw[M * 4];void fft(int *a, int n, int dft) {for(int i = 0, j = 0; i < n; i++) {if(i < j) swap(a[i], a[j]);for(int l = n >> 1; (j ^= l) < l; l >>= 1);}for(int step = 1; step < n; step <<= 1) {int wn = (dft == 1) ? pw[step] : iw[step];for(int i = 0; i < n; i += step << 1) {int wnk = 1;for(int j = i; j < i + step; j++) {int x = a[j], y = 1ll * wnk * a[j + step] % mod;a[j] = (x + y) % mod;a[j + step] = (x - y + mod) % mod;wnk = 1ll * wnk * wn % mod;}}}if(dft == -1) {int inv = poww(n, mod - 2);for(int i = 0; i < n; i++) a[i] = 1ll * a[i] * inv % mod;}
}int main() {n = read();a[0] = 1;biao = sqrt(n) + 1;for(int i = 1; i < biao; i++) {for(int j = i; j <= n; j++) {add(a[j], a[j - i]);}}f[1][biao] = 1;for(int i = 1; i <= biao; i++) {for(int j = 0; j <= n; j++) {if(f[i][j]) {if(j + i <= n) add(f[i][j + i], f[i][j]);if(j + biao <= n) add(f[i + 1][j + biao], f[i][j]);}add(b[j], f[i][j]);}}add(b[0], 1);for(int i = 1; i < 4 * M; i <<= 1) pw[i] = poww(g, (mod - 1) / 2 / i), iw[i] = poww(pw[i], mod - 2);n++;int up = (n << 1) - 1;while(up - (up & -up)) up += (up & -up);fft(a, up, 1), fft(b, up, 1);for(int i = 0; i < up; i++) a[i] = 1ll * a[i] * b[i] % mod;fft(a, up, -1);for(int i = 1; i < n; i++) cout << a[i] << '\n';return 0;
}