QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94964#6132. Repair the ArtworkGeorge_Plover#AC ✓3638ms230944kbC++231.4kb2023-04-08 14:55:122023-04-08 14:55:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-08 14:55:13]
  • 评测
  • 测评结果:AC
  • 用时:3638ms
  • 内存:230944kb
  • [2023-04-08 14:55:12]
  • 提交

answer

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
template<class T> void chkmin(T &x,T y){if(y<x)x=y;}
typedef long long ll;
const int N=105,MOD=1000000007;
int mo(int x){return x>=MOD?x-MOD:x;}
void moplus(int &x,int y){x=mo(x+y);}
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%MOD;
        b>>=1;
        a=1ll*a*a%MOD;
    }
    return res;
}
int f[N][N][N*N/2],a[N],kmi[N*N/2];
int n,m;
void Main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    For(i,1,n)scanf("%d",a+i);
    f[0][0][0]=1;
    For(i,1,n)
        For(j,0,i)
            memset(f[i][j],0,i*(i+1)*2+4);
    For(i,0,n-1)
        For(j,0,i)
            For(k,0,i*(i+1)/2)
                if(a[i+1]==0)moplus(f[i+1][j+1][k+j+1],f[i][j][k]);
                else if(a[i+1]==1)moplus(f[i+1][0][k],f[i][j][k]);
                else moplus(f[i+1][0][k],MOD-f[i][j][k]),moplus(f[i+1][j+1][k+j+1],f[i][j][k]);
    int ans=0;
    For(k,1,n*(n+1)/2)kmi[k]=ksm(k,m);
    For(j,0,n)
        For(k,1,n*(n+1)/2)
            ans=(ans+1ll*f[n][j][k]*kmi[k])%MOD;
    printf("%d\n",ans);
}
int main()
{
    //int ti=clock();
    //freopen("G.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)Main();
    //printf("time=%.4lf\n",1.0*(clock()-ti)/CLOCKS_PER_SEC);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9896kb

input:

3
2 2
2 0
3 2
2 1 0
3 1
2 1 0

output:

8
3
1

result:

ok 3 number(s): "8 3 1"

Test #2:

score: 0
Accepted
time: 4ms
memory: 93644kb

input:

100
2 1
0 1
2 1
2 1
2 1
1 1
1 6
2
1 14
2
3 12
2 2 2
6 13
2 2 0 2 0 2
7 14
0 0 0 0 2 2 0
5 8
2 2 0 0 0
5 5
2 2 0 0 0
12 3
0 2 0 2 2 0 1 2 2 2 2 0
7 11
2 2 0 1 0 1 0
4 4
2 1 2 2
7 5
1 1 0 0 1 0 0
2 14
2 1
15 17
2 2 1 2 0 0 0 0 2 0 1 0 0 0 0
15 11
1 1 2 0 1 2 0 0 1 0 2 1 1 1 1
15 18
1 0 1 0 2 2 1 2 0 1...

output:

1
1
0
1
1
175715347
833406719
467966815
458805426
650344
2208
537089254
146
7776
1
703335050
123067364
355668256
487954758
53774922
544070885
436748805
369291507
760487845
513270785
501075264
487417783
464534262
979007529
137956839
143317512
648268264
851188473
702545117
946416372
595191705
35054850...

result:

ok 100 numbers

Test #3:

score: 0
Accepted
time: 2286ms
memory: 230944kb

input:

1000
20 673037423
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 774964932
2 2 2
17 730319736
2 2 1 1 2 2 2 2 2 2 2 2 2 1 2 2 1
11 893285699
2 2 2 1 2 1 2 2 2 1 2
16 98149251
1 2 1 2 1 2 1 1 2 1 2 2 2 2 1 2
7 556953277
1 2 2 1 2 2 2
3 228111342
1 1 1
11 640995044
2 2 1 1 2 2 1 1 1 1 1
19 741419324
1 1 2 ...

output:

447486147
204414804
452414918
684654914
763978130
805973365
0
922180033
214948715
401017738
0
201368027
752718484
611006275
848004989
391560729
950934074
202096866
443534870
24665646
482580424
321199514
922369975
152629767
5546104
1
194145234
1
1
1
562381239
648246425
497517379
217016206
961507095
4...

result:

ok 1000 numbers

Test #4:

score: 0
Accepted
time: 3638ms
memory: 230868kb

input:

1000
50 416236992
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 657728991
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 740461763
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

763259804
476502422
599342821
232859927
793988697
591429049
270188459
585052379
112828376
874793236
511742305
443789116
531138043
829814299
715762187
530976897
659595243
398499036
665696512
377388317
780011237
877457048
769085674
80046792
628967449
305823394
274620920
654337446
807171478
690217437
6...

result:

ok 1000 numbers

Test #5:

score: 0
Accepted
time: 3221ms
memory: 230900kb

input:

1000
50 598094879
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 370102582
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
50 89148477
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...

output:

799398716
932856936
764416567
57812598
711885564
231337579
355184372
128337468
66039637
243697360
95147120
522827313
427687773
11613749
119992325
840421248
552748897
2153604
854978507
598264350
888588637
168914307
64499881
640494492
442303426
759524304
392240094
936658374
641034548
250860728
8449099...

result:

ok 1000 numbers