P8737 题解

· · 题解

定义 path(x,y,z) 表示 从 (0,0,0) 走到 (x,y,z) 的方案数。

显然的经过容斥得到，若 r1\le r2,c1\le c2,h1\le h2，则 ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1,m-c1,w-h1)-path(r2,c2,h2)\times path(n-r2,m-c2,w-h2)+path(r1,c1,h1)\times path(r2-r1,c2-c1,h2-h1)\times path(n-r2,m-c2,w-h2)

若 r1\ge r2,c1\ge c2,h1\ge h2 同理。

否则， ans=path(n,m,w)-path(r1,c1,h1)\times path(n-r1,m-c1,w-h1)-path(r2,c2,h2)\times path(n-r2,m-c2,w-h2)

那我们可以定义 f(x,a) 表示用 a 个质数走到 x 的方案数，集合 P 表示全体素数。

那我们就可以得到 f(x,a)=\displaystyle{\sum_{b\in P,b\le x}f(x-b,a-1)}。

则 \space path(x,y,z)

&=\displaystyle{\sum_{i\le x,j\le y,k\le z}C_{i+j+k}^i\times C_{j+k}^{j}\times f(x,i)\times f(y,j) \times f(z,k)}\\ &=\displaystyle{\sum_{i\le x,j\le y,k\le z}\frac{(i+j+k)!}{i!\times(j+k)!}\times\frac{(j+k)!}{j!\times k!}\times f(x,i)\times f(y,j) \times f(z,k)}\\ &=\displaystyle{\sum_{i\le x,j\le y,k\le z}(i+j+k)!\space\times\frac{f(x,i)}{i!}\times\frac{f(y,j)}{j!}\times\frac{f(z,k)}{k!}}\\ &=\displaystyle{\sum_{l\le x+y,i+j=l}\frac{f(x,i)}{i!}\times\frac{f(y,j)}{j!}\space\sum_{k\le z}(l+k)!\space\times \frac{f(z,k)}{k!}} \end{aligned}

复杂度为 O(n^2)。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
int n,m,w,r1,r2,c1,c2,h1,h2,prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,10000};
int f[1005][1005],C[3005][3005],fac[3005],inv[3005];
int path(int x,int y,int z){
    int ans=0;
    for(int l=0;l<=x+y;l++){
        int aa=0,bb=0;
        for(int i=0;i<=l;i++)if(i<=x&&l-i<=y){
            aa+=f[x][i]*inv[i]%mod*f[y][l-i]%mod*inv[l-i]%mod;
        }
        for(int k=0;k<=z;k++)bb+=fac[l+k]*f[z][k]%mod*inv[k]%mod;
        aa%=mod,bb%=mod;
        ans+=aa*bb%mod;
    }
    return ans%mod;
}
int ksm(int x,int y){
    int res=1;
    while(y){
        if(y&1)res=res*x%mod;
        x=x*x%mod;
        y>>=1; 
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    f[0][0]=1;
    for(int i=1;i<=1000;i++)for(int j=1;j<=i/2;j++){
        for(int k=0;;k++){
            if(prime[k]>i)break;
            f[i][j]+=f[i-prime[k]][j-1];
            f[i][j]%=mod;
        }
    } 
    fac[0]=1;
    for(int i=1;i<=3000;i++)fac[i]=fac[i-1]*i%mod;
    inv[3000]=ksm(fac[3000],mod-2);
    for(int i=2999;~i;i--)inv[i]=inv[i+1]*(i+1)%mod; 
    cin>>n>>m>>w>>r1>>c1>>h1>>r2>>c2>>h2;
    n--,m--,w--,r1--,c1--,h1--,r2--,c2--,h2--;
    if(r1>=r2&&c1>=c2&&h1>=h2){
        swap(r1,r2);
        swap(c1,c2);
        swap(h1,h2);
    }
    if(r1<=r2&&c1<=c2&&h1<=h2){
        int ans=(path(n,m,w)-path(r1,c1,h1)*path(n-r1,m-c1,w-h1)%mod-path(r2,c2,h2)*path(n-r2,m-c2,w-h2)%mod+path(r1,c1,h1)*path(r2-r1,c2-c1,h2-h1)%mod*path(n-r2,m-c2,w-h2)%mod+3ll*mod)%mod;
        cout<<ans;
        return 0;
    }
    int ans=(path(n,m,w)-path(r1,c1,h1)*path(n-r1,m-c1,w-h1)%mod-path(r2,c2,h2)*path(n-r2,m-c2,w-h2)%mod+3ll*mod)%mod;
    cout<<ans;
    return 0;
}