今日は実装軽めだね。
https://yukicoder.me/problems/no/727
問題
店に2N人の人が来る。
N人はそれぞれ異なる商品を1つ売りに来て、残りN人は店にある商品をいずれか1つ買って帰る。
なお、買う人は店に商品が1個以上あるときしか来ない。
倍々の組み合わせは何通りあるか。
解法
売る人が来る順番がN!通り、買う人が来る順番がN!通り。
あとは売る人と買う人の対応付けを考える。
全部で2N人が来るわけだが、売買どちらか未確定の人のうち、最初に来るのは売る人である。
その人の商品を買うのは、残り(2N-1)人のうちの誰かである。
…と2人ずつ組にすることを考えると、その組み合わせは(2N-1)!!通りである。
よってN!*N!*(2N-1)!!が解。
int N; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll ret=1; for(i=1;i<=N;i++) ret=ret*i%mo*i%mo; for(i=1;i<=2*N-1;i+=2) ret=ret*i%mo; cout<<ret<<endl; }
まとめ
最後の(2N-1)!!の部分、最初真面目にDPしようとしてしまった。