New Year Contest 2015 I問題 - マージ

Source

New Year Contest 2015
問題文

問題概要

$1$ から $N$ の,$N$ 要素の置換 $P,Q$ が与えられる.
次の操作によって,配列 $R$ を作るとき,相異なる配列は何通りできるか ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
・$R$ を空にする
・$P$ と $Q$ が両方共空になるまで,$P$ か $Q$ の先頭の要素(片方がからならばそちらは選べない)を $1$ つ取り出し,$R$ の最後にくっつける,というのを繰り返す.

解法

DPかメモ化再帰する.
状態は($P$ の残りの要素の個数,$Q$ の残りの要素の個数)を取り,そこまでで(もしくはそれ以降のみを考えて)作れる配列のパターン数を計算する.
残りのみを考えて,$P$ の先頭と $Q$ の先頭が一致する場合,もっと一般に,$P$ の先頭から何個かと $Q$ の先頭から何個かが一致する場合は,複数のパターンで同じ配列が得られるので,包除原理をする.
その際の包除原理の係数は,二項係数と包除原理を用いて最初にDPをして計算しておいた.
$P$ と $Q$ が置換なので,$P$ の先頭と $Q$ の先頭が一致しているのは合計で $O(N^2)$ を超えられないので,時間計算量は合計で $O(N^2)$ になる.

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
 
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
#define ll long long
#define ull unsigned ll
 
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
 
#define MD 1000000007
 
void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){ll d=1,e=0,f,g=0,h=1,i,j=x,k=y,l,q;while(k>0)q=j/k,l=j%k,f=d-q*e,i=g-q*h,j=k,k=l,d=e,e=f,g=h,h=i;*c=j;*a=d;*b=g;}
ll get_inv(ll n, ll p){ll a,b,c;extended_euclid(n,p,&c,&a,&b);if(a<p)a+=p;return a%p;}
 
struct combination{
  int *f,*v,**d, m,s;
  void* init(void *mem, int md, int lim=1000100, int small=0){int i,j;m=md;s=small;f=(int*)mem;v=f+lim;d=(int**)(v+lim);d[0]=(int*)(d+s);REP(i,1,s)d[i]=d[i-1]+s;mem=(void*)(d[0]+s*s);f[0]=1;REP(i,1,lim)f[i]=(ll)f[i-1]*i%m;v[lim-1]=get_inv(f[lim-1],m);for(i=lim-1;i;i--)v[i-1]=(ll)v[i]*i%m;REP(i,1,s)d[0][i]=0;rep(i,s)d[i][0]=1;REP(i,1,s)REP(j,1,s){d[i][j]=d[i-1][j-1]+d[i-1][j];if(d[i][j]>=m)d[i][j]-=m;}return mem;}
  ll C(int a, int b){if(b<0||b>a)return 0;if(a<s)return d[a][b];return (ll)f[a]*v[b]%m*v[a-b]%m;}
  ll P(int a, int b){if(b<0||b>a)return 0;return (ll)f[a]*v[a-b]%m;}
  ll H(int a, int b){if(a==0&&b==0)return 1;if(a<=0||b<0)return 0;return C(a+b-1,b);}
};
 
 
int N, P[2222], Q[2222];
int dp[2222][2222];
ll cnt[2222];
 
int solve(int a, int b){
  int i, j, k;
  int res = 0;
 
  if(dp[a][b] >= 0) return dp[a][b];
  if(a==N || b==N) return dp[a][b] = 1;
 
  res += solve(a+1,b);
  if(res >= MD) res -= MD;
  res += solve(a,b+1);
  if(res >= MD) res -= MD;
 
  for(i=0;;i++){
    if(a+i >= N || b+i >= N) break;
    if(P[a+i] != Q[b+i]) break;
    res = (res - cnt[i+1] * solve(a+i+1, b+i+1)) % MD;
    if(res < 0) res += MD;
  }
 
  return dp[a][b] = res;
}
 
int main(){
  int i, j, k, res;
  void *mem = malloc(70000000);
  ll inv = (MD + 1) / 2;
  combination comb;
 
  mem = comb.init(mem, MD, 10000, 0);
  REP(i,1,2222){
    cnt[i] = comb.C(2*i, i) * inv % MD;
    REP(j,1,i){
      cnt[i] -= cnt[j] * comb.C(2*(i-j), i-j);
      cnt[i] %= MD;
    }
  }
  
 
  reader(&N);
  rep(i,N) reader(P+i);
  rep(i,N) reader(Q+i);
 
  rep(i,N+1) rep(j,N+1) dp[i][j] = -1;
  res = solve(0,0);
  writerLn(res);
 
  return 0;
}

Current time: 2017年07月21日13時37分11秒
Last modified: 2015年01月28日00時32分36秒 (by laycrs)
Tags: Competitive_Programming AtCoder New_Year_Contest_2015
トップページに戻る

Logged in as: unknown user (not login)

ログイン: