蓝桥杯官网 试题 PREV-253 历届真题 质数行者【第十一届】【决赛】【研究生组】【C++】【Java】两种解法

#include<cstdio>
#include<cstring>
int p[200],pp=1,upper;
long long C[1500][500],dp[1000][500],dp2[1000];
const long long mod=1000000007;
void makeC()
{
	int i,j;
	for(i=0;i<1500;i++)
		C[i][0]=1;
	for(i=1;i<1500;i++)
		for(j=1;j<500;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
void makeP()
{
	int i,j;
	p[0]=2;
	for(i=3;i<1000;i+=2)
	{
		for(j=3;j*j<=i;j+=2)
			if(i%j==0)break;
		if(j*j>i)p[pp++]=i;
	}
}
long long calc(int r,int c,int w)
{
	int i,j,k,upr=r/2,upc=c/2,upw=w/2;
	long long ans=0;
	memset(dp2,0,sizeof(dp2));
	for(i=0;i<=upr;i++)
		for(j=0;j<=upc;j++)
			dp2[i+j]=(dp2[i+j]+dp[r][i]*dp[c][j]%mod*C[i+j][i]%mod)%mod;
	for(i=0;i<=upr+upc;i++)
		for(k=0;k<=upw;k++)
			ans=(ans+dp2[i]*dp[w][k]%mod*C[i+k][k]%mod)%mod;
	return ans;
}
void makeDP()
{
	int i,j,k;
	dp[0][0]=1;
	for(i=2;i<=upper;i++)
	{
		for(j=0;j<pp;j++)
			if(p[j]>i)break;
			else
			{
				for(k=1;k<=i/2;k++)
					dp[i][k]=(dp[i][k]+dp[i-p[j]][k-1])%mod;
			}
	}
}
int main()
{
	int i,j,k,r1,c1,w1,r2,c2,w2,r,c,w;
	long long ans;
	makeC();makeP();
	scanf("%d%d%d",&r,&c,&w);
	r--;c--;w--;
	scanf("%d%d%d%d%d%d",&r1,&c1,&w1,&r2,&c2,&w2);
	r1--,c1--,w1--,r2--,c2--,w2--;
	upper=r>c?r:c;
	upper=upper>w?upper:w;
	makeDP();
	ans=calc(r,c,w)%mod;
	ans-=calc(r1,c1,w1)*calc(r-r1,c-c1,w-w1)%mod;
	ans-=calc(r2,c2,w2)*calc(r-r2,c-c2,w-w2)%mod;
	if(r1>=r2&&c1>=c2&&w1>=w2)
		ans+=calc(r2,c2,w2)*calc(r1-r2,c1-c2,w1-w2)%mod*calc(r-r1,c-c1,w-w1)%mod;
	else if(r1<=r2&&c1<=c2&&w1<=w2)
		ans+=calc(r1,c1,w1)*calc(r2-r1,c2-c1,w2-w1)%mod*calc(r-r2,c-c2,w-w2)%mod;
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public boolean bushu(int a, List<Integer> list) {
		boolean q = true;
		if (!list.contains(a)) {
			for (int i = 0; i < list.size(); i++) {
				int b = list.get(i);
				if (a % b == 0) {
					q = false;
					break;
				}
			}
		}
		if (q) {
			list.add(a);
		}
		return q;
	}
	public long niyuan(long a, long x,long mod)     //这里边做快速幂边取模
	{
		long ans = 1;
		while(x>0) 
		{
			if((x&1)!=0) 
				ans = (ans * a) %mod;
			a = (a * a) %mod;
			x >>= 1;
		}
		return ans;
	}
	public long all(int x,int y,int z,long[][] dp,long mod,long jiechen[],long niyuan[]) {
		long[] tmp=new long[x+y+z+1];
		long all=0;
		for(int i=1;i<=x;i++) {
			for(int j=1;j<=y;j++) {
				long bs=dp[x][i]*dp[y][j]%mod*jiechen[i+j]%mod*niyuan[i]%mod*niyuan[j]%mod;
				if(bs!=0) {
					tmp[i+j]=(tmp[i+j]+bs)%mod;
					all=all+tmp[i+j];
				}
			}
		}
		long ans=0;
		for(int i=0;i<=z;i++) {
			for(int j=0;j<=x+y;j++) {
				ans=ans+dp[z][i]*tmp[j]%mod*jiechen[i+j]%mod*niyuan[i]%mod*niyuan[j]%mod;
				ans=ans%mod;
			}
		}
		return ans;
	}
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		long[][] dp;
		int xj[][]= new int[2][3];
		int zhishu[]=new int[169];
		long mod=1000000007;
		List<Integer> list = new ArrayList<Integer>();
		Main s=new Main();
		int i1=1;
		for (int i = 2; i < 1000; i++) {
			if (s.bushu(i, list)) {
				zhishu[i1++] = i;
			}
		}
		Scanner in = new Scanner(System.in);
		int x,y,z;
		x = in.nextInt();
		y = in.nextInt();
		z = in.nextInt();
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 3; j++) {
				xj[i][j] = in.nextInt();
			}
		}
		int max=Math.max(x,Math.max(y, z));
		long[] jiechen=new long[max*3+1];
		long[] niyuan=new long[max*3+1];
		jiechen[1]=1;
		jiechen[0]=1;
		niyuan[1]=1;
		niyuan[0]=1;
		for(int i=2;i<max*3+1;i++) {
				jiechen[i]=(jiechen[i-1]*i)%mod;
		}
		for(int i=2;i<max*3+1;i++) {
			niyuan[i]=s.niyuan(jiechen[i],mod-2, mod);
		}
		dp=new long[max+1][max+1];
		dp[1][0]=1;
		for(int i=3;i<=max;i++) {
			for(int j=1;j<=i;j++) {
				for(int k=1;k<=168&&zhishu[k]<i;k++) {
					dp[i][j]=(dp[i][j]+dp[i-zhishu[k]][j-1])%mod;
				}
			}
		}
		long ans=s.all(x, y, z, dp, mod, jiechen,niyuan);
		ans=(ans-s.all(xj[0][0],xj[0][1],xj[0][2],dp, mod, jiechen,niyuan)*s.all(x-xj[0][0]+1, y-xj[0][1]+1, z-xj[0][2]+1, dp, mod, jiechen,niyuan)%mod+mod)%mod;
		ans=(ans-s.all(xj[1][0],xj[1][1],xj[1][2],dp, mod, jiechen,niyuan)*s.all(x-xj[1][0]+1, y-xj[1][1]+1, z-xj[1][2]+1, dp, mod, jiechen,niyuan)%mod+mod)%mod;
		if(xj[0][0]<=xj[1][0]&&xj[0][1]<=xj[1][1]&&xj[0][2]<=xj[1][2]) {
			ans=(ans+s.all(xj[0][0], xj[0][1],xj[0][2], dp, mod, jiechen,niyuan)*s.all(xj[1][0]-xj[0][0]+1, xj[1][1]-xj[0][1]+1,xj[1][2]-xj[0][2]+1, dp, mod, jiechen,niyuan)%mod*s.all(x-xj[1][0]+1, y-xj[1][1]+1,z-xj[1][2]+1, dp, mod, jiechen,niyuan)%mod)%mod;
		}
		if(xj[0][0]>=xj[1][0]&&xj[0][1]>=xj[1][1]&&xj[0][2]>=xj[1][2]) {
			ans=(ans+s.all(xj[1][0], xj[1][1],xj[1][2], dp, mod, jiechen,niyuan)*s.all(xj[0][0]-xj[1][0]+1, xj[0][1]-xj[1][1]+1,xj[0][2]-xj[1][2]+1, dp, mod, jiechen,niyuan)%mod*s.all(x-xj[0][0]+1, y-xj[0][1]+1,z-xj[0][2]+1, dp, mod, jiechen,niyuan)%mod)%mod;
		}
		System.out.println(ans);
	}
}