题目：https://www.cnblogs.com/Juve/articles/11226266.html
solution：
30%：dp
设dp[k][i][j]表示经过k时间，在(i,j)的方案数
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 #define MAXN 105 6 using namespace std; 7 ll dp[MAXN][MAXN<<1][MAXN<<1],t,n,m,mod; 8 int main(){ 9 scanf("%lld%lld%lld%lld",&t,&mod,&n,&m); 10 if(n<0) n=-n; 11 if(m<0) m=-m; 12 if((t-n-m)&1){ 13 cout<<0<<endl; 14 return 0; 15 } 16 int xkl=105; 17 dp[0][xkl][xkl]=1; 18 for(ll i=1;i<=t;i++){ 19 for(ll j=-t;j<=t;j++){ 20 for(ll k=-t;k<=t;k++){ 21 dp[i][j+xkl][k+xkl]=(dp[i][j+xkl][k+xkl]+dp[i-1][j+xkl][k+1+xkl]+dp[i-1][j+xkl][k-1+xkl]+dp[i-1][j-1+xkl][k+xkl]+dp[i-1][j+1+xkl][k+xkl])%mod; 22 } 23 } 24 } 25 cout<<dp[t][n+xkl][m+xkl]%mod<<endl; 26 return 0; 27 }
它可以走到-t，所以要防爆
正解：（转载Barca）
我们设ri,le,up,down分别为向右左上下走的步数，且总步数为T，
然后我们只要知道，向一个方向走的步数就能得到其他的，但是我们发现光凭一个是求不出的，
我们再转化一下思路，我们设在上下方向走的步数为k,则up+down=k,
然后又因为他最后必须走到(n,m)，所以向上走的步数减去向下走的步数为m,即up-down=m，
同理我们可以求出ri与le的关系，同样是两个方程，
这样我们就可以通过枚举k，来得到向各个方向走的步数，这样就能列出组合数的式子了，即：
ans=
(不知为何我数学公式挂了)
$sum limits_{k=m}^{t-n}C_t^k*C_k^{frac{k-m}{2}}*C_{n-k}^{frac{t-k-n}{2}}$
-------->这有什么错吗？
但你这样也只有60分，因为mod不一定是质数
那我们可以CRT合并
先对mod分解因数，再用lucas求出mod每个因数下的ans，然后发现一个方程组
$egin{cases} x & equiv & ans_1 (mod p_1) \ x & equiv & ans_2 (mod p_2) \ & vdots & \ x & equiv & ans_n (mod p_n) end{cases}$
from Rorschach_XR 为什么今天我Latex挂掉了，rp++14：38它终于好了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
#define MAXN 100005
using namespace std;
ll t,n,m,mod,ans[MAXN];
ll q_pow(ll a,ll b,ll p){
ll res=1;
while(b){
if(b&1) res=(res*a)%p;
a=(a*a)%p;
b>>=1;
}
return res%p;
}
ll tot=0,prime[MAXN];
void divide(ll p){//分解质因数
ll t=(ll)sqrt(p);
for(ll i=2;i<=t;i++){
if(p%i==0){
prime[++tot]=i;
p/=i;
}
}
if(p>1) prime[++tot]=p;
}
ll fac[MAXN];
void get_fac(ll p){
fac[0]=fac[1]=1;
for(ll i=2;i<=t;i++)
fac[i]=fac[i-1]*i%p;
}
ll C(ll n,ll m,ll p){
if(m>n) return 0;
return fac[n]*q_pow(fac[m]*fac[n-m]%p,p-2,p)%p;
}
ll lucas(ll n,ll m,ll p){
if(m==0) return 1;
return C(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
ll CRT(ll ans[]){
ll res=0;
for(ll i=1;i<=tot;i++)
res=(res+mod/prime[i]*ans[i]%mod*q_pow(mod/prime[i],prime[i]-2,prime[i])%mod)%mod;
return res;
}
int main(){
scanf("%lld%lld%lld%lld",&t,&mod,&n,&m);
if(n<0) n=-n;
if(m<0) m=-m;
divide(mod);//分解质因数
for(ll i=1;i<=tot;i++){
get_fac(prime[i]);//mod(prime[i])意义下的fac
for(ll k=n;k<=t-m;k+=2)//步数不能为1
ans[i]=(ans[i]+lucas(t,k,prime[i])*lucas(k,(k-n)/2,prime[i])%mod*lucas(t-k,(t-m-k)/2,prime[i])%mod)%mod;
}
printf("%lld
",CRT(ans)%mod);
return 0;
}