LOJ6609 无意识的石子堆 加强版

Link
设有\(k\)列有\(2\)枚棋子，那么有\(2n-2k\)列有\(1\)枚棋子，\(m-2n+k\)列为空。
将其转化为二分图，左部有\(n\)个点且每个点度数为\(2\)，右边有\(k\)个点度数为\(2\)，有\(2n-2k\)个点度数为\(1\)，要求它的完美匹配数。
将度数\(2\)为的点拆成两个度数为\(1\)的点，那么此时左右各有\(2n\)个点，考虑容斥枚举重边的数量，则总的匹配数量为：

这可以利用卷积\(O(n\log n)\)求出，最后答案为：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using i64=long long;
const int N=1<<22|1,P=943718401;
int n,lim,rev[N];i64 m,w[N],fac[N],ifac[N],ffac[N],f[N],g[N];
i64 mod(i64 x){return x+(x>>63&P);}
i64 pow(i64 a,i64 b){i64 r=1;for(;b;b>>=1,a=a*a%P)if(b&1)r=a*r%P;return r;}
void init(int deg)
{
    int half=(lim=1<<(32-__builtin_clz(deg)))/2;i64 g=pow(7,(P-1)/lim);
    w[half]=fac[0]=ffac[0]=1;
    for(int i=1;i<lim;++i) rev[i]=(rev[i>>1]>>1)|(i&1? half:0);
    for(int i=1;i<=deg;++i) fac[i]=i*fac[i-1]%P,ffac[i]=(m-i+1)%P*ffac[i-1]%P;
    ifac[deg]=pow(fac[deg],P-2);
    for(int i=deg;i;--i) ifac[i-1]=ifac[i]*i%P;
    for(int i=half+1;i<lim;++i) w[i]=g*w[i-1]%P;
    for(int i=half-1;i;--i) w[i]=w[i<<1];
}
void DFT(i64*a)
{
    for(int i=1;i<lim;++i) if(i<rev[i]) std::swap(a[i],a[rev[i]]);
    for(int i=1;i<lim;i<<=1) for(int j=0,d=i<<1;j<lim;j+=d) for(int k=0,x;k<i;++k) x=w[i|k]*a[i|j|k]%P,a[i|j|k]=mod(a[j|k]-x),a[j|k]=mod(a[j|k]+x-P);
}
int main()
{
    i64 ans=0,pw;
    scanf("%d%lld",&n,&m),init(n+n),memcpy(g,ifac,8*n+8);
    for(int i=(pw=1,0);i<=n;++i) f[i]=mod((i&1? -1:1)*fac[2*(n-i)]*pw%P*ifac[i]%P*ifac[n-i]%P),pw=mod(2*pw-P);
    DFT(f),DFT(g);
    for(int i=0;i<lim;++i) f[i]=f[i]*g[i]%P;
    std::reverse(f+1,f+lim),DFT(f);
    for(int i=(pw=1,0),x=P-P/2;i<=n;++i) ans=mod(ans+ffac[2*n-i]*pw%P*ifac[2*(n-i)]%P*f[i]%P-P),pw=pw*x%P;
    printf("%lld",2*ans*fac[n]%P*pw%P*(P-P/lim)%P);
}

LOJ6609 无意识的石子堆 加强版

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12926878.html