계수(count)

계수(count)

제목 설명

 
귀염둥이 visit_세계의 경기, 그럼 반드시 계수 문제가 있을 거야!
NN 노드의 두 갈래 트리를 고려하면 노드에 1 N1 N의 번호가 표시됩니다.그리고 번호가 ii인 노드는 두 갈래 나무의 앞 순서에서 마침 ii가 등장한다.
우리는 AiAi가 번호를 ii로 표시하는 점이 두 갈래 나무의 중순에 나타나는 위치를 정의합니다.
현재 MM의 제한 조건을 제시하고 ii의 제한 조건은 ui,viui,vi를 제시하여 Aui가 vivi 전에 나타났다는 것을 나타낸다.
너는 상술한 모든 제한 조건을 충족시키는 몇 종류의 서로 다른 띠번호 두 갈래 나무가 있는지 계산해야 한다. 정답은 109+7109+7이다.
 
 

입력

 
첫 번째 줄은 정수 T(1≤T≤5)T(1≤T≤5)로 데이터 그룹 수를 나타낸다.
각 그룹의 데이터 첫 번째 동작은 두 개의 정수 N, MN, M입니다. 의미는 제목에 설명된 바와 같습니다.
다음 MM행, 줄마다 두 개의 정수 ui,vi(1≤ui,vi≤N)ui,vi(1≤ui,vi≤N).제한을 설명하다.
 
 

출력

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

샘플 입력

3
5 0
3 2
1 2
2 3
3 3
1 2
2 3
3 1

샘플 출력

1

힌트

 
설명하다
첫 번째 데이터는 아무런 제한이 없을 때 5개 점의 두 갈래 나무 형태 개수는 4242이다.
2조 데이터, 유일하게 조건을 충족시키는 두 갈래 나무의 형태는 1-2-3.(1은 뿌리, 2, 3은 모두 오른쪽 아들).
제3조 데이터, 제한 조건에 모순이 발생한다.

예제 2

문서를 보십시오.

데이터 범위 및 하위 작업

모든 테스트 데이터에 대해 T≤5, N≤400, M≤103T≤5, N≤400, M≤103을 보증합니다.
하위 작업 1(20분): M=0M=0.
하위 퀘스트 2(15분): N≤10N≤10.
하위 퀘스트 3(20분): N≤50, M≤1N≤50, M≤1.
하위 퀘스트 4(15분): N≤50N≤50.
하위 퀘스트 5(30분): 특별한 제한이 없습니다.
 
 

출처

국경절 캠프
solution
20점이 카틀란드 수였어요. 그리고 제가 죽었어요.
f[i][j]는 먼저 차례대로 차례대로 i~j로 구성된 나무가 몇 가지 다른 형태를 가지고 있는지 나타낸다
그러면 if(합법) f[i][j]=f[i+1][k]+f[k+1][j]
우리는 하나의 점이 합법적인지 아닌지를 어떻게 판단할 것인가를 고려한다
그렇다면
1 [i+1,k]의 어떤 점도 반복할 수 없음 [k+1,j] 이후
2 [i+1,k]의 어떤 점에서도 i이후로는
3i의 중서 반복은 [k+1,j] 이후에 할 수 없습니다.
구간 대 구간은 2차원 접두사와 최적화를 사용할 수 있다
 
효율 O(n^3)

#include
#include
#include
#include
#include
#include
#define maxn 405
#define mod 1000000007
#define ll long long
using namespace std;
int T,n,m,t1,t2;
ll f[maxn][maxn],s[maxn][maxn],a[maxn][maxn];
void init(){
    for(int i=0;i<=400;i++)
    for(int j=0;j<=400;j++)f[i][j]=s[i][j]=a[i][j]=0;
}
int calc(int x,int y,int xx,int yy){
    return s[xx][yy]-s[xx][y-1]-s[x-1][yy]+s[x-1][y-1];
}
bool pd(int ii,int xa,int xb,int ya,int yb){
    if(calc(ya,xa,yb,xb))return 0;
    if(calc(ya,ii,yb,ii))return 0;
    if(calc(ii,xa,ii,xb))return 0;
    return 1;
}
int main()
{
    cin>>T;
    while(T--){
        init();
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            scanf("%d%d",&t1,&t2);
            a[t1][t2]=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
        }
        for(int i=1;i<=n;i++)f[i][i]=1;
        for(int l=1;l<=n;l++){
        for(int i=1;i+l<=n;i++){
            int j=i+l;
            if(!calc(i,i+1,i,j))f[i][j]+=f[i+1][j];
            if(!calc(i+1,i,j,i))f[i][j]+=f[i+1][j];
            for(int k=i+1;k

 
posted @
2018-10-18 16:45 liankewei 읽기 (
...) 설명(
...) 모음 편집