J.Involutions

题解

令 为大小为 的集合对应的答案。

第 个点可以和前 个点之一配对，也可以形成不动点，因此有转移式 。

从组合数角度理解，分别考虑选取 个配对的贡献，则有 。

注意到 大于 的项会被消去，对剩余项运用 Lucas 定理可以得到 。

据此考虑暴力枚举前 项，发现在极端数据下运行时间约 4.7 秒，无法通过。

因此考虑循环展开，即一次枚举 与 ，此时运行时间缩小至一半，即 2.3 秒，可以通过本题。

Bonus：尝试利用循环展开通过 H. Color of Goods。

代码

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

#define M 998244353

int i,j,k,n,m,t;
ll n0,res,f1,f2,f3,f4;

int main(){
	cin>>n0>>m;
	f1=1; f2=m; n=n0%M;
	for(i=1;i+1<n;i+=2){
		f4=((1ll*m*m+i+1)%M*f2+1ll*i*m%M*f1)%M;
		f3=(f1*i+f2*m)%M;
		f1=f3; f2=f4;
	}
	for(;i<n;i++){
		f2=(f1*i+f2*m)%M;
	}
	while(n0>n){f2=f2*m%M; n0-=M;}
	cout<<f2;
}