最近O(2^N)系の包除原理の苦手意識が消えてきたと思ったけど、O(N^2)な包除原理はやっぱり苦手。
http://yukicoder.me/problems/643
問題
基本設定は(1)と同じ。
今度は条件を満たす割り振り方の組み合わせ数を求めよ。
解法
Editorialを見て解いた。
出席番号iを嫌いな生徒数をf(i)とする。
0~(N-1)の部分集合Sで衝突(出席番号がその番号を望まない生徒に割当たっている)するような組み合わせは、となるので、これを包除原理の要領で|S|の偶奇に合わせて足し引きする。
Sをまじめに2^N通り列挙する必要はなく、|S|の個数ごとに組み合わせ数を計算していくDPでO(N^2)で解くことができる。
ll mo=1000000007; int N; int X[5010]; ll dp[5050]; ll fact[5050]; void solve() { int i,j,k,l,r,x,y; string s; fact[0]=1; for(i=1;i<=5000;i++) fact[i]=fact[i-1]*i%mo; cin>>N; FOR(i,N) cin>>x, X[x]++; dp[0]=1; FOR(i,N) for(x=N;x>=0;x--) if(dp[x]) (dp[x+1] += X[i]*dp[x]) %= mo; ll ret=0; FOR(x,N+1) ret += ((x%2)?(-1):1)*dp[x]*fact[N-x]%mo; cout<<(ret%mo+mo)%mo<<endl; }
まとめ
終わってみると非常に単純なんだよなぁ。
下手にUnKoderのマラソン問題が頭に浮かんでしまってはまった。
包除原理=O(2^N)のイメージがあったので、最初にアプローチから外してしまったのよね。