[NOIP模拟测试7]visit 题解(组合数学+CRT+Lucas定理)

Orz

因为有T的限制，所以不难搞出来一个$O(T^3)$的暴力dp

但我没试据说有30分？

正解的话显然是组合数学啦

首先$n,m$可能为负，但这并没有影响，

我们可以都把它搞成正的即都看作向右上方走

那么可以想到真正有效的步都是向右或者向上走的其它两个方向都是在起反作用

设u为向上走步数，d下，l左，r右

它们满足关系：

$r-l=m,u-d=n,T=u+d+l+r$

因为有效步数为$m+n$，所以$T-m-n$必为偶数

因为要保证剩下的步上下均分，左右均分

枚举$udlr$其中一个可得最终答案：

$ans=\sum \limits_{i=n,2|(i-n)}^{t-m} \binom{t}{i} \binom{i}{\frac{i-n}{2}} \binom{t-i}{\frac{t-i-m}{2}}$

(从天皇那里copy过来的)

按道理讲本题应该结束了

但丧心病狂的出题人还要恶心你一下：模数可能不为质数

但也给出一定是几个互不相同的质数之积，从exLucas的魔爪中拯救了我们

之后就中国剩余定理就行了

把模数分解出质因子$p[i]$，对于每个因子都算一边答案，记为$ans[i]$

那么得到最后答案的过程，就相当于求解

$\begin{cases} x\equiv ans_1(mod\ p_1)\\ x\equiv ans_2(mod\ p_2)\\ x\equiv ans_3(mod\ p_3)\\ ...\\ x\equiv ans_n(mod\ p_n)\\ \end{cases}$

这不裸的CRT么？板子打一遍就完事了。

扩欧都不用打，可以用前边的快速幂结合费马小定理解CRT里的同余方程。

//#define R

#include<cstdio>

#include<iostream>

#include<cstring>

#include<vector>

#include<cmath>

#define re register

using namespace std;

const int N=;

typedef long long ll;

int T,mod,n,m;

ll fac[N],ans[];

vector<int> fact;

int abss(int x)

{

    return x<?-x:x;

}

void divi(int x)

{

    int sq=sqrt(x)+;

    for(int i=;i<=sq;i++)

    {

        if(x%i==)

        {

            fact.push_back(i);

            while(x%i==)x/=i;

        }

        if(x==)break;

    }

    if(x!=)fact.push_back(x);

}

ll qpow(ll a,ll b,ll p)

{

    ll res=;a=a%p;

    while(b)

    {

        if(b&)res=res*a%p;

        a=a*a%p;

        b>>=;

    }

    return res;

}

ll C(ll x,ll y,ll p)

{

    if(x<y)return ;

    return fac[x]*qpow(fac[y],p-,p)%p*qpow(fac[x-y],p-,p)%p;

}

ll lucas(ll x,ll y,ll p)

{

    if(!y)return ;

    return C(x%p,y%p,p)*lucas(x/p,y/p,p)%p;

}

void getfac(ll p)

{

    fac[]=;

    for(int i=;i<=T;i++)

        fac[i]=1LL*i*fac[i-]%p;

}

int main()

{

    scanf("%d%d%d%d",&T,&mod,&n,&m);

    n=abss(n),m=abss(m);

    divi(mod);

    int sz=fact.size();

    for(re int now=;now<sz;now++)

    {

        int p=fact[now];getfac(p);

        for(re int i=n;i<=T-m;i++)

        {

            if((i-n)&||(T-i-m)&)continue;

            ll res=;

            res=res*lucas(T,i,p)%p*lucas(i,(i-n)/,p)%p*lucas(T-i,(T-i-m)/,p)%p;

            ans[now]=(ans[now]+res)%p;

        }

    }

    ll anss=;

    for(re int i=;i<sz;i++)

    {

        ll times=mod/fact[i];

        ll ress=qpow(times,fact[i]-,fact[i]);

        ress=(ress%fact[i]+fact[i])%fact[i];

        anss=(anss+times*ress*ans[i])%mod;

    }

    cout<<(anss+mod)%mod<<endl;

    return ;

}

巴特西

[NOIP模拟测试7]visit 题解(组合数学+CRT+Lucas定理)

最新文章

热门文章