自动搬运

查看原文

来自洛谷，原作者为

	DerrickLo **

搬运于2025-08-24 22:41:57，当前版本为作者最后更新于2023-09-17 11:37:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

定义 $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)$

$\begin{aligned} &=\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;
}