QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#465938#9112. Zayin and Rafflegrass8cow#AC ✓2858ms104932kbC++171.4kb2024-07-07 13:55:142024-07-07 13:55:14

Judging History

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

  • [2024-07-07 13:55:14]
  • 评测
  • 测评结果:AC
  • 用时:2858ms
  • 内存:104932kb
  • [2024-07-07 13:55:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int mod=1e9+7;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
const int I=qpow(1000000000,mod-2);
int p[8],f[1<<16],st[101000][256],a[8],pp[1<<8],t[1<<16];
int pe[101001];
int main(){
    scanf("%d%d%d",&n,&m,&k);for(int i=0;i<k;i++)scanf("%d",&p[i]),p[i]=1ll*p[i]*I%mod;
    for(int s=1;s<(1<<k);s++)pp[s]=pp[s>>1]+(s&1);
    for(int i=0;i<n;i++){
        for(int j=0;j<k;j++)scanf("%d",&a[j]);
        for(int s=0;s<(1<<k);s++)for(int j=0;j<k;j++)if((s>>j)&1)
        st[i][s]|=a[j];
    }
    for(int s=0;s<(1<<m);s++)f[s]=1;
    for(int s=0;s<(1<<k);s++){
        int pw=0;
        for(int i=0;i<k;i++)if((s>>i)&1)(pw+=p[i])%=mod;
        pe[0]=1;
        for(int i=1;i<=n;i++)pe[i]=1ll*pw*pe[i-1]%mod;
        int S=((1<<k)-1)^s;
        memset(t,0,sizeof(t));
        for(int i=0;i<n;i++){
            for(int s2=S;;s2=(s2-1)&S){
                t[st[i][s|s2]]+=((pp[s2]&1)?-1:1);
                if(!s2)break;
            }
        }
        for(int i=0;i<m;i++)for(int s2=0;s2<(1<<m);s2++)if((s2>>i)&1)
        t[s2]+=t[s2^(1<<i)];
        for(int s2=0;s2<(1<<m);s2++)
        f[s2]=1ll*f[s2]*pe[t[s2]]%mod;
    }
    for(int i=0;i<m;i++)for(int s2=0;s2<(1<<m);s2++)if((s2>>i)&1)
    (f[s2]+=mod-f[s2^(1<<i)])%=mod;
    for(int s=0;s<(1<<m);s++)printf("%d\n",f[s]);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2778ms
memory: 104932kb

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: 2858ms
memory: 104916kb

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: 6188kb

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: 0ms
memory: 4092kb

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: 209ms
memory: 4564kb

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