AGC065 D. Not Intersect

题目链接：https://atcoder.jp/contests/agc065/tasks/agc065_d

题目大意：圆上有 $n$ 个点，问有多少种连法，使得有 $m$ 条边且边不交叉（可以在端点处相交）

$n,m\le 10^7$

做法

神仙组合意义，投降。

当 $m=0$ 或者 $m>2n-3$ 时可以直接输出答案，下面默认 $n\ge 2,0<m\le 2n-3$

设 $f_i$ 表示 $n$ 个点 $i$ 条边的答案，$g_i$ 表示 $n$ 个点 $i$ 条边且允许重边的答案。

显然有：$f_n=\sum\limits_{i=1}^n\binom{n-1}{i-1}g_i$

则由二项式反演有：$g_n=\sum\limits_{i=1}^{n}(-1)^{n-i}\binom{n-1}{i-1}f_i$ 。

现在考虑怎么计算 $g_i$ ，考虑边不能交叉这个条件，如果你足够智慧，你就会发现有一个结构很符合这个要求：栈。

现在我们用这么一个过程去描述连边的过程：

从 $1$ 到 $n$ ，到达 $i$ 的时候，先弹出栈内的若干元素，再往栈内加入若干个 $i$ ，到最后栈为空，如果 $i$ 在 $j$ 的时候弹出就代表了一条 $(i,j)$ 的边。

显然，这个过程一一对应，现在就是计数了。

可以发现，$1$ 只能入栈，$n$ 只能出栈，所以我们不妨改为 $n-1$ 次入栈和出栈。（接下来假设要求 $g_k$ 的值）

现在就是 $a_i$ 表示入栈的次数，$b_i$ 表示出栈的次数，满足：

$$1\le i\le n-1,a_i\ge b_i,0\le a_i,b_i \le k,a_i\le a_{i+1},b_i\le b_{i+1},a_{n-1}=b_{n-1}=k$$

显然，一个合法的 $a$ 序列代表了一条从 $(0,0)$ 到 $(n-2,k)$ 只能向右或者向上的的路径，$b$ 同理。

则一个合法的 $a,b$ 序列对应了两条合法的路径，且满足一条路径始终在另外一条路径下端。

可以发现，我们设 $0$ 为向右，$1$ 为向上，假设我们能计算有 $a$ 个 $0$ ，$b$ 个 $1$ 时有多少对路径满足第二条路径在第一条路径下方，称作函数 $calc(a,b)$ ，那么我们所求的就是 $calc(n-2,k)$ 。

研究第 $i$ 步，可以发现就四种情况：$(0,0),(0,1),(1,0),(1,1)$ ，可以发现，就是要让每个时刻 $(1,0)$ 的数量不少于 $(0,1)$ 的数量，如果用折线法描述就是上面是：$0,-1,0,1$ ，然后不要让折线低过 $x$ 轴，显然，$-1,1$ 的数量是一样的，枚举 $1$ 的数量就可以知道四种情况的数量了：

$$\begin{align*} calc(a,b)&=\sum\limits_{i=0}^{min(a,b)}\frac{(2i)!}{i!(i+1)!}*\binom{a+b-2i}{a-i}*\binom{(a+b-2i)+(2i+1)-1}{(2i+1)-1}\\ &=\sum\limits_{i=0}^{min(a,b)}\frac{(2i)!}{i!(i+1)!}*\binom{a+b-2i}{a-i}*\binom{a+b}{2i}\\ &=\sum\limits_{i=0}^{min(a,b)}\frac{(2i)!}{i!(i+1)!}*\frac{(a+b-2i)!}{(a-i)!(b-i)!}*\frac{(a+b)!}{(2i)!(a+b-2i)!}\\ &=\sum\limits_{i=0}^{min(a,b)}\frac{(a+b)!}{i!(i+1)!(a-i)!(b-i)!}\\ &=\frac{(a+b)!}{a!(b+1)!}\sum\limits_{i=0}^{min(a,b)}\frac{a!}{i!(a-i)!}\frac{(b+1)!}{(i+1)!(b-i)!}\\ &=\frac{(a+b)!}{a!(b+1)!}\sum\binom{a}{i}\binom{b+1}{b-i}\\ &=\frac{(a+b)!}{a!(b+1)!}\binom{a+b+1}{b}\\ &=\frac{(a+b)!(a+b+1)!}{a!b!(a+1)!(b+1)!} \end{align*}$$

然后直接算就行了。

时间复杂度：$O(n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int N=3e7+105;
LL fc[N],nfc[N];
void init(){
    const int L=3e7+3;
    fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=L;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
    for(int i=2;i<=L;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
}
int n;LL m;
LL g[N];
LL calc(int a,int b){
    return fc[a+b+1]*fc[a+b]%mod*nfc[a]%mod*nfc[b]%mod*nfc[a+1]%mod*nfc[b+1]%mod;
}
LL C(int x,int y){
    return fc[x]*nfc[y]%mod*nfc[x-y]%mod;
}
int main(){
    init();
    scanf("%d%lld",&n,&m);
    if(!m){
        printf("1\n");
        return 0;
    }
    if(m>n+n-3){
        printf("0\n");
        return 0;
    }
    //n>=2
    for(int i=1;i<=m;i++)g[i]=calc(n-2,i);
    LL ans=0;
    for(int i=1;i<=m;i++){
        if((m-i)&1)ans=(ans-g[i]*C(m-1,i-1)%mod+mod)%mod;
        else ans=(ans+g[i]*C(m-1,i-1))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

坑

没有生成函数做法。