P8737 [蓝桥杯 2020 国 B] 质数行者

首先，注意到方案数只与3种步数有关，与在哪出发哪结束无关，于是考虑如何求出\(sol(n,m,w)\)。
三种走法可以相互独立，最后的答案只与他们的步数有关，所以需要一个\(f[i][j]\)表示用\(j\)步走到\(i\)的方案数，简单DP可以求出，复杂度为\(O(n^2k)\)，其中k为质数个数，最多有200个，可以接受。
下面就到了结合起来的时候，当三种步数分别为\(a,b,c\)时，需要确定他们的顺序，也就是组合情况有多少种，可以使用两个组合数相乘，种数为：\(C(a+b+c,a)* C(b+c,b)\)，那么此时方案数就是:\(C(a+b+c,a)* C(b+c,b)* f[n][a]* f[m][b]* f[w][c]\)，一个\(O(n^3)\)才可以解决，显然不可以接受。
发现将组合数拆开：\(C(a+b+c,a)* C(b+c,b)=\frac {(a+b+c)!} {a!(b+c)!}* \frac {(b+c)!} {b!c!}=\frac {(a+b+c)!} {a!b!c!}\)
那么此时方案数可以写成\((a+b+c)! \frac {f[n][a]} {a!}* \frac {f[m][b]} {b!}* \frac{f[w][c]} {c!}\)，成功得把他们独立了出来，能做到只与总步数有关了。
对于以上的写法，最终的答案为\(\sum_{a=1}^n\sum_{b=1}^m\sum_{c=1}^w(a+b+c)! \frac {f[n][a]} {a!}* \frac {f[m][b]} {b!}* \frac{f[w][c]} {c!}\)。
不妨先处理只有\(a\)与\(b\)的情况，把\(a+b\)的所有情况提前求出：\(\sum_{a=1}^n\sum_{b=1}^mg[a+b]=\frac {f[n][a]} {a!}* \frac {f[m][b]} {b!}\)
那么最后再接着枚举\(c\)，直接枚举\(l=a+b\)即可：\(sol(n,m,w)=\sum_{l=0}^{n+m}\sum_{c=1}^w\frac{f[w][c]} {c!}* g[a+b]* (l+c)!\)。
见到有两个限制点，考虑一个显然的容斥，最后答案即为总的方案数-过点1-过点2+同时过点1和点2（可能没有）。
对于过某点的方案，直接分成两段路再把方案数相乘。
最后注意把所有输入的数据先减去1，意味到(1,1,1)的距离。

代码：

#include<algorithm>
#include<stdio.h>
#define ll long long
using namespace std;
int n,m,w;
int r1,c1,h1,r2,c2,h2;
int bj[1005],pri[1005],n1;
ll mod=1e9+7;
void GetPrime() {
	for(int i=2;i<1000;i++) {
		if(!bj[i]) pri[++n1]=i;
		for(int j=1;j<=n1 && i*pri[j]<1000;j++) {
			bj[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
ll jc[3005];
void Getjc() {
	jc[0]=1;
	for(int i=1;i<=3000;i++) {
		jc[i]=jc[i-1]*i%mod;
	}
}
ll fp(ll x,ll y){
	ll ans=1;
	for(;y;y>>=1) {
		if(y&1) ans=ans*x%mod;
		x=x*x%mod;
	}
	return ans;
}
ll f[1005][1005];
void DP() {
	f[0][0]=1;
	for(int i=1;i<=1000;i++) {
		for(int j=1;j<=500;j++) {
			for(int k=1;k<=n1;k++) {
				if(pri[k]>i) break;
				f[i][j]=(f[i][j]+f[i-pri[k]][j-1])%mod;
			}
		}
	}
	for(int j=0;j<=500;j++) {
		ll num=fp(jc[j],mod-2);
		for(int i=1;i<=1000;i++) {
			f[i][j]=f[i][j]*num%mod;
		}
	}	
//	for(int i=0;i<=1000;i++) {
//		for(int j=0;j<=500;j++) {
//			printf("%lld ",f[i][j]);
//		}
//		printf("\n");
//	}
}
ll g[2005];
ll sol(int a,int b,int c) {
	ll ans=0;
	for(int i=0;i<=1000;i++) g[i]=0;
	for(int i=0;i<=500;i++) {
		for(int j=0;j<=500;j++) {
			g[i+j]=(g[i+j]+f[a][i]*f[b][j]%mod)%mod;
		}
	}
	for(int i=0;i<=1000;i++) {
//		printf("%lld\n",g[i]);
		for(int k=0;k<=500;k++) {
			ll num1=g[i]*f[c][k]%mod*jc[i+k]%mod;
			ans=(ans+num1)%mod;
		}
	}
//	printf("%lld %lld %lld %lld\n",a,b,c,ans);
	return ans;
}
int main() {
//	freopen("game10.in","r",stdin);
//	freopen("game10.out","w",stdout);
	scanf("%d%d%d",&n,&m,&w); n--,m--,w--;
	scanf("%d%d%d%d%d%d",&r1,&c1,&h1,&r2,&c2,&h2); r1--,c1--,h1--,r2--,c2--,h2--;
	GetPrime();
	Getjc();
	DP();
//	ll ans=sol(n,m,w); ll num1=0,num2=0,num3=0;
//	num2=sol(r1,c1,h1)*sol(n-r1,m-c1,w-h1)%mod;
//	num3=sol(r2,c2,h2)*sol(n-r2,m-c2,w-h2)%mod;
//	if(r1<=r2 && c1<=c2 && h1<=h2) num3=sol(r1,c1,h1)*sol(r2-r1,c2-c1,h2-h1)%mod*sol(n-r2,m-c2,w-h2)%mod;
//	else if(r1>=r2 && c1>=r2 && h1>=h2) num3=sol(r2,c2,h2)*sol(r1-r2,c1-c2,h1-h2)%mod*sol(n-r1,m-c1,w-h1)%mod;
//	ans=ans-num1-num2+num3;

	
	ll ans=sol(n,m,w)-sol(r1,c1,h1)*sol(n-r1,m-c1,w-h1)%mod-sol(r2,c2,h2)*sol(n-r2,m-c2,w-h2)%mod;
	if(r1<=r2&&c1<=c2&&h1<=h2)ans+=sol(r1,c1,h1)*sol(r2-r1,c2-c1,h2-h1)%mod*sol(n-r2,m-c2,w-h2)%mod;
	if(r2<=r1&&c2<=c1&&h2<=h1)ans+=sol(r2,c2,h2)*sol(r1-r2,c1-c2,h1-h2)%mod*sol(n-r1,m-c1,w-h1)%mod;
//	printf("%lld %lld %lld %lld\n",ans,num1,num2,num3);
	ans=(ans%mod+mod)%mod;
	printf("%lld",ans);
	return 0;
}