题目连接

https://ac.nowcoder.com/acm/contest/5881/D

解题思路

一开始我随便举了几个例子，感觉像是数学题，应该有数学公式，所以就手工画了个表，结果还真就神了，表格关于对角线对称。乍一看数值1，6，10……，想到会不会和组合数有关，比划了比划，还真就扯出关系了。

l\x    1  2  3  4  5

 1     1  1  1  1  1
 2     1  2  3  4  5
 3     1  3  6 10 15
 4     1  4 10 20 35
 5     1  5 15 35 70

l和x自减后：

l\x    0  1  2  3  4

 0     1  1  1  1  1
 1     1  2  3  4  5
 2     1  3  6 10 15
 3     1  4 10 20 35
 4     1  5 15 35 70

众所周知，10是C(5,2)，所以规律为C(l+x,min(l,x))，此时的l和x都是自减后的。
特殊情况特判，min(l,x)=0时，输出1。

最重要的还是组合数的求法：
繁琐的东西（里面的知识点详讲部分的链接） 不再扯了，就先提一下费马小定理的变形，记住就行， a^(mod-1)%mod=1 => b*a^(mod-2)%mod=b/a%mod
已知： C(n,m)=n!/(m!*(n-m)!)
由费马小定理变式可得： C(n,m)=n!*(m!)^(mod-2)%mod*((n-m)!)^(mod-2)%mod

总结一下求组合数的步骤：
S1：求出全部取模后的阶乘，保存在数组fac中；
S2：通过费马小定理+快速幂求出(m!)^(mod-2)%mod和((n-m)!)^(mod-2)%mod；
S3：三部分相乘并取模，输出。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=911451407;
const int N=2e6+10;//开两倍，因为C函数第一个参数最大为l+x

ll T,l,x;
ll fac[N];//阶乘

void Create(){//创建阶乘数组
    fac[0]=fac[1]=1;
    for(int i=2;i<=N;i++) fac[i]=fac[i-1]*i%mod;
}
ll KSM(ll x,ll p){//快速幂函数
    ll ans=1;
    while(p){
        if(p&1LL) ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
ll Inv(ll x){//逆元函数
    return KSM(x,mod-2);
}
ll C(ll n,ll m){//求组合数函数
    return fac[n]*Inv(fac[m])%mod*Inv(fac[n-m])%mod;//注意函数的参数是阶乘，很容易顺手写成m和n-m
}
void Solve(){
    cin>>T;
    while(T--){
        cin>>l>>x;
        l--,x--;
        if(!min(l,x)) cout<<1<<endl;
        cout<<C(l+x,min(l,x))<<endl;
    }
}
int main(){
    Create();
    Solve();
}