QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#94960 | #6132. Repair the Artwork | George_Plover# | TL | 8ms | 93724kb | C++23 | 1.2kb | 2023-04-08 14:45:07 | 2023-04-08 14:45:10 |
Judging History
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...