kmjp's blog

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

yukicoder : No.329 全射

yukicoder

こういうWF久々に書いた。
http://yukicoder.me/problems/663

問題

N個の集合A[i]がある。
A[i]はw[i]個の整数1～w[i]からなる集合である。
また、2つの整数対(i,j)の集合Eが与えられる。

ここでf:A[i]→A[j]となる関数fは、以下の何れかを満たすとき"生きている"と定義する。

  1. i==jのとき
  2. (i,j)∈Eのとき
  3. 生きている関数g:A[i]→A[k]、h:A[k]→A[j]を合成してできる関数f=h・g

w,Eが与えられたとき、生きている関数fのうち全射となるものを求めよ。

解法

f:A[i]→A[j]が全射となるためには、w[i]≧w[j]であること事が必須である。
また、(i,j)がEに含まれない場合、関数の合成でfを作れる場合もあるが、その場合合成の過程で経由する各集合も要素数がw[j]以上でなければならない。

そこで、まずWarshall-Floyedの要領で各集合から各集合に変換するような関数の合成が存在するか、またその過程で取りえる集合の最小要素数のうち、合成順による最大値を求めよう。

WFの結果、f:A[i]→A[j]となる関数のうち生きていて、かつ関数の合成過程ですべて要素数がw[j]以上の場合、そのような関数fが存在する。
fの個数は、w[i]個の要素をw[j]個にマップする関数の個数なので、以下の何れかで解ける。

  • 包除原理の要領で、w[j]^w[i]通りの組み合わせのうち、w[j]個すべてに要素がマップされない組み合わせを削る。
    • ちょっと計算量が多く、定数倍高速化をしないと通らない。自分はインラインアセンブラで最初通した。
  • w[i]個をw[j]個に分ける分割数を求めたあと、w[j]の並べ方w[j]!を掛ける。
int N,M;
int W[300];
int mat[300][300];
ll mo=1000000007;

ll dp[1010][1010];
ll fact[1010];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	fact[0]=dp[0][0]=1;
	for(i=1;i<=1000;i++) {
		fact[i]=fact[i-1]*i%mo;
		dp[i][1]=1;
		for(j=2;j<=i;j++) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]*j)%mo;
	}
	
	cin>>N>>M;
	FOR(i,N) cin>>W[i], mat[i][i]=W[i];
	FOR(i,M) {
		cin>>x>>y, x--, y--;
		mat[x][y]=min(W[x],W[y]);
	}
	
	FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y] = max(mat[x][y], min(mat[x][z],mat[z][y]));
	
	ll ret=0;
	FOR(x,N) FOR(y,N) if(mat[x][y]>=W[y]) ret +=(dp[W[x]][W[y]] * fact[W[y]])%mo;
	
	cout<<ret%mo<<endl;
	
}

まとめ

この問題、言い回しが難しい＋固いのでなんか自然なストーリーの問題設定が欲しいなと思うけど、どんな問題文ならいいんだろうな。