牛客练习赛62 B. 病毒扩散

大致题意:自行看题.
分析:打表前10秒的情况，发现就是n次多项式系数问题.手推规律 t秒合法答案: C[t-x][y]*C[t][x]. 然后再判断一下没有感染的情况---( x+y>t ).

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+10;
const int mod=998244353;


ll qpow(ll a, ll b)// 快速幂
{
    ll ans = 1;
    a = a % mod;
    while (b)
    {
        if(b & 1) ans = (ans* a) % mod;
        a = ( a*a )% mod;
        b = b >> 1;
    }
    return ans;
}




ll c[maxn];

ll xishu( ll n,ll m ,ll k )
{
    return   ( c[k] * qpow( c[m] * c[k - m], mod - 2) ) % mod;
}

int main()
{

    c[1]=1,c[0]=1;
    for( ll i=2;i<maxn;i++ ) c[i]=(c[i-1]*i)%mod;
    int n;
    scanf("%d",&n);
    while( n-- )
    {
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        if( a+b>t )
        {
            puts("0");
            continue;
        }

        ll x1=xishu( b,t-b,t);
        ll x2=xishu( a,t-b-a,t-b);
        printf("%lld\n",(x1*x2)%mod);
    }
    return 0;
}

/*
第0秒
1
1 1

第1秒
1
1*2 1*2
1   2   1

第2秒
1
1*3 1*3
1*3 2*3 1*3
1   3   3   1


第3秒
1
4 4
6 12 6
4 12 12 4
1 4 6 4 1

--->

1
1*4 1*4
1*6 2*6 1*6
1*4 3*4 3*4 1*4
1 4 6 4 1

*/