第6回ドワンゴからの挑戦状予選 C-Cookie Distribution

考察メモ消す前に要点だけ

こう言う問題は色を用いて考えるのが好き

言い換え

$K$ 色のボールがある（単色のボールが $K$ 種類）。 $i$ 色目は $a_i$ 個ある。これらのボールを $N$ 人に、一人に同じ色二個いかないように全て配る。各人は手持ちのボールを一個光らせる。最終的な状態（各人が持ってるボールとその色、光り方）は何通りか。

例

サンプル1の場合

図の作成が下手であんまり光ってる感ないかもしれん

ここまで言い換えると簡単で、ボールを光らせるかどうかをそのボールをもらった瞬間に決定すると考えれば、
dp[i][b]:[0,i)色まで配り、b人は光らせるボールを選んだ
と状態をまとめることが出来る

遷移は配ると楽で、 $i$ 色目のボールを光らせる人が $x$ 人の時ごとに考えると、

$dp[i+1][b+x]+=dp[i][b]\times \binom{n-b}{x} \binom{n-x}{a_i-x}$

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/modint>
using namespace atcoder;
using mint=modint1000000007;

#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) v.begin(),v.end()

mint dp[100][3001];
mint Factorial[5000000],Finverse[5000000];
inline void Cinit(){
  Factorial[0]=1;
  for(int i=1;i<5e6;i++)Factorial[i]=Factorial[i-1]*i;
  Finverse[4999999]=mint(1)/Factorial[4999999];
  for(int i=4999998;i>=0;i--)Finverse[i]=(i+1)*Finverse[i+1];
}
mint nCk(int n,int k){
  if(n<k||k<0||n<0)return 0;
  return Factorial[n]*Finverse[n-k]*Finverse[k];
}

int main(){
  Cinit();
  int n,k;cin>>n>>k;
  vector<int> a(k);
  REP(i,k)cin>>a[i];
  dp[0][0]=1;
  REP(i,k)REP(b,n+1)REP(x,n+1)
    dp[i+1][b+x]+=dp[i][b]*nCk(n-b,x)*nCk(n-x,a[i]-x);
  cout<<dp[k][n].val()<<endl;
}

atcoder.jp

blogskol

思わず声に出して読みたくなるブログ

第6回ドワンゴからの挑戦状予選 C-Cookie Distribution

言い換え

例