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

· · 题解

分析

跳马问题，设横坐标偏移量为 k，纵坐标偏移量为 l，横着跳 x 次，竖着跳 y 次，容易解方程得 x=(2k-l) \div 3，y=2k-x。那么总方案数就是 \dbinom{x+y}{x}。

但是题目还给了一些限制，有一些点不能走。由于这些点非常少，于是我们考虑直接枚举后容斥，选了奇数个合法的点就减去贡献，选了偶数个合法的点就加上贡献，算贡献的方法同上。由于数据范围偏大，所以可以用 \text{Lucas} 定理减少预处理范围，时间复杂度 O(2^RR \log n)。

代码

#include <bits/stdc++.h>
#define M 15
#define N 1000005
#define x first
#define y second
#define p 10007
#define _bpc __builtin_popcount
using namespace std;
int T,n,m,k,sum,x,y,fc[N],cnt;
pair<int,int> a[M];
vector<pair<int,int>> tmp;
inline int qpow(int x,int y){
    int sum=1;
    while(y){
        if(y&1) sum=sum*x%p;
        x=x*x%p;
        y>>=1;
    }
    return sum;
}
inline int mod(int x){
    if(x<0) return x+p;
    if(x>=p) return x-p;
    return x;
}
inline int zh(int n,int m){
    if(m>n) return 0;
    return (fc[n]*qpow(fc[m],p-2))%p*qpow(fc[n-m],p-2)%p;
}
int lucas(int n,int m){
    if(!m) return 1;
    return lucas(n/p,m/p)*zh(n%p,m%p)%p;
}//lucas
int main(){
    scanf("%d",&T);
    fc[0]=fc[1]=1;
    for(int i=2;i<=p+2;i++) fc[i]=fc[i-1]*i%p;//预处理阶乘
    for(int t=1;t<=T;t++){
        sum=0;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=k;i++) scanf("%d%d",&a[i].x,&a[i].y);
        sort(a+1,a+1+k);
        for(int i=0;i<(1<<k);i++){
            cnt=1;
            tmp.clear();
            tmp.push_back({1,1});
            for(int j=0;j<k;j++) if((1<<j)&i) tmp.push_back(a[j+1]);
            tmp.push_back({n,m});
            for(int j=1;j<(int)tmp.size();j++){
                int k=tmp[j].x-tmp[j-1].x,l=tmp[j].y-tmp[j-1].y;
                if(k<0||l<0||((k<<1)-l)%3||(k<<1)-l<0) goto lk;
                x=((k<<1)-l)/3,y=k-(x<<1);
                if(y<0) goto lk;
                cnt=cnt*lucas(x+y,x)%p;//算贡献
            }
            sum=mod(sum+((_bpc(i)&1)?-1:1)*cnt); 
            lk:
        }//枚举
        printf("Case #%d: %d\n",t,sum);
    }
    return 0;
}