QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#50783 | #4436. Link with Bracket Sequence II | zzxzzx123 | AC ✓ | 323ms | 7816kb | C++17 | 969b | 2022-09-29 11:58:28 | 2022-09-29 11:58:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=510;
int a[N];
ll g[N][N],f[N][N];
int n,m;
ll sol(int i,int j){
if(a[i]>0)
{
if((a[i]+a[j])==0)
{
return 1;
}else if(!a[j])
{
return 1;
}
}else if(!a[i])
{
if(!a[j])
{
return m;
}else if(a[j]<0){
return 1;
}
}
return 0;
}//处理一下
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
memset(g,0,sizeof g);
memset(f,0,sizeof f);
for(int i=1;i<n;i++)
{
g[i][i+1]=f[i][i+1]=sol(i,i+1);
}
for(int len=4;len<=n;len+=2)
{
for(int i=1;i+len-1<=n;i++){
int j=i+len-1;
f[i][j]=g[i+1][j-1]*sol(i,j)%mod;
g[i][j]=f[i][j];//初始化
for(int k=i+1;k<j;k+=2)
{
g[i][j]=(g[i][j]+g[i][k]*f[k+1][j]%mod)%mod;
}
}
}
printf("%lld\n",g[1][n]);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 323ms
memory: 7816kb
input:
20 10 1 1 -1 0 -1 -1 1 -1 1 0 0 10 2 0 1 1 -2 1 -2 -1 1 -2 1 8 5 0 0 4 0 0 2 -2 0 9 5 0 0 0 -3 0 0 0 0 0 8 5 0 1 0 0 0 0 0 0 498 249013689 239722195 0 0 0 -59682797 187213467 0 0 220688278 0 0 -133178217 165866643 -165866643 216987003 55229518 -55229518 -216987003 0 82546192 0 0 0 0 -62330427 -19687...
output:
0 0 75 0 1125 469841384 200768531 102789125 188155310 573855452 1 10742885 839674900 273705999 280134765 397511344 679455456 227852148 343052576 776801212
result:
ok 20 lines