【模拟7.22】visit(卢卡斯定理&&中国剩余定理)

如此显然的组合数我把它当DP做，我真是。。。。

因为起点终点已经确定，我们发现如果我们确定了一个方向的步数其他方向也就确定了

组合数做法1：

设向右走了a步，然后向左走了b=a-n步，设向上为c，向下为d;

c+d=t-a-b; c-d=m;

求出c=（t+n+m-i-i）/2;if(c%2)continue;

(因为如果c不能整除2表示向右多走的步数无法走回)

组合数做法2：

参考nc神犇的做法

首先设水平方向一共走了i步，所以(i-n)/2为水平方向上返回的步数，

竖直方向上步数t-i，中同理返回的是（t-i-m）/2;

式子C(t,i)*C(i,(i-n)/2)*C(t-i,(t-i-m)/2)

(因为竖直方向+水平方向步数=t，所以不用乘C(t-i，t-i))

至于卢卡斯和中国剩余定理（随便总结的）

我们发现数据为多个质数乘积，显然可以用中国剩余定理求解，当然要提前分解质因数

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<stack>
  8 #include<vector>
  9 #include<queue>
 10 #define MAXN 100001
 11 #define ps push_back
 12 #define ll long long
 13 using namespace std;
 14 vector<int>su;ll jie[MAXN];
 15 void fen(int x)
 16 {
 17    for(int i=2;i<=sqrt(x);++i)
 18    {
 19        if(x%i==0)
 20        {
 21            while(x%i==0)
 22            {
 23                x/=i;
 24            }
 25            su.ps(i);
 26        }
 27    }
 28    if(x!=1)
 29    {
 30           su.ps(x);
 31    }
 32 }
 33 ll pow(ll x,ll y,ll mod)
 34 {
 35     ll ans=1;
 36     if(y==0)return 1;
 37     while(y)
 38     {
 39        if(y&1)ans=ans*x%mod;
 40        x=x*x%mod;
 41        y>>=1;
 42     }
 43     return ans%mod;
 44 }
 45 ll C(ll x,ll y,ll mod)
 46 {
 47     if(y>x)return 0;
 48     if(y==0)return 1;
 49     return jie[x]*pow(jie[y]*jie[x-y]%mod,mod-2,mod)%mod;
 50 }
 51 ll lus(ll x,ll y,ll mod)
 52 {
 53    if(y>x)return 0;
 54    if(y==0)return 1;
 55    return lus(x/mod,y/mod,mod)*C(x%mod,y%mod,mod)%mod;
 56 }
 57 ll M[MAXN],ans[MAXN];
 58 void exgcd(ll a,ll b,ll &x,ll &y)
 59 {
 60    if(b==0){
 61       x=1;y=0;return ;
 62    }
 63    exgcd(b,a%b,x,y);
 64    ll z=x;x=y;y=z-(a/b)*y;
 65    return ;
 66 }
 67 ll sum;ll len=1;
 68 void CRT()
 69 {
 70    for(ll i=0;i<su.size();++i)
 71    {
 72       len*=su[i];    
 73       //printf("%lld
",len);  
 74    }
 75    for(ll i=0;i<su.size();++i)
 76    {
 77       M[i]=len/su[i];
 78    }
 79    for(ll i=0;i<su.size();++i)
 80    {
 81         ll x,y;
 82         exgcd(M[i],su[i],x,y);
 83         x=(x+su[i])%su[i];
 84         sum=(sum+ans[i]*M[i]*x)%len;
 85         //printf("sum=%lld ans=%lld M=%lld x=%lld
",sum,ans[i],M[i],x);
 86    }
 87    printf("%lld
",sum);
 88 }
 89 ll t;
 90 void fir(ll mod)
 91 {
 92     for(ll i=1;i<=min(mod,t);++i)
 93     {
 94         jie[i]=(jie[i-1]*i)%mod;
 95     }
 96 }
 97 ll MOD,n,m;
 98 int main()
 99 {
100       scanf("%lld%lld",&t,&MOD);
101       scanf("%lld%lld",&n,&m);
102       if(n<0)n=-n;
103       if(m<0)m=-m;
104       jie[0]=1;    
105       fen(MOD);
106       for(ll k=0;k<su.size();++k)
107       {
108           fir(su[k]);
109           ll mod=su[k];
110           //printf("mod=%lld
",mod);
111           for(ll i=n;i<=t-m;++i)
112           {     
113             ll a=i;
114             ll b=i-n;
115             ll c=(t+n+m-i-i);
116             if(c%2!=0)continue;c/=2ll;
117             ll d=t-a-b-c;
118             ans[k]=(ans[k]+lus(t,a,mod)*lus(t-a,b,mod)%mod*lus(t-a-b,c,mod)%mod+mod)%mod;
119           }
120      }
121      CRT();
122 }

View Code