Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2205-cf833e09
この記事にトラックバックする(FC2ブログユーザー)

SRM532 DIV1 HARD - DengklekCountingFormations (この記事を編集する[管理者用])

Source

TopCoder SRM532 DIV1 HARD (1000pt)
Problem Statement

問題概要

N行M列のグリッドがある.
各セルに1以上K以下の数字を1つ書くのだけど,以下の条件を満たす書き方は何通りあるかをmod 1000000007で求める問題.
 任意の2つの行A, Bに対して,少なくても1つの数字が存在して,行Aに含まれるその数字の数と行Bに含まれるその数字の数は異なる
Nは10以下,Mは50以下,Kは100以下.

解法

他にも方法があるみたいだけど自分が解いた方法.
まず,Mの分割数を列挙する.
 M = A + B + C + ... (A ≥ B ≥ C ≥ ...)
として,ある行に対して,最も多い数字がA個,次に多い数字がB個,…,となる
数字の選び方と,数字を選んだとき1行に並べるパターン数を計算する.
後は,今何行埋めたか,を状態として,その数字の選び方のうち何個使うかで場合分けするDPする.
素直にやって,組み合わせの数とかを事前計算したり漸化式でうまく計算するとO(N^2 * Mの分割数)となるが微妙にタイムリミットが厳しい.
分割数を列挙して組み合わせの数を計算した時,「数字を選んだとき1行に並べるパターン数」が一致するものを全部まとめておくと最悪ケースで4倍ぐらい早くなって間に合うと思う.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long
#define M 1000000007

ll pw(ll a,ll b, ll md){
  ll r;
  if(!b) return 1;
  r = pw(a,b/2,md);
  r = (r*r)%md;
  if(b%2) r = (r*a)%md;
  return r;
}

void extended_euclid(ll x,ll y,ll *c,ll *a,ll *b){
  ll a0,a1,a2,b0,b1,b2,r0,r1,r2,q;
  r0=x; r1=y; a0=1; a1=0; b0=0; b1=1;
  while(r1>0){
    q=r0/r1; r2=r0%r1; a2=a0-q*a1; b2=b0-q*b1;
    r0=r1; r1=r2; a0=a1; a1=a2; b0=b1; b1=b2;
  }
  *c=r0; *a=a0; *b=b0;
}

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;
}


ll tst[500000], cst[500000]; int tst_size;
pair<ll,ll> for_sort[500000];
ll comb[200][200];
ll fact[200], fact_inv[200];

int now[10000];

void gen(int depth, int m, int st, int k){
  int i,j,sum;

  if(m == 0){
    tst[tst_size] = 1;
    sum = 0;
    rep(i,depth){
      sum += now[i];
      tst[tst_size] = (tst[tst_size] * fact_inv[now[i]])%M;
    }
    tst[tst_size] = (tst[tst_size] * fact[sum])%M;

    cst[tst_size] = (fact[k]*fact_inv[k-depth])%M;
    rep(i,depth){
      REP(j,i,depth) if(now[i]!=now[j]) break;
      cst[tst_size] = (cst[tst_size] * fact_inv[j-i])%M;
      i = j-1;
    }

    tst_size++;
  }

  if(depth == k) return;

  REP(i,st,m+1){
    now[depth] = i;
    gen(depth+1, m-i, i, k);
  }
}

class DengklekCountingFormations {
public:
int numFormations(int n, int m, int k) {
  int i,j,r;
  ll res = 0, tmp, mul1, mul2;
  ll dp[12];

  rep(i,200) comb[0][i] = 0;
  rep(i,200) comb[i][0] = 1;
  REP(i,1,200) REP(j,1,200) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j])%M;

  fact[0] = 1;
  REP(i,1,200) fact[i] = (fact[i-1]*i)%M;
  rep(i,200) fact_inv[i] = get_inv(fact[i], M);

  tst_size = 0;
  gen(0, m, 1, k);

  rep(i,tst_size) for_sort[i] = make_pair(tst[i], cst[i]);
  sort(for_sort, for_sort+tst_size);
  rep(i,tst_size) tst[i] = for_sort[i].first, cst[i] = for_sort[i].second;

  k = 1;
  REP(i,1,tst_size){
    if(tst[k-1] == tst[i]){
      cst[k-1] = (cst[k-1] + cst[i])%M;
    } else {
      tst[k] = tst[i];
      cst[k] = cst[i];
      k++;
    }
  }
  tst_size = k;

  dp[0] = 1;
  REP(i,1,n+1) dp[i] = 0;

  rep(j,tst_size) for(i=n-1;i>=0;i--) if(dp[i]){
    mul1 = mul2 = 1;
    REP(k,i+1,n+1){
      mul1 = (mul1 * tst[j])%M;
      mul2 = (mul2 * (cst[j]-(k-i-1)))%M;
      tmp = (mul1 * mul2)%M;
      if(tmp==0) break;
      tmp *= comb[n-i][k-i];
      tmp %= M;
      dp[k] += tmp * dp[i];
      dp[k] %= M;
    }
  }

  res = dp[n];
  return (int)res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2205-cf833e09
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。