[ICPC 2018 Asia Qingdao Onsite L]Sub-cycle Graph

Link

n个点m条边组成的无环图的数目。生成函数学的很不好。

Solution

题目中的图本质上是有标号链的集合。
长度为n的有标号链个数为\max(1,\frac {n!}2)
有标号链的egf为

E=x+\frac 12(x^2+x^3+…)=x(\frac {1-\frac x2}{1-x})

那么k条有标号链的序列的egf为E^k,由于n个点m条边会出现n-m条链,因此答案就是\frac {n!}{(n-m)!}([x^n] (E^{n-m}))
至于求[x^n]E^k的方法,A=(1-\frac x2)^k,B=(\frac 1{1-x})^k可以求出来,求出x^{n-k}[A*B]就OK了。

\begin{aligned}
A&=\sum_{i=0}^k(-1)^i\frac {\binom{k}{i}}{2^i}x^i\\
B&=\sum_{i=0}^k\binom{k-1+i}{i}x^i
\end{aligned}

Code

#include <bits/stdc++.h>

const int N=2e5,XN=N+11,P=1e9+7;

int Add(int x,int const &y) {
    return (x+=y)>=P?x-P:x;
}

int Mul(long long x,int const &y) {
    return x*y%P;
}

int Pow(long long base,int v) {
    static long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

int fact[XN],ifact[XN],inv2[XN];

int C(int n,int m) {
    return n>=m?Mul(fact[n],Mul(ifact[m],ifact[n-m])):0;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    fact[0]=1;inv2[0]=1;inv2[1]=Pow(2,P-2);
    for(int i=1;i<=N;++i) {
        fact[i]=Mul(fact[i-1],i);
        inv2[i]=Mul(inv2[i-1],inv2[1]);
    }
    ifact[N]=Pow(fact[N],P-2);
    for(int i=N-1;i>=0;--i)
        ifact[i]=Mul(ifact[i+1],i+1);

    int T;std::cin>>T;
    while(T--) {
        int n,m;std::cin>>n>>m;
        if(m>n)
            std::cout<<0<<'\n';
        else if(n==m)
            std::cout<<Mul(fact[n-1],inv2[1])<<'\n';
        else {
            int k=n-m;int Ans=0;
            for(int i=0;i<=n-k;++i)
                Ans=Add(Ans,Mul(Mul(i&1?P-1:1,Mul(C(k,i),inv2[i])),C(n-i-1,k-1)));
            Ans=Mul(Ans,Mul(fact[n],ifact[n-m]));
            std::cout<<Ans<<'\n';
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注