QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50783#4436. Link with Bracket Sequence IIzzxzzx123AC ✓323ms7816kbC++17969b2022-09-29 11:58:282022-09-29 11:58:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-29 11:58:31]
  • 评测
  • 测评结果:AC
  • 用时:323ms
  • 内存:7816kb
  • [2022-09-29 11:58:28]
  • 提交

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