P11402 题解

dAniel_lele · 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;
}