ZOJ4069 Subcycle

$$ \text{题意：} \\ \text{求}n\text{个点，}n-m\text{个链组成的带标号图的个数。} \\ \text{首先特判,}n<m\text{为0，}n=m\text{为}\frac{\left( n-1 \right) !}{2} \\ \text{对于其他情况，考虑}egf \\ \text{设}T\left( x \right) =\sum_{i\ge 0}{f_i\frac{x^i}{i!}} \\ f_i\text{表示}i\text{个点的带标号链的个数，} \\ \text{显然，}f_0=\text{0,}f_1=\text{1,}f_n=\frac{n!}{2}\left( n\ge 2 \right) \\ \text{则}T\left( x \right) =x+\frac{x^2}{2}+\frac{x^3}{2}+……=\frac{x}{2\left( 1-x \right)}+\frac{x}{2}=\frac{2x-x^2}{2\left( 1-x \right)}=\frac{x\left( 2-x \right)}{2\left( 1-x \right)} \\ \text{设}k=n-m \\ \text{则}T^k\left( x \right) \text{表示}k\text{条链的生成函数。} \\ \text{任意两条带标号的链合并在一起可以形成一个有两条链的图，同时要重新分配标号，所以需要使用}egf \\ T\left( x \right) ^k=x^k\times 2^{-k}\times \frac{\left( 2-x \right) ^k}{\left( 1-x \right) ^k} \\ \text{我们需要求出}T\left( x \right) ^k\text{的}n\text{次项，表示}n\text{个点}m\text{条链的方案数} \\ \frac{1}{\left( 1-x \right) ^k}=\sum_{i\ge 0}{\left( \begin{array}{c} i+k-1\\ i\\ \end{array} \right) x^i} \\ \left( 2-x \right) ^k=\sum_{i\ge 0}{\left( \begin{array}{c} k\\ i\\ \end{array} \right)}2^{k-i}\times \left( -1 \right) ^k\times x^k \\ \text{将其中一个多项式偏移}k\text{位}\left( x^k \right) \text{后，对这两个多项式进行简单卷积，求出其}n\text{次项即可。} \\ \text{求出来后的答案需要乘}n!,\text{因为这是}egf\text{，同时需要除}k!,\text{因为这种做法考虑了不同链的组成顺序} \\ $$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cmath>
typedef long long int int_t;

using std::cin;
using std::endl;
using std::cout;

const int_t LARGE = 400000;
const int_t mod = 1e9 + 7;

int_t fact[LARGE + 1] = {1};
int_t fact_inv[LARGE + 1] = {1};
int_t pow2[LARGE + 1] = {1};
int_t power(int_t base,int_t index){
    base = (base % mod + mod) % mod;
    if(index < 0){
        base = power(base,mod - 2);
        index *= -1;
    }
    int_t result = 1;
    while(index){
        if(index & 1) result = result * base % mod;
        base = base * base % mod;
        index >>= 1;
    }
    return result;
}
int_t C(int_t n,int_t m){
    if(n < m) return 0;
    return fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod ;
}

int main(){
    for(int_t i = 1;i <= LARGE ;i ++){
        fact[i] = fact[i - 1] * i % mod;
        pow2[i] = pow2[i - 1] * 2 % mod;
    }
    fact_inv[LARGE] = power(fact[LARGE],-1);
    for(int_t i = LARGE - 1;i >= 1;i --){
        fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod;
    }
    int T;
    scanf("%d",&T);
    for(int _i = 1;_i <= T;_i ++){
        int_t n,m;
        scanf("%lld%lld",&n,&m);
        if(n < m){
            cout << 0 << endl;
            continue;
        }else if(n == m){
            cout << fact[n - 1] * power(2 , -1) % mod << endl; 
            continue;
        } 
        m = n - m;
        //A:分子多项式,B:分母多项式 
        static int_t A[LARGE + 1],B[LARGE + 1];
        for(int_t i = 0;i <= m;i++){
            int_t flag = 1;
            if(i % 2) flag = mod - 1;
            A[i] = C(m,i) * flag % mod * pow2[m - i] % mod;
        }
        for(int_t i = 0;i <= n;i++){
            B[i] = C(m + i - 1,i);
        }
        for(int_t i = n + m; i >= m ; i --){
            B[i] = B[i - m];
        }
        for(int_t i = 0;i < m;i ++) B[i] = 0;
        int_t result = 0;
        for(int_t i = 0;i <= n;i++){
            result = (result + A[i] * B[n - i] % mod + mod) % mod;
        }
        result = result * power(2,- m) % mod;
        result = result * fact[n] % mod;
        result = result * fact_inv[m] % mod;
        printf("%d\n",(int)result);
        std::fill(A,A + n + 1,0);
        std::fill(B,B + n + m + 1,0);
    }
	return 0;
}