CF755G PolandBall and Many Other Balls 题解

老师潦草的笔记（

题目大意

给你 $n$ 个球，让你选 $m(1 \le m \le k)$ 组球。每组只有 $1$ 个球或 $2$ 个相邻球。

令选出 $m$ 组球的方案数为 $f_m$，现在让你输出 $f_i(1 \le k \le i) % 998244353$

数据范围

$$n \le 10^9, k < 2^{15}$$

分析

看到这一题的第一眼，我想到了用 dp 求解。

假设在 $i$ 组球分成 $j$ 组的方案为 $f_{[i,j]}$，我们能得到转移方程 $f_{[i,j]}=f_{[i-1,j]}+f_{[i-1,j-1]}+f_{[i-2,j-1]}$

AC 代码

/*****************************************
备注：
******************************************/
#include<queue>
#include<math.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<iomanip>
#include<map>
#include<string.h>
#include<algorithm>
using namespace std;
#define int unsigned long long
const int MAXN = 1 << 16;
const int MR = 10 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
void add(int &x,int &y)
{
	x += y;
	if(x >= MOD)x -= MOD;
}
int ksm(int a,int b)
{
	int ans = 1;
	while(b)
	{
		if(b & 1)ans = ans * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return ans;
}
vector<int> ans;//存储每一个f{1~k}的答案
int n, k, bin[MAXN];
map<int, vector<int> > mp;//记忆化
void NTT(vector<int> &A, int num)
{
	int x[MAXN], y[MAXN];
	for(int i = 0;i < MAXN; i++)
	{
		x[i] = A[bin[i]];
	}
	int xxx, xxxx;
	if(num)xxx = 3,xxxx = 1;
	else xxx = (MOD + 1) / 3, xxxx = ksm(MAXN, MOD - 2);
	for(int k = 1;k < MAXN; k <<= 1)
	{
		int tmp = ksm(xxx, (MOD - 1) / k / 2);
		for(int i = y[0] = 1;i < k; i++)
		{
			y[i] = y[i - 1] * tmp % MOD;
		}
		for(int i = 0;i < MAXN; i += (k << 1))
		{
			for(int j = 0;j < k; j++)
			{
				int ttmp = y[j] * x[i|j|k] % MOD;
				x[i|j|k] = x[i|j] + MOD - ttmp;
				x[i|j] += ttmp;
			}
		}
	}
	for(int i = 0;i < MAXN; i++)
	{
		A[i] = x[i] % MOD * xxxx % MOD;
	}
}
vector<int> operator *(vector<int> a,vector<int> b)
{
	for(int i = MAXN  >> 1;i < MAXN; i++)a[i] = b[i] = 0;
	NTT(a, 1);
	NTT(b, 1);
	for(int i = 0;i < MAXN; i++)a[i] = a[i] * b[i] % MOD;
	NTT(a, 0);
	return a;
}
vector<int> solve(int n)
{
	vector<int> ans(MAXN, 0);//开MAXN,清0
	if(n == 0)
	{
		ans[0] = 1;
		return ans;
	}
	if(n == 1)
	{
		ans[0] = ans[1] = 1;
		return ans;
	}
	if(n == 2)
	{
		ans[0] = ans[2] = 1;
		ans[1] = 3;
		return ans;
	}
	if(mp.find(n) != mp.end())return mp[n];
	int tmp = (n - 2) >> 1;
	vector<int> l = solve(tmp), r = solve(tmp + 1);
	vector<int> xxx = r;
	for(int i = 1;i < MAXN; i++)
	{
		add(xxx[i], r[i - 1]);
		add(xxx[i], l[i - 1]);
	}
	vector<int>ll = l * (n & 1 ? r : l);
	vector<int>rr = r * (n & 1 ? xxx : r);
	for(int i = 0;i < MAXN; i++)
	{
		ans[i] = rr[i];
		if(i > 0)add(ans[i], ll[i - 1]);
	}
	mp[n] = ans;
	return ans;
}
signed main()
{
	for(int i = 0;i < MAXN; i++)
	{
		bin[i] = (bin[i >> 1] >> 1) | ((i & 1) << 15);
	}
	cin >> n >> k;
	ans = solve(n);
	for(int i = 1;i <= k; i++)
	{
		cout << ans[i] << ' ';
	}
	return 0;
}