QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#506519 | #9112. Zayin and Raffle | Cheek_support | RE | 0ms | 0kb | C++14 | 2.6kb | 2024-08-05 18:45:11 | 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 ...