kmjp's blog

競技プログラミング参加記です

yukicoder : No.727 仲介人moko

今日は実装軽めだね。
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しようとしてしまった。