「题解」提高组 tg

(未完待续)

题目链接:GMOJ 6302

题目

题解

先贴一下代码。

#include<cstdio>
#include<algorithm>
using std::swap;
typedef long long ll;
#define MOD 1000000007
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    register char ch=getchar();
    register int res=0;
    while(ch<'0'||'9'<ch)ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return res;
}
const int MAXN=(10000000<<1)+5;
int T,fact[MAXN],inv[MAXN];//开int省空间
void Init(int);
int pow(int,int,int);
int C(int,int,int);
int main(void){
    freopen("tg.in","r",stdin);
    freopen("tg.out","w",stdout);
    register int ans1,ans2;
    Init(MOD);
    T=read();
    //scanf("%d",&T);
    while(T--){
        static int n,x,y;
        n=read(),x=read(),y=read();
        //scanf("%d%d%d",&n,&x,&y);
        if(x<y)
            swap(x,y);
        ans1=(C(x+y-2,x-1,MOD)-C(x+y-2,x,MOD)+MOD)%MOD;
        ans2=(C(2*n-x-y,n-x,MOD)-C(2*n-x-y,n-x-1,MOD)+MOD)%MOD;
        printf("%lld\n",(ll)ans1*ans2%MOD);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void Init(int mod){
    register int i;
    fact[0]=1;
    for(i=1;i<MAXN;++i)
        fact[i]=(ll)fact[i-1]*i%mod;
    inv[MAXN-1]=pow(fact[MAXN-1],mod-2,mod);
    for(i=MAXN-2;i>=0;--i)
        inv[i]=(ll)inv[i+1]*(i+1)%mod;
    return;
}
int pow(int x,int exp,int mod){
    register int res=1;
    while(exp){
        if(exp&1)
            res=(ll)res*x%mod;
        x=(ll)x*x%mod;
        exp>>=1;
    }
    return res;
}
int C(int x,int y,int mod){
    return (ll)fact[x]*inv[y]%mod*inv[x-y]%mod;
}