Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM477 DIV2 HARD - CarelessSecretary (この記事を編集する[管理者用])

Source

TopCoder SRM477 DIV2 HARD (1000pt)
Problem Statement

問題概要

1~Nまでのpermutationのうち,
 p[i] != i (i=1,2,...,K)
を満たす物の数をmod 1000000007で求める問題.
Nは1000以下,Kは12以下.

解法

解法1:包除原理.
コンビネーションの数をちゃんと計算すればO(K^2+N).
解法2:DP.
状態数は,何個目の要素を考えているか,1~Kまでどれを使ったかのビットマスクでK*2^K.
以下のコードはDP.

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

int n,k;
ll dp[20][5000];
ll fact[2000];

ll solve(int depth,int mask){
  int i,j;
  ll res=0;

  if(dp[depth][mask]>=0) return dp[depth][mask];
  if(depth==k) return dp[depth][mask] = fact[n-k];

  rep(i,k) if(!(mask&1<<i)) if(depth!=i) res = (res+solve(depth+1,mask^(1<<i)))%M;

  j = n-k-depth; rep(i,k) if(mask&1<<i) j++;
  if(j>=0) res = (res + solve(depth+1,mask) * j)%M;

  return dp[depth][mask] = res;
}

class CarelessSecretary {
public:
int howMany(int N, int K) {
  int i,j;

  fact[0]=1; REP(i,1,2000) fact[i]=(fact[i-1]*i)%M;

  n=N; k=K;
  rep(i,20) rep(j,5000) dp[i][j]=-1;
  
  return solve(0,0);
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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