BZOJ3782 上学路线

BZOJ3782 上学路线

1 题外话

奇怪的DP增加了

2 sol

直接删去坏点的难度有点大（暴力\(O(nm)\) ），考虑DP

设\(f[i]\) 表示从\((0,0)\) 走到第\(i\) 个坏点，中途不经过其他坏点的方案数

求某个\(f[x]\) 时，我们枚举它第一个经过的坏点\(i\) ，那么他的贡献是\(f[i]\times C^{|x_x-x_i|}_{|x_x-x_i|+|y_x-y_i|}\)

后面组合数的意义为从\(i\) 走到\(x\) 的方案数（不考虑是否经过其他坏点）

那么\(f[x]=\sum_{i\in T} f[i]\times C^{|x_x-i_x|}_{|x_x-i_x|+|x_y-i_y|}\)

初始化时将\((n,m)\) 放入坏点，将每个坏点排序求出$f$即可

3 code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=210;
const int M=1000010;

inline void read(int &x) {
    x=0;
    int f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if (ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    x*=f;
}

struct point {
    long long x;
    long long y;
};

point p[N];
long long n,m,t,P;

inline bool comp(const point &x,const point &y) {
    return x.x==y.x?x.y<y.y:x.x<y.x;
}

int pri[5];
int con;
long long fac[5][M],fac_inv[5][M],inv[5][M];

inline void pre() {
    long long x=P;
    for(int i=2;i*i<=x;i++) {
        while (x%i==0) {
            pri[++con]=i;
            x/=i;
        }
    }
    if (x!=1) {
        pri[++con]=x;
    }
    for(int i=1;i<=con;i++) {
        fac[i][0]=fac[i][1]=fac_inv[i][0]=fac_inv[i][1]=inv[i][0]=inv[i][1]=1;
        int mod=pri[i];
        for(int j=2;j<pri[i];j++) {
            fac[i][j]=1ll*fac[i][j-1]*j%mod;
            inv[i][j]=1ll*(mod-mod/j)*inv[i][mod%j]%mod;
            fac_inv[i][j]=1ll*fac_inv[i][j-1]*inv[i][j]%mod;
        }
    }
}

long long lucas(long long n,long long m,int pid) {
    if (m>n) {
        return 0;
    }
    if (n<pri[pid]&&m<pri[pid]) {
        return 1ll*fac[pid][n]*fac_inv[pid][m]%pri[pid]*fac_inv[pid][n-m]%pri[pid];
    }
    return 1ll*lucas(n%pri[pid],m%pri[pid],pid)*lucas(n/pri[pid],m/pri[pid],pid)%pri[pid];
}

long long C(long long n,long long m) {
    if (m>n) {
        return 0;
    }
    long long res=0;
    for(int i=1;i<=con;i++) {
        res=(res+1ll*lucas(n,m,i)*(P/pri[i])%P*inv[i][(P/pri[i])%pri[i]]%P)%P;
    }
    return res;
}

long long f[N];

int main() {
    scanf("%lld%lld%lld%lld",&n,&m,&t,&P);
    pre();
    for(int i=1;i<=t;i++) {
        scanf("%lld%lld",&p[i].x,&p[i].y);
    }
    t++;
    p[t].x=n,p[t].y=m;
    sort(p+1,p+t+1,comp);
    for(int i=1;i<=t;i++) {
        f[i]=C(0ll+p[i].x+p[i].y,0ll+p[i].x);
        for(int j=1;j<i;j++) {
            if (p[j].x<=p[i].x&&p[j].y<=p[i].y) {
                f[i]=(f[i]-1ll*f[j]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%P)%P;
            }
        }
        f[i]=(f[i]+P)%P;
    }
    printf("%lld\n",f[t]);
    return 0;
}

4 注意

模数不一定是质数，最后要用CRT合并

Author: tt66ea

Created: 2021-08-12 周四 16:18

Validate