Submission #2367376

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

const int mod=1000000007;
inline void add(int &a,int b){
    a+=b;
    if(a>=mod)a-=mod;
}
int mpow(int n,int m){
    int ret=1;
    while(m){
        if(m&1)ret=ret*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return ret;
}
const int FACT_SIZE=1111111;
int fact[FACT_SIZE];
int inv[FACT_SIZE];
struct fact_exec{
    fact_exec(){
        fact[0]=1;
        for(int i=1;i<FACT_SIZE;i++)fact[i]=fact[i-1]*i%mod;
        inv[FACT_SIZE-1]=mpow(fact[FACT_SIZE-1],mod-2);
        for(int i=FACT_SIZE-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    }
}factexec;
int nCk(int n,int k){
    if(n<0|k<0||k>n)return 0;
    return fact[n]*inv[k]%mod*inv[n-k]%mod;
}
int nPk(int n,int k){
    if(n<0||k<0||k>n)return 0;
    return fact[n]*inv[n-k]%mod;
}


int N;
int dp[2][52][52][52][52];

int sum[52][52][52][52];
int sum2[52][52][52][52];
int sum3[52][52][52];
int sum4[52][52][52];
signed main(){

    cin>>N;
    vint A(2*N-1);
    rep(i,2*N-1)cin>>A[i];
    sort(all(A));
    while(N>1&&A[N-2]==A[N-1]&&A[N-1]==A[N]){
        A.erase(A.begin()+N-2,A.begin()+N);
        N--;
    }


    if(N>1&&A[N-2]==A[N-1])dp[0][N-1][N][N-1][0]=1;
    else if(N>1&&A[N-1]==A[N])dp[0][N-1][0][N-1][N]=1;
    else dp[0][N-1][0][N-1][0]=1;

    for(int x=0;x<N-1;x++){
        memset(sum,0,sizeof(sum));
        memset(sum2,0,sizeof(sum2));
        memset(sum3,0,sizeof(sum3));
        memset(sum4,0,sizeof(sum4));
        for(int i=0;i<N;i++){
            for(int j=0;j<=N;j++){
                for(int k=0;k<N;k++){
                    for(int l=0;l<=N;l++){
                        if(dp[x&1][i][j][k][l]==0)continue;

                        if(j==N||l==N){
                            int jj=j,ll=l;
                            if(jj==N)jj=0;
                            if(ll==N)ll=0;


                            int a=max(N-1-x-1,k);
                            int b=k+ll;
                            if(a<b){
                                add(sum[i][jj][k][a-k],dp[x&1][i][j][k][l]);
                                add(sum[i][jj][k][b-k],mod-dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1;
                            if(a<k){
                                add(dp[(x+1)&1][i][jj][a][(a>0&&A[2*N-1-1-a]==A[2*N-1-1-(a-1)])*N],dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1+1;
                            b=k;
                            if(a<b){
                                add(sum3[i][jj][a],dp[x&1][i][j][k][l]);
                                add(sum3[i][jj][b],mod-dp[x&1][i][j][k][l]);
                            }
                            /*
                            for(int m=N-1-x-1;m<k+ll;m++){
                                if(m>=k)add(dp[(x+1)&1][i][jj][k][m-k],dp[x&1][i][j][k][l]);
                                else if(m==N-1-x-1||A[2*N-1-1-m]!=A[2*N-1-1-(m-1)])add(dp[(x+1)&1][i][jj][m][(m>0&&A[2*N-1-1-m]==A[2*N-1-1-(m-1)])*N],dp[x&1][i][j][k][l]);
                            }
                            */

                            a=max(N-1-x-1,i);
                            b=i+jj;
                            if(a<b){
                                add(sum2[i][a-i][k][ll],dp[x&1][i][j][k][l]);
                                add(sum2[i][b-i][k][ll],mod-dp[x&1][i][j][k][l]);
                            }


                            a=N-1-x-1;
                            if(a<i){
                                add(dp[(x+1)&1][a][(a>0&&A[a]==A[a-1])*N][k][ll],dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1+1;
                            b=i;
                            if(a<b){
                                add(sum4[a][k][ll],dp[x&1][i][j][k][l]);
                                add(sum4[b][k][ll],mod-dp[x&1][i][j][k][l]);
                            }
                            /*
                            for(int m=N-1-x-1;m<i+jj;m++){
                                if(m>=i)add(dp[(x+1)&1][i][m-i][k][ll],dp[x&1][i][j][k][l]);
                                else if(m==N-1-x-1||A[m]!=A[m-1])add(dp[(x+1)&1][m][(m>0&&A[m]==A[m-1])*N][k][ll],dp[x&1][i][j][k][l]);

                            }
                            */
                        }
                        else{
                            add(dp[(x+1)&1][i][j][k][l],dp[x&1][i][j][k][l]);

                            int a=max(N-1-x-1,k);
                            int b=k+l;
                            if(a<b){
                                add(sum[i][j+1][k][a-k],dp[x&1][i][j][k][l]);
                                add(sum[i][j+1][k][b-k],mod-dp[x&1][i][j][k][l]);
                            }
                            a=N-1-x-1;
                            if(a<k){
                                add(dp[(x+1)&1][i][j+1][a][(a>0&&A[2*N-1-1-a]==A[2*N-1-1-(a-1)])*N],dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1+1;
                            b=k;
                            if(a<b){
                                add(sum3[i][j+1][a],dp[x&1][i][j][k][l]);
                                add(sum3[i][j+1][b],mod-dp[x&1][i][j][k][l]);
                            }

                            /*
                            for(int m=N-1-x-1;m<k+l;m++){
                                if(m>=k);//add(dp[(x+1)&1][i][j+1][k][m-k],dp[x&1][i][j][k][l]);
                                else if(m==N-1-x-1||A[2*N-1-1-m]!=A[2*N-1-1-(m-1)])add(dp[(x+1)&1][i][j+1][m][(m>0&&A[2*N-1-1-m]==A[2*N-1-1-m+1])*N],dp[x&1][i][j][k][l]);
                            }*/


                            a=max(N-1-x-1,i);
                            b=i+j;
                            if(a<b){
                                add(sum2[i][a-i][k][l+1],dp[x&1][i][j][k][l]);
                                add(sum2[i][b-i][k][l+1],mod-dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1;
                            if(a<i){
                                add(dp[(x+1)&1][a][(a>0&&A[a]==A[a-1])*N][k][l+1],dp[x&1][i][j][k][l]);
                            }

                            a=N-1-x-1+1;
                            b=i;
                            if(a<b){
                                add(sum4[a][k][l+1],dp[x&1][i][j][k][l]);
                                add(sum4[b][k][l+1],mod-dp[x&1][i][j][k][l]);
                            }
                            /*
                            for(int m=N-1-x-1;m<i+j;m++){
                                if(m>=i);//add(dp[(x+1)&1][i][m-i][k][l+1],dp[x&1][i][j][k][l]);
                                else if(m==N-1-x-1||A[m]!=A[m-1])add(dp[(x+1)&1][m][(m>0&&A[m]==A[m-1])*N][k][l+1],dp[x&1][i][j][k][l]);
                            }
                            */
                        }

                        dp[x&1][i][j][k][l]=0;
                    }
                }
            }
        }


        rep(i,N)rep(j,N+1)rep(k,N)rep(l,N+1){
            add(sum[i][j][k][l+1],sum[i][j][k][l]);
            add(dp[(x+1)&1][i][j][k][l],sum[i][j][k][l]);
            add(sum2[i][j+1][k][l],sum2[i][j][k][l]);
            add(dp[(x+1)&1][i][j][k][l],sum2[i][j][k][l]);
        }
        rep(i,N)rep(j,N+1)rep(k,N){
            add(sum3[i][j][k+1],sum3[i][j][k]);
            if(k&&A[2*N-1-1-k]!=A[2*N-1-1-(k-1)])add(dp[(x+1)&1][i][j][k][0],sum3[i][j][k]);
        }
        rep(i,N)rep(k,N)rep(l,N+1){
            add(sum4[i+1][k][l],sum4[i][k][l]);
            if(i&&A[i]!=A[i-1])add(dp[(x+1)&1][i][0][k][l],sum4[i][k][l]);
        }
    }

    /*
    for(int x=0;x<N-1;x++){
        for(int i=2*N-1;i>=0;i--){
            int j=N-1-x;
            for(int k=2*N-1;k>=0;k--){
                int l=N-1-x;

                add(dp[x+1][i][k],dp[x][i][k]);
                for(int m=l-1;m<k;m++)add(dp[x+1][i+1][m],dp[x][i][k]);
                for(int m=j-1;m<i;m++)add(dp[x+1][m][k+1],dp[x][i][k]);
            }
        }
    }*/

    int ans=0;
    rep(i,N+1)rep(j,N+1)rep(k,N+1)rep(l,N+1)add(ans,dp[(N-1)&1][i][j][k][l]);
    cout<<ans<<endl;
    return 0;
}

Submission Info

Judge Result