题意：
给定\(n\)个小球，标号为\(1,2,...,n\)，现在要从中选出\(m\)组。每一组只能包含一个小球或者两个标号相邻的小球。
给定\(k\)，求出所有分组为\(m,1\leq m\leq k\)的方案数。
思路：
考虑直接暴力\(dp:dp_{i,j}\)表示前\(i\)个球划分\(j\)个组的方案数，那么考虑第\(i\)个数划分的三种情况：
- 不加入任意一组中，那么\(dp_{i,j}=dp_{i-1,j}\);
- 和\(i-1\)合并为一组，那么此时就有\(dp_{i,j}=dp_{i-2,j-1}\);
- 自己单独为一组，那么\(dp_{i,j}=dp_{i-1,j-1}\)。
但这样\(dp\)时空显然不能承受，观察上面\(dp\)转移式，我们相当于从最近的一处断开，其实我们可以考虑倍增进行\(dp\)，也就是从中间断开。
我们定义\(F_i\)为一个\(i\)次多项式（其实就是生成函数），每一项系数为将\(i\)个数划分\(j\)组的方案数。
假设现在知道\(F_a,F_{a-1},F_{a-2}\)，那么我们容易推出相关式子：
- 从中间断开，即\(a,a+1\)不在同一组中：\(F_{a+a}=F_a*F_a\);
- \(a,a+1\)为一组时：\(F_{a+a}=x* F_{a-1}*F_{a-1}\);
\(F_{2a-1},F_{2a-2}\)同理。
但这样只能做\(n\)为\(2\)的次幂的情况，我们考虑求\(F_{a+1}:\)
- \(\displaystyle F_{a+1}=2F_{a}+xF_{a-1}\)
这样我们即可类似于快速幂那样求出\(n\)为任意数的值。
现在我们已知\(F_{a-2},F_{a-1},F_a\)，就可以推得\(F_{2a-2},F_{2a-1},F_{2a}\)。
并且也可以通过\(F_{a-2},F_{a-1},F_{a}\)得到\(F_{a-1},F_{a},F_{a+1}\)。
这个题就愉快地做出来了(好难)
代码如下：
/*
* Author: heyuhhh
* Created Time: 2020/4/10 10:46:08
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <assert.h>
#define MP make_pair
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << std::endl; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ‘ ‘; err(args...); }
template <template<typename...> class T, typename t, typename... A>
void err(const T <t> &arg, const A&... args) {
for (auto &v : arg) std::cout << v << ‘ ‘; err(args...); }
#else
#define dbg(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int MOD = 998244353, inv2 = (MOD + 1) >> 1;
const int N = 4e5 + 5, M = (1 << 19); //四倍空间,M=2^x且M>=N
typedef vector <int> Poly;
#define ri register int
#define cs const
inline int add(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
inline int dec(int a, int b) {return a < b ? a - b + MOD : a - b;}
inline int mul(int a, int b) {return 1ll * a * b % MOD;}
inline int qpow(int a, int b) {int res = 1; while(b) {if(b & 1) res = mul(res, a); a = mul(a, a); b >>= 1;} return res;}
int rev[N], inv[N], pw[M], W[2][M];
inline void init() {
inv[0] = inv[1] = 1;
for(ri i = 2; i < N; i++) inv[i] = mul(inv[MOD % i], MOD - MOD / i);
int w0 = qpow(3, (MOD - 1) / M), w1 = qpow((MOD + 1) / 3, (MOD - 1) / M);
W[0][0] = W[1][0] = 1;
for(ri i = 1; i < M; i++) {
W[0][i] = mul(W[0][i - 1], w0);
W[1][i] = mul(W[1][i - 1], w1);
}
}
inline void init_rev(int len) {
for(ri i = 0; i < len; i++) rev[i] = rev[i >> 1] >> 1 | ((i & 1) * (len >> 1));
}
inline void NTT(Poly &a, int n, int op) {
for(ri i = 0; i < n; i++) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(ri i = 1; i < n; i <<= 1) {
int t = M / (i << 1), t2 = (op == -1 ? 1 : 0);
for(ri j = 0; j < i; ++j) pw[j] = W[t2][j * t];
int wn = (op == -1 ? W[1][i] : W[0][i]);
for(ri j = 0; j < n; j += (i << 1)) {
for(ri k = 0, x, y; k < i; ++k) {
x = a[j + k], y = mul(pw[k], a[j + k + i]);
a[j + k] = add(x, y);
a[j + k + i] = dec(x, y);
}
}
}
if(op == -1) for(ri i = 0; i < n; i++) a[i] = mul(a[i], inv[n]);
}
inline Poly operator + (cs Poly &a, cs Poly &b) {
Poly c = a; c.resize(max(sz(a), sz(b)));
for(ri i = 0; i < sz(b); i++) c[i] = add(c[i], b[i]);
return c;
}
inline Poly operator * (Poly a, Poly b) {
int n = sz(a), m = sz(b), l = 1;
while(l < n + m - 1) l <<= 1;
init_rev(l);
a.resize(l), NTT(a, l, 1);
b.resize(l), NTT(b, l, 1);
for(ri i = 0; i < l; i++) a[i] = mul(a[i], b[i]);
NTT(a, l, -1);
a.resize(n + m - 1);
return a;
}
void move(Poly &t) {
t.resize(sz(t) + 1);
for(int i = sz(t) - 1; i; i--) t[i] = t[i - 1];
t[0] = 0;
}
vector <Poly> add(cs vector <Poly> &f) {
Poly t = f[2] + f[1];
move(t);
return vector <Poly> {f[1], f[2], f[2] + t};
}
Poly combine(Poly &a, Poly &b, Poly &c, Poly &d) {
Poly A = a * b, B = c * d;
move(B);
Poly ans = A + B;
return ans;
}
vector <Poly> combine(vector <Poly> &f) {
vector <Poly> g(3);
g[2] = combine(f[2], f[2], f[1], f[1]);
g[1] = combine(f[2], f[1], f[1], f[0]);
g[0] = combine(f[1], f[1], f[0], f[0]);
return g;
}
void run() {
init();
int n, k; cin >> n >> k;
vector <Poly> f(3);
f[0] = vector <int> {1};
f[1] = vector <int> {1, 1};
f[2] = vector <int> {1, 3, 1};
int high;
for(high = 31; high >= 0; high--) if(n >> high & 1) break;
for(--high; high >= 0; high--) {
if(n >> high & 1) f = add(f);
if(high) {
vector <Poly> g = combine(f);
f.swap(g);
}
for(int i = 0; i < 3; i++) f[i].resize(k + 1);
}
int o = (n == 1 ? 1 : 2);
for(int i = 1; i <= k; i++) {
cout << f[o][i] << " \n"[i == k];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(20);
run();
return 0;
}