【蓝桥杯 质数行者】

蓝桥杯 质数行者 题目描述

小蓝在玩一个叫质数行者的游戏。

游戏在一个 n×m×w 的立体方格图上进行，从北到南依次标号为第 1 行到
第 n 行，从西到东依次标号为第 1 列到第 m 列，从下到上依次标号为第 1 层到第 w 层。

小蓝要控制自己的角色从第 1 行第 1 列第 1 层移动到第 n 行第 m 列第 w层。

每一步，他可以向东走质数格、向南走质数格或者向上走质数格。

每走到一个位置，小蓝的角色要稍作停留。

在游戏中有两个陷阱，分别为第 r 1 行第 c 1 列第 h 1 层和第 r 2 行第 c 2 列第h2 层。

这两个陷阱的位置可以跨过，但不能停留。

也就是说，小蓝不能控制角色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。

小蓝最近比较清闲，因此他想用不同的走法来完成这个游戏。

所谓两个走法不同，是指小蓝稍作停留的位置集合不同。

请帮小蓝计算一下，他总共有多少种不同的走法。

提示：请注意内存限制，如果你的程序运行时超过内存限制将不得分。

【输入格式】
输入第一行包含两个整数 n, m, w，表示方格图的大小。

第二行包含 6 个整数，r 1 , c 1 , h 1 , r 2 , c 2 , h 2 ，表示陷阱的位置。

【输出格式】
输出一行，包含一个整数，表示走法的数量。

答案可能非常大，请输出答
案除以 1000000007 的余数。

【样例输入】
5 6 1
3 4 1 1 2 1
【样例输出】
11

解题思路

如果考试遇上这题估计可以直接打个暴力走了，正解我想了一个上午才想出来（太菜了）。

题目要求的是从(1,1,1)走到(n,m,w)且不经过两个陷阱的点的方案总数。

首先我们不考虑陷阱的情况，然后在所有的答案中减去陷阱点的情况就行了。

考虑直接从(1,1,1)到(n,m,w)的情况。

我们可以把这个三维的过程分成三个一维的质数分解方案，然后再将三个一维的方案合并成一个三维的方案数就行了。

考虑一维的情况从1到n只能走质数步，一共有多少方案数？
如果只求这个答案一维dp就够了，dp[i]表示到达i时一共有多少种方案数。

然而我们还要考虑合并的情况，所以这里我们设计的状态为dp[i][j]表示走到i时，一共走了j步的方案总数。

转移方程为：dp[i][j]+=dp[i-k][j-1] //k为某个质数值

一维的情况解决了，怎么合并为二维呢？当我们确定了在x轴上走的每一步的顺序，加入y轴的情况就相当于我往x轴的步骤中插入我在y轴走的步数。

比如：当n=5，m=6时，我要在x轴上走4步，在y轴上走5步。

那么在x轴走的方案就只有 2 2一种，y轴的方案有(5),(2,3),(3,2)三种。

把y轴加入进x轴，就相当于是把y中的数字打包插入x的空隙之中。

也相当于是把x维走的情况和y维走的情况作一个排列然后再消去原本已经确定的步骤的影响。

设X[i]表示x维度到达n，且走了i部的方案数，Y[i]表示y维度到达m，且走了i步的方案数，XY[i]表示X微到达n，Y微到达m时，一共走了i部的方案数。

可以知道的是X[i]=dp[n][i],Y[i]=dp[m][i]（dp含义见上）。

XY[i+j]+=X[i] * Y[j] * (i+j)! /(i!)/(j!)
//x维走了i部的方案数为X[i]，y维走了j步的方案数为Y[j]，两个维度一共走了(i+j)步，排列就是(i+j)!，但是这些步的顺序在每个维度内是固定的，所以还要除以i！和j！

好！现在求出来了到(n,m,w)的方案数，那么最后答案就是【(1,1,1)到(n,m,w)的方案数】-【(1,1,1)到(R1,C1,H1)的方案数】-【(1,1,1)到(R2,C2,H2)的方案数】+【(R1,C1,H1)到(R2,C2,H2)的方案数】。

简单的容斥一下就好了。

这样我们就合并了两个维度，那么再合并一个维度就跟上面的原理是一样的了。

最后我们计算一下时间复杂度：计算dp时差不多是n2的，计算阶乘的时候，由于还要求乘法逆元，所以是n2logn的（可以更快，但不想改了），所以最后时间复杂度为n2logn的。

上代码

#include
#include
#include
#include
using namespace std;
#define mod 1000000007
#define N 2005
#define ll long long
ll vis[N];
ll prime[N];
ll jie[N],S[N][N];
ll tot;
ll inv(ll x){
	ll p=mod-2;
	ll y=1;
	while(p){
		if(p&1){
			y=(y*x)%mod;
		}
		x=(x*x)%mod;
		p>>=1;
	}
	return y;
}
ll dp[N][N];
void preparation(ll n,ll m,ll w){
	if(n<1||m<1||w<1)return ;
	int nm=max(n+m,w);
	jie[0]=1;
	for(int i=1;i<=nm;i++)jie[i]=(jie[i-1]*i)%mod;
	for(int i=0;i<=nm;i++){
		for(ll j=0;j<=i;j++){
			S[i][j]=((jie[i+j]*inv(jie[i]))%mod*inv(jie[j]))%mod;
			S[j][i]=S[i][j];
		}
	}
	int mm=max(max(n,m),w);
	for(int i=2;i<=mm;i++){
		if(!vis[i])prime[++tot]=i;
		for(ll j=1;prime[j]*i<=mm&&j<=tot;j++){
			vis[prime[j]*i]=1;
		}
	}dp[1][0]=1;
	for(int i=2;i<=mm;i++){
		for(int k=1;k<=(i-1)/2;k++){
			for(int j=1;j<=tot&&prime[j]<i;j++){
				dp[i][k]=(dp[i][k]+dp[i-prime[j]][k-1])%mod;
			}
		}
	}
}
ll X[N],Y[N],Z[N],XY[N*2],XYZ[N*3];
ll find(ll x,ll y,ll z){
	ll totx=(x-1)/2,toty=(y-1)/2,totz=(z-1)/2,ans=0;
	for(int i=0;i<=totx;i++){
		X[i]=dp[x][i];
	}
	for(int i=0;i<=toty;i++){
		Y[i]=dp[y][i];

	}
	for(int i=0;i<=totz;i++){
		Z[i]=dp[z][i];
	}
	for(int i=0;i<=totx+toty;i++)XY[i]=0;
	for(int i=0;i<=totx;i++){
		for(int j=0;j<=toty;j++){
			XY[i+j]+=((X[i]*Y[j])%mod*S[i][j])%mod;
			XY[i+j]=XY[i+j]%mod;
		}
	}
	for(int i=0;i<=totx+toty+totz;i++)XYZ[i]=0;
	for(int i=0;i<=totx+toty;i++){
		for(ll j=0;j<=totz;j++){
			XYZ[i+j]+=(((XY[i]*Z[j])%mod)*S[i][j])%mod;
			XYZ[i+j]=XYZ[i+j]%mod;
		}
	}
	for(ll i=0;i<=totx+toty+totz;i++)ans=(ans+XYZ[i])%mod;
	return ans;
}
ll n,m,w,R1,R2,C1,C2,H1,H2;
int main(){
	scanf("%lld%lld%lld",&n,&m,&w);
	scanf("%lld%lld%lld%lld%lld%lld",&R1,&C1,&H1,&R2,&C2,&H2);
	if(R1>R2||C1>C2||H1>H2){
		swap(R1,R2);swap(C1,C2);swap(H1,H2);
	}
	preparation(n,m,w);
	ll ans1=find(n,m,w);
	ll ans2=(find(R1,C1,H1)*find(n-R1+1,m-C1+1,w-H1+1))%mod;
	ll ans3=(find(R2,C2,H2)*find(n-R2+1,m-C2+1,w-H2+1))%mod;
	ll ans4=(((find(R1,C1,H1)*find(R2-R1+1,C2-C1+1,H2-H1+1))%mod)*find(n-R2+1,m-C2+1,w-H2+1))%mod;
	printf("%lld %lld %lld %lld\n",ans1,ans2,ans3,ans4); 
	printf("%lld\n",(ans1-ans2-ans3+ans4+mod)%mod);
}