题解：P13473 [GCJ 2008 #3] Endless Knight

· · 题解

第一次用 lucas，第一次知道 lucas 中途出现计算 C^n_m(n<m) 直接返回 0 就行。

思路流程

先考虑如何算从一点到另一点的方案数。
假如从这一点到另一点需要下移 1 格右移 2 格的次数 s 步，下移 2 格右移 1 格的次数 t 步。这个是好算的，解一个二元一次方程组就行，方案数就是 C^{a+b}_a=C^{a+b}_b。
注意需要 lucas 计算，不然没法预处理到 10^8。
考虑石头的影响，发现 r\le 10，考虑直接枚举会经过那些石子并减去。
但这个是不对的，因为可能会重复减，于是容斥一下算贡献就行。

时间复杂度：O(\sum 2^r+V)，分别是处理询问的时间与预处理时间，V=10007。由于 V 较大，所以 lucas 的时间看做常数。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define debug(i) cout<<"Cute_MKS "<<i<<' '
#define int long long
#define pii pair<int,int>
#define mkp(a,b) make_pair(a,b)
const int mod=10007;
int T,n,m,r,inv[mod+10],jc[mod+10],ans;
struct sto
{
    int x,y;
    bool operator<(const sto &t)const{return (x^t.x?x<t.x:y<t.y);}
}a[11];
int qp(int b,int p)
{
    if(p==1) return b;
    int g=qp(b,p>>1);
    if(p&1) return g*g%mod*b%mod;
    else return g*g%mod;
}
inline int C(int n,int m){return n>=m?jc[n]*inv[m]%mod*inv[n-m]%mod:0;}
inline int lucas(int n,int m){return C(n%mod,m%mod)*C(n/mod,m/mod)%mod;}
inline int que(int x1,int y1,int x2,int y2)
{
    int x=x2-x1,y=y2-y1; 
    if((x+y)%3) return -1;
    int t=(x+y)/3;
    if(t<0||x<t||y<t) return -1;
    return lucas(t,x-t);
}
inline void init()
{
    jc[0]=inv[0]=1;
    for(int i=1;i<mod;i++) jc[i]=jc[i-1]*i%mod;
    inv[mod-1]=qp(jc[mod-1],mod-2);
    for(int i=mod-2;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
inline void sol(int op)
{
    cin>>n>>m>>r;
    cout<<"Case #"<<op<<": ";
    for(int i=1;i<=r;i++) cin>>a[i].x>>a[i].y;
    sort(a+1,a+r+1);
    ans=que(1,1,n,m);
    if(ans==-1){cout<<"0\n";return ;}
    for(int i=1;i<(1<<r);i++)
    {
        int t=1,s=1,sum=1,tot=0;
        for(int j=1;j<=r;j++) 
        {
            if((i>>(j-1)&1)==0) continue;
            if(que(t,s,a[j].x,a[j].y)==-1){sum=-1;break;}
            sum=sum*que(t,s,a[j].x,a[j].y)%mod;
            t=a[j].x,s=a[j].y;
            tot++;
        }
        if(que(t,s,n,m)==-1||sum==-1) sum=-1;
        else sum=sum*que(t,s,n,m)%mod;
        //debug(op)<<i<<' '<<sum<<' '<<t<<' '<<s<<endl;
        if(sum==-1) continue;
        if(tot&1){ans=(ans-sum+mod)%mod;}
        else ans=(ans+sum)%mod;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    cin>>T;
    for(int i=1;i<=T;i++) sol(i);
}