QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94960#6132. Repair the ArtworkGeorge_Plover#TL 8ms93724kbC++231.2kb2023-04-08 14:45:072023-04-08 14:45:10

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:45:10]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:93724kb
  • [2023-04-08 14:45:07]
  • 提交

answer

#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];
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)
            fill(f[i][j],f[i][j]+i*(i+1)/2+1,0);
    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(j,0,n)
        For(k,1,n*(n+1)/2)
            ans=(ans+1ll*f[n][j][k]*ksm(k,m))%MOD;
    printf("%d\n",ans);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)Main();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9736kb

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: 8ms
memory: 93724kb

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: -100
Time Limit Exceeded

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: