过是过了,但是我想问一件事,为什么当我将 75∼77 行隐藏掉就会 WA 掉呢?个人感觉在 91∼93 行已经判断了减去只被自己包含的数量,再怎么说也该 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;
}