QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#506519#9112. Zayin and RaffleCheek_supportRE 0ms0kbC++142.6kb2024-08-05 18:45:112024-08-05 18:45:11

Judging History

你现在查看的是最新测评结果

  • [2024-08-05 18:45:11]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-08-05 18:45:11]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define mod 1000000007
using namespace std;
int read(){
	int num=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+(c^48);c=getchar();}
	return num*f;
}
template<typename T> void Write(T x){
	if(x>9)Write(x/10);
	putchar(x%10+'0');
}
template<typename T> void write(T x){
	if(x<0){x=-x;putchar('-');}
	Write(x);putchar('\n');
}
template<typename T> T inc(T x,T y){return (x+y>=mod)?(x+y-mod):(x+y);}
template<typename T> T dec(T x,T y){return (x-y<0)?(x-y+mod):(x-y);}
const int N=100000+10,M=16,K=8;
const int TOT=1000000000,INV=857142863;
int a[N][K+5];
int b[K+5];

int poww(int n,int m){
	int ret=1;int temp=n;int tmp=m;
	while(tmp){
		if(tmp&1)ret=(1ll*ret*temp)%mod;
		temp=(1ll*temp*temp)%mod;
		tmp>>=1;
	}
	return ret;
}


int F[1<<M],G[1<<M];
int H[1<<K],Num[1<<K];
bool vis[M+5];
int num[K+5];
vector<int>p[1<<M];
int main(){
	int n=read(),m=read(),k=read();
	rep(i,1,k){
		b[i]=read();
	}
	rep(i,1,n){
		rep(j,1,k)a[i][j]=read();
		int tmp=0;
		rep(j,1,k){
			if(!a[i][j])continue;
			tmp|=(1<<(a[i][j]-1));
		}
		p[tmp].push_back(i);
	}
	
	/*rep(i,0,(1<<m)-1){
		rep(j,0,m-1)vis[j+1]=((i>>j)&1);
		int tmp=1;
		rep(j,1,n){
			int cnt=0;
			rep(l,1,k)cnt+=(vis[a[j][l]])*b[l];
			tmp=(1ll*tmp*(TOT-cnt)%mod*INV)%mod;
		}
		G[i]=tmp;
	}*/
	rep(i,0,(1<<m)-1)G[i]=1;
	rep(i,0,(1<<m)-1){
		if(!p[i].size())continue;
		int len=0;
		rep(j,0,m-1){
			if(!((i>>j)&1))continue;
			num[++len]=j+1;
		}
		
		rep(j,1,(1<<len)-1)H[j]=1;
		
		H[0]=1;
		rep(j,1,(1<<len)-1){
			H[j]=1;
			Num[j]=0;
				
			rep(pos,1,len){
				vis[num[pos]]=((j>>(pos-1))&1);
				Num[j]|=vis[num[pos]]*(1<<(num[pos]-1));;
			}
				
			for(auto x:p[i]){	
				int cnt=0;
				rep(pos,1,k)cnt+=(!vis[a[x][pos]])*b[pos];
			
				H[j]=(1ll*H[j]*cnt%mod*INV)%mod;
			}
		}
		
		rep(pos,0,len-1){
			rep(j,0,(1<<len)-1){
				if(!(j&(1<<pos)))continue;
				if(!H[j^(1<<pos)])continue;
				H[j]=(1ll*H[j]*poww(H[j^(1<<pos)],mod-2))%mod;
			}
		}
		rep(j,0,(1<<len)-1)G[Num[j]]=(1ll*G[Num[j]]*H[j])%mod;
	}
	rep(i,0,m-1){
		rep(j,0,(1<<m)-1){
			if(!(j&(1<<i)))continue;
			G[j]=(1ll*G[j]*G[j^(1<<i)])%mod;
		}
	}
	
	rep(i,0,(1<<m)-1)F[i]=G[i^((1<<m)-1)];
	rep(i,0,m-1){
		rep(j,0,(1<<m)-1){
			if(!(j&(1<<i)))continue;
			F[j]=dec(F[j],F[j^(1<<i)]);
		}
	}
	rep(i,0,(1<<m)-1){
		write(F[i]);
	}
	return 0;
}
/*
2 2 2
400000000 600000000
1 0
2 1

6 3 3
500000000 300000000 200000000
1 0 3
2 1 3
3 1 2
0 0 0
2 3 3
1 3 0

*/

详细

Test #1:

score: 0
Runtime Error

input:

100000 16 8
14837 17850 15180 22820 26722 4874 4574 999893143
15006 45877 19815 26604 6797 0 25449 15769
26395 0 495 64118 18133 47822 5863 39708
56443 188 55498 14620 36924 25033 0 36587
55421 21544 59411 3280 55222 0 51028 55986
42323 41153 53683 16144 53188 15759 0 28378
63709 51900 0 18592 1916 ...

output:


result: