Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Open 2010 Round 3 HARD - Passwords (この記事を編集する[管理者用])

Source

TopCoder Open 2010 Algorithm Round 3 HARD (1000pt)
Problem Statement
Open 2010 Algorithm Round 3 自分の参加記録

問題概要

アルファベットと数字からなるN文字の文字列のうち以下の条件を満たす物の数をmod 1000000009で求める問題.
 小文字アルファベットを少なくてもL文字含む
 大文字アルファベットを少なくてもU文字含む
 数字を少なくてもD文字含む
Nは200000以下.

解法

使う数字の数が大きい方からループして計算する.
適当に組み合わせの数を掛けるのを除外すると,ループの中で計算しないといけないのは
 E(n) = C(n,st) + C(n,st+1) + ... + C(n,ed)
といったものになる.これを毎回計算するとTLE.
次のループで計算しないといけないのは
 E(n-1) = C(n-1,st) + C(n-1,st+1) + ... + C(n-1,ed-1)
となって,二項係数の漸化式を用いて
 E(n-1) = 2*E(n) + C(n-1,st-1) + C(C-1,ed)
という形の漸化式で計算すれば間に合う.

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 NN 300000
#define M 1000000009
#define ll long long

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

ll f[NN], finv[NN];
ll pw26[NN], pw10[NN];
ll comb(ll a,ll b){
  ll res;
  if(b<0 || b>a) return 0;
  res = f[a];
  res = (res*finv[a-b])%M;
  res = (res*finv[b])%M;
  return res;
}


class Passwords {
public:
int countValid(int N, int L, int U, int D) {
  int i,j,k;
  ll res=0, tmp, bef;
  int n,a,b,st,ed;

  f[0]=1; REP(i,1,NN) f[i]=(f[i-1]*i)%M;
  rep(i,NN) finv[i] = pw(f[i],M-2);

  pw26[0]=1; REP(i,1,NN) pw26[i]=(pw26[i-1]*26)%M;
  pw10[0]=1; REP(i,1,NN) pw10[i]=(pw10[i-1]*10)%M;

  bef=-1;
  for(i=N;i>=D;i--){
    n = N-i; a = L; b = U;
    st = L; ed = n-U;
    if(st > ed) continue;

    if(bef==-1){
      bef = 0;
      REP(k,st,ed+1) bef = (bef+comb(n,k))%M;
    } else {
      bef = (bef * 2)%M;
      bef = (bef + comb(n-1,st-1))%M;
      bef = (bef + comb(n-1,ed))%M;
    }
    tmp = bef;
    
    tmp = (tmp * comb(N,i))%M;
    tmp = (tmp * pw10[i])%M;
    tmp = (tmp * pw26[N-i])%M;
    res = (res+tmp)%M;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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