萌新求助简单生成函数

做法：

令

dp_{i,j}

为排序后，第

j+

个数为

i

的方案数，同时令

f_i(x)=\sum\limits_{j=0}^{\infty}dp_{i,j}x^j

，则有：

f_i(x)=1+\sum\limits_{j<i\land(i-j)\mod 2=1} xf_j(x)

。

令

g_i(x)=\sum\limits_{j<i\land(i-j)\mod 2=0}f_i(x)

，则有

g_i(x)=1+g_{i-2}(x)+xg_{i-1}(x)

。然后矩阵快速幂即可。

但是这个做法 WA 了一个点，有没有好心人帮忙看看/kel

CPP

#include<bits/stdc++.h>
#include<atcoder/all>
#define int long long
#define endl '\n'
using namespace atcoder;
using namespace std;
const int N = 2e5 + 5,mod = 998244353;
int frac[N];
int qpow(int a,int b){
	int ans = 1;
	while(b){
		if(b & 1)ans = ans * a % mod;
		a = a * a % mod,b >>= 1;
	}
	return ans;
}
int C(int n,int m){
	if(n < m)return 0;
	return frac[n] * qpow(frac[m] * frac[n - m] % mod,mod - 2) % mod;
}
void init(int n){
	frac[0] = 1;
	for(int i = 1;i <= n;i++)frac[i] = frac[i - 1] * i % mod;
}
struct matrix{
	vector<int> a[3][3];
}base,tmp;
void add(vector<int> &a,const vector<int> &b){
	while(a.size() < b.size())a.push_back(0);
	for(int i = 0;i < b.size();i++)a[i] = (a[i] + b[i]) % mod;
}
matrix operator*(const matrix &a,const matrix &b){
	matrix c;
	for(int i = 0;i < 3;i++){
		for(int k = 0;k < 3;k++){
			for(int j = 0;j < 3;j++){
				add(c.a[i][j],convolution(a.a[i][k],b.a[k][j]));
			}
		}
	}
	return c;
}
matrix qpow(matrix a,int b){
	b--;
	matrix ans = a;
	while(b){
		if(b & 1)ans = ans * a;
		a = a * a,b >>= 1;
	}
	return ans;
}
int n,m;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	base.a[0][1].push_back(1);
	base.a[1][0].push_back(1);
	base.a[1][1].push_back(0);
	base.a[1][1].push_back(1);
	base.a[2][1].push_back(1);
	base.a[2][2].push_back(1);
	tmp.a[0][0].push_back(1);
	tmp.a[0][1].push_back(1),tmp.a[0][1].push_back(1);
	tmp.a[0][2].push_back(1);
	matrix ans = (tmp * qpow(base,m - 1));
	init(n);
	cout << (ans.a[0][0][n - 1] + ans.a[0][1][n - 1]) * frac[n] % mod;
}

萌新求助简单生成函数

讨论操作

回复

相关推荐

萌新求助简单生成函数