mxqz,已过,但想知道为什么程序中某3行是十分必要的。
查看原帖
mxqz,已过,但想知道为什么程序中某3行是十分必要的。
600914
sszcdjr楼主2022/8/7 21:24

过是过了,但是我想问一件事,为什么当我将 757775\sim77 行隐藏掉就会 WA\texttt{WA} 掉呢?个人感觉在 919391\sim93 行已经判断了减去只被自己包含的数量,再怎么说也该 TLE\texttt{TLE} 啊。

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
int fac[1000005],inv[1000005];
void init(){
	fac[0]=1;
	for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=qp(fac[1000000],mod-2);
	for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int i,int j){
	if(i<0||j<0||i<j) return 0;
	return fac[i]*inv[i-j]%mod*inv[j]%mod;
}
int count(int i){
	int ans=0;
	while(i){
		ans+=(i%2);
		i>>=1;
	}
	return ans;
}
struct node{
	int x,y,z,cx,cy,cz;
}a[10005];
bool cmp(node A,node B){
	if(A.cx!=B.cx) return A.cx<B.cx;
	if(A.cy!=B.cy) return A.cy<B.cy;
	return A.cz<B.cz;
}
int dp[65][65][65],sol[10005];
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	init();
	dp[0][0][0]=1;
	for(int i=0;i<=64;i++){
		for(int j=0;j<=64;j++){
			for(int k=0;k<=64;k++){
				for(int l=i+1;l<=64;l++){
					dp[l][j][k]=(dp[l][j][k]+dp[i][j][k]*C(l,i))%mod;
				}
				for(int l=j+1;l<=64;l++){
					dp[i][l][k]=(dp[i][l][k]+dp[i][j][k]*C(l,j))%mod;
				}
				for(int l=k+1;l<=64;l++){
					dp[i][j][l]=(dp[i][j][l]+dp[i][j][k]*C(l,k))%mod;
				}
			}
		}
	}
	int ex,ey,ez;
	cin>>ex>>ey>>ez;
	int n,m=1;
	cin>>n;
	a[1].x=ex,a[1].y=ey,a[1].z=ez;
	for(int i=1;i<=n;i++){
		int X,Y,Z;
		cin>>X>>Y>>Z;
		if(X>ex||Y>ey||Z>ez){
			continue;
		}
		if((X&a[1].x)!=X) continue;
		if((Y&a[1].y)!=Y) continue;
		if((Z&a[1].z)!=Z) continue;
		m++;
		a[m].x=X,a[m].y=Y,a[m].z=Z;
	}
	for(int i=1;i<=m;i++){
		a[i].cx=count(a[i].x);
		a[i].cy=count(a[i].y);
		a[i].cz=count(a[i].z);
	}
	sort(a+1,a+m+1,cmp);
//	if(m>1) return 0;
	for(int i=1;i<=m;i++){
		sol[i]=dp[a[i].cx][a[i].cy][a[i].cz];
		for(int j=1;j<i;j++){
			if(((a[j].x&a[i].x)==a[j].x))
			if(((a[j].y&a[i].y)==a[j].y))
			if(((a[j].z&a[i].z)==a[j].z))
			sol[i]=(sol[i]+mod-sol[j]*dp[a[i].cx-a[j].cx][a[i].cy-a[j].cy][a[i].cz-a[j].cz]%mod)%mod;
		}
	}
	cout<<sol[m];
	return 0;
}

2022/8/7 21:24
加载中...