QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #504963 | #9112. Zayin and Raffle | WorldFinalEscaped# | AC ✓ | 3643ms | 8408kb | C++14 | 2.1kb | 2024-08-04 17:54:35 | 2024-08-04 17:54:35 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e9+7;
int n,m,k,InvI,T[N],InvT[N],B[N],S[N],tmp[N],p[N],a[N],ansz[N],ans[N],res[N];
long long cntz[N],resz[N];
inline int fastpow(int x, int y){
int z=1;
for (; y; y>>=1,x=1ll*x*x%mod)
if (y&1) z=1ll*z*x%mod;
return z;
}
int main(){
scanf("%d%d%d",&n,&m,&k); InvI=fastpow(1000000000,mod-2);
for (int i=1; i<=k; i++) scanf("%d",&p[i]),p[i]=1ll*p[i]*InvI%mod;
for (int i=1; i<(1<<k); i++){
B[i]=__builtin_popcount(i);
T[i]=(T[i^(i&-i)]+p[(int)log2(i&-i)+1])%mod;
InvT[i]=fastpow(T[i],mod-2);
}
for (int i=0; i<(1<<m); i++) tmp[i]=ans[i]=res[i]=1;
for (; n; n--){
for (int j=1; j<=k; j++) scanf("%d",&a[j]);
for (int j=1; j<(1<<k); j++) S[j]=S[j^(j&-j)]|a[(int)log2(j&-j)+1];
for (int i=0; i<(1<<k); i++){
for (int j=i; j; j=(j-1)&i)
if (B[i]%2==B[j]%2){
if (T[j]) tmp[S[i]]=1ll*tmp[S[i]]*T[j]%mod;
else cntz[S[i]]++;
} else {
if (T[j]) tmp[S[i]]=1ll*tmp[S[i]]*InvT[j]%mod;
else cntz[S[i]]--;
}
if (B[i]%2==B[0]%2){
if (T[0]) tmp[S[i]]=1ll*tmp[S[i]]*T[0]%mod;
else cntz[S[i]]++;
} else {
if (T[0]) tmp[S[i]]=1ll*tmp[S[i]]*InvT[0]%mod;
else cntz[S[i]]--;
}
}
for (int j=1; j<(1<<k); j++) S[j]=0;
}
for (int i=0; i<(1<<m); i++){
for (int j=i; j; j=(j-1)&i)
if ((i&j)==j){
res[i]=1ll*res[i]*tmp[j]%mod;
resz[i]+=cntz[j];
}
res[i]=1ll*res[i]*tmp[0]%mod;
resz[i]+=cntz[0];
}
for (int i=0; i<(1<<m); i++){
ans[i]=resz[i]?0:res[i];
for (int j=i; j; j=(j-1)&i)
if (i!=j) ans[i]=(ans[i]+mod-ans[j])%mod;
if (i!=0) ans[i]=(ans[i]+mod-ans[0])%mod;
}
for (int i=0; i<(1<<m); i++) printf("%d\n",ansz[i]?0:ans[i]);
}
/*
2 2 2
400000000 600000000
1 0
2 1
*/
詳細信息
Test #1:
score: 100
Accepted
time: 3636ms
memory: 7100kb
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:
105532035 709209358 742395693 674439956 829972983 268323536 719611672 686061778 667639364 160529448 284006277 426487374 560675131 711436547 151999054 83251935 704825434 897033675 576472928 375148047 149541480 425599467 975644650 421255417 560324160 127313981 870564235 441704026 939196723 26709030 47...
result:
ok 65536 lines
Test #2:
score: 0
Accepted
time: 3643ms
memory: 8408kb
input:
100000 16 8 14266 4655 1910 6044 23911 5824 16951 999926439 2048 0 1792 49290 734 9216 288 55841 8 16530 5376 32785 289 0 320 8193 0 4 4 8 2048 0 0 8192 0 0 4 0 2 8224 0 0 4096 0 0 64 0 16386 2048 512 5120 32768 4160 512 0 0 512 0 0 0 8 0 0 0 0 0 0 0 8320 0 0 64 16384 16 0 0 0 4 128 8192 1024 0 2048...
output:
113134088 271310664 142021959 771434593 462641801 447067166 870052188 985866201 925618887 81764332 143783792 621593236 863707267 834046424 450353991 858184227 79201855 721850044 757424758 42085201 806870006 528044310 815006195 283966654 133805243 883587876 917828483 930878846 982582330 952003871 392...
result:
ok 65536 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 8208kb
input:
2 2 2 400000000 600000000 1 0 2 1
output:
0 200000002 680000005 120000001
result:
ok 4 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 8084kb
input:
10 5 5 30917 23628 20402 8259 999916794 23 25 18 0 26 13 11 0 7 7 7 10 0 12 30 9 6 17 0 18 26 0 27 20 14 24 29 0 26 0 10 23 0 8 7 7 21 8 0 17 2 30 21 0 30 29 10 0 27 30
output:
28922508 0 35621404 0 0 0 888248407 987509770 49397963 679795862 955143439 848384330 218304519 79967140 395924634 114547821 0 895939031 439920966 216672282 170089344 877936956 565519965 184330350 210465780 167531170 720441818 841868009 666011595 327987524 706054720 727462785
result:
ok 32 lines
Test #5:
score: 0
Accepted
time: 347ms
memory: 7192kb
input:
100 16 8 31365 21599 10193 28133 28700 27407 14496 999838107 4022 50386 30744 39278 43773 0 18674 38369 0 33802 31067 14537 43121 61045 29756 8818 5508 61053 28374 0 10443 64627 15285 6833 15374 28108 52460 1325 0 6241 10022 23568 0 42995 8213 895 38219 18427 692 21001 62860 2351 62552 51883 48859 0...
output:
452309043 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 65536 lines