[CSP-S 에뮬레이션 테스트]: 계수(DP+ 기억식 검색)

제목 설명

$visit\text{_}세계 $의 경기, 그것은 반드시 계수 문제가 있을 것이다!$N$노드의 두 갈래 트리를 고려하면, 노드에 $1\sim N$의 번호가 표시됩니다.그리고 번호가 $i$인 노드는 두 갈래 나무의 앞 순서에 마침 $i$개가 나타납니다.우리 정의 $A_i$는 번호가 $i$인 점이 두 갈래 트리의 중간 순서에 나타나는 위치를 나타냅니다.현재, $M$개 제한 조건, $i$개 제한 조건은 $u_i,v_i$, $A_{u_i},A_{v_i}$는 상기 모든 제한 조건을 충족시키는 몇 가지 다른 표시 트리가 있는지 계산해야 합니다. 정답은 $10^9+7$입니다.

형식 입력

첫 번째 줄은 데이터 그룹 수를 나타내는 정수 $T (1\leqslant T\leqslant 5) $입니다.각 그룹의 데이터 첫 번째 동작은 제목에 설명된 대로 두 개의 정수 $N, M$입니다.다음 $M$행, 행당 두 개의 정수 $u_i,v_i(1\leqslant u_i,v_i\leqslant N)$.제한 사항을 설명합니다.

출력 형식

각 그룹의 데이터에 대해 한 줄에 하나의 정수를 출력하여 답을 표시한다.

예제

샘플 입력:
35 03 21 22 33 31 22 33 1
샘플 출력:
4210

데이터 범위 및 팁

예제 설명:
첫 번째 데이터는 제한이 없을 때 5$개의 점의 두 갈래 트리 형태 개수는 42$입니다.두 번째 그룹의 데이터, 유일하게 조건을 충족시키는 두 갈래 나무의 형태는 $1-2-3$이다.($1$은 루트이고 $2,3$는 모두 오른쪽 아들입니다.)제3조 데이터, 제한 조건에 모순이 발생한다.
데이터 범위:
모든 테스트 데이터에 대해 $T\leqslant 5, N\leqslant 400, M\leqslant 10^3$하위 작업 $1$($20$분): $M=0$를 보장합니다.하위 작업 $2$($15$분): $N\leqslant 10$.하위 작업 $3$($20$분): $N\leqslant 50, M\leqslant 1$.하위 작업 $4$($15$분): $N\leqslant 50$입니다.하위 작업 $5$($30$분): 특별한 제한이 없습니다.

풀다

먼저 세 가지 반복 서열을 복습해 봅시다.
　　$\alpha.$앞(먼저) 순서 반복: 루트 $\rightarrow$왼쪽 $\rightarrow$오른쪽.
$\beta, $중 순서 반복: 왼쪽 $\rightarrow$중 $\rightarrow$오른쪽.
　　$\gamma.$다음 순서 반복: 왼쪽 $\rightarrow$오른쪽 $\rightarrow$루트.
기억을 편리하게 하기 위해서 우리는'뿌리'가 그 안에 있는 위치만 기억하면 된다. 먼저 뿌리를 앞, 중간, 중간, 뒤가 뿌리를 뒤로, 왼쪽이 앞, 오른쪽이 뒤에 있다.
$M=0$의 상황에서 착안해도 무방하다. 규칙을 찾아서 카드란 수를 발견할 수 있다. 간단하게 증명해 보자.
왼쪽 아들에게는 $+1$, 오른쪽 아들에게는 $-1$로 카트란드 수이다.
하지만 계속 생각하다 보면 죽는다..
다른 사고방식으로 이 문제를 해결하는 것을 고려하고 $DP$를 고려하여 $dp[l][r]$표시점의 번호 구간 $[l,r]$로 구성할 수 있는 서로 다른 형태의 수의 개수를 설정합니다.
앞 순서를 만족시켜야 하기 때문에 점의 번호이기 때문에 $l$는 루트 노드일 뿐만 아니라 좌우 트리 안의 점의 번호도 각각 연속적이기 때문에 우리는 이동 방정식을 얻을 수 있다.
$$dp[l][r]=\sum\limits_{i=l}^r dp[l+1][i]\times dp[i+1][r]$$
이어서 제한이 있는 상황을 고려하면 사실 매우 간단하다.두 개의 $u$와 $v$를 설정해도 무방하며, $u$의 번호는 $v$보다 작습니다.
만약 제한이 존재하면 중순으로 $v$가 $u$에 들어가기 전에 $v$는 $u$의 왼쪽 트리에 있어야 합니다.반대의 이치.
따라서 왼쪽 트리에서 가장 큰 점 ($L[i]$로 설정됨) 과 오른쪽 트리에서 가장 작은 점 ($R[i]$로 설정됨) 을 미리 처리할 수 있습니다.
$$dp[l][r]=\sum\limits_{i=L[l]}^{R[l]}dp[l+1][i]\times dp[i+1][r])$$
그래서 이 문제는 해결되었다.
시간 복잡도: $\Theta(n^3)$.
예상 득점: $100$분.
실제 득점: $100$분.

코드 시간

#include
using namespace std;
const int mod=1000000007;
int N,M;
bool Map[401][401];
int L[401],R[401];
long long dp[401][401];
void pre_work()
{
	memset(Map,0,sizeof(Map));
	memset(dp,-1,sizeof(dp));
}
long long dfs(int l,int r)
{
	if(l>r)return 1;
	if(L[l]>r)return 0;
	if(l==r)return 1;
	if(dp[l][r]!=-1)return dp[l][r];
	dp[l][r]=0;
	for(int i=L[l];i<=min(R[l],r);i++)
		dp[l][r]=(dp[l][r]+dfs(l+1,i)*dfs(i+1,r)%mod)%mod;
	return dp[l][r];
}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		pre_work();
		scanf("%d%d",&N,&M);
		for(int i=1;i<=M;i++)
		{
			int u,v;scanf("%d%d",&u,&v);
			Map[u][v]=1;
		}
		for(int i=1;i<=N;i++)
		{
			L[i]=R[i]=i;
			for(int j=i+1;j<=N;j++)if(Map[j][i])L[i]=j;
			for(int j=i+1;j<=N;j++){if(Map[i][j])break;R[i]=j;}
		}
		printf("%lld
",max(0LL,dfs(1,N)));
	}
	return 0;
}

rp++