自动搬运

查看原文

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 23:07:03，当前版本为作者最后更新于2025-01-28 23:37:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于不允许有长度为 $3$ 的简单路，故每个连通块必然是菊花或三元环。

考察 $3\mid n$，我们发现可以取到最大值，即全部取三元环。

考察 $3\nmid n$，此时必要需要至少一个菊花。然而一个菊花会让边数从 $n$ 减少 $1$，故只会放一个菊花。

也就是说我们最后的图是由若干三元环以及一个菊花组成。

图是有标号的，考虑将三元环在编号最大的点处计算。

考虑 $dp_{i,0/1}$ 表示放了 $i$ 个点，是否选菊花中心的方案数。

每次转移可以加入一个菊花的点/中心，或者加入某个三元环中编号最大的点。此时，另外两个点与已放置需要乘上个组合数。

总复杂度 $O(n)$。注意选择 $2$ 个点时选哪个为中心没有区别，需要减去。

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod {
    ull b, m;
    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
    ull reduce(ull a) {
        ull q = (ull)((L(m) * a) >> 64);
        ull r = a - q * b; // can be proven that 0 <= r < 2*b
        return r >= b ? r - b : r;
    }
};
FastMod F(2);
int mod;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=F.reduce(ans*a);
		a=F.reduce(a*a);
		b>>=1;
	}
	return ans;
}
int f[30000005][2],fac[30000005],inv[30000005],inv2;
signed main(){
	int q; cin>>q>>mod; F=FastMod(mod);
	fac[0]=1; for(int i=1;i<=30000000;i++) fac[i]=F.reduce(fac[i-1]*i); inv2=(mod+1)/2;
	inv[30000000]=qp(fac[30000000],mod-2); for(int i=29999999;i>=0;i--) inv[i]=F.reduce(inv[i+1]*(i+1));
	f[0][0]=1;
	for(int i=0;i<=30000000;i++){
		f[i][0]=F.reduce(f[i][0]);
		f[i][1]=F.reduce(f[i][1]);
		//select a cycle
		f[i+3][0]+=f[i][0]*F.reduce((i+2)*(i+1)/2);
		f[i+3][1]+=f[i][1]*F.reduce((i+2)*(i+1)/2);
		//select a point
		f[i+1][0]+=f[i][0];
		f[i+1][1]+=f[i][0]+f[i][1];
	}
	while(q--){
		int n; cin>>n;
		if(n%3==0){
			cout<<F.reduce(F.reduce(fac[n]*inv[n/3])*qp(6,mod-1-n/3))<<"\n";
		}
		else if(n%3==1){
			cout<<f[n][1]<<"\n";
		}
		else{
			cout<<F.reduce(f[n][1]+mod-F.reduce(F.reduce(F.reduce(fac[n-2]*inv[n/3])*qp(6,mod-1-n/3))*F.reduce(n*(n-1)/2)))<<"\n";
		}
	}
	return 0;
}