CSAcademy Round #27 : G. Permutation Towers

これも思いつかない。
https://csacademy.com/contest/round-27/task/permutation-towers/

問題

数直線上1～Xの格子点上に、高さ1～Nの塔を1個ずつ建てたい。
なお、両隣で隣接する塔との間隔は、自身の高さ以上でなければならない。

N,M,Xが与えられたとき、上記を満たす塔の配置の組み合わせをMで割った剰余を求めよ。

解法

まず以下をもとめてしまおう。
f(x) := 塔の並べ方のうち、先頭から末尾までの塔の最短距離がxであるようなものの並べ方
本来xの距離があればいいものを(X-1)の距離のところに配置するので(X-1-x)余裕があるため、その余裕分をどの塔の間に配分するか考えると、解はとなる。
あとはf(x)をどう求めるか。

これはどうもSRM489の類題だったらしく、下記解説がわかりやすかった。
SRM489 Div1Hard - Algorithmer’s note

塔をいくつかまとめたグループを考える。塔を小さい順にこのグループ群に追加していくとする。
グループ内の塔は互いの距離が確定しており、間に別の塔を挿入することができない。
以下を考える。
g(i,g,x) := i番目までの塔を処理したのち、g個のグループがあり、各グループの距離の総和はxであるような組み合わせの数
先ほどのf(x)との関係は、f(x) = g(N,1,x)となる。

新たな塔iを加えるとき、そのやり方は3通りある。

• 塔単独で新たなグループを形成する。
  • g(i+1,g+1,x) += g(i,g,x)
• 既存のグループのいずれかの左右の端に追加する。その場合そのグループの長さがi増える。
  • g(i+1,g,x+i) += (2*g)*g(i,g,x)
• ２つのグループの間に挟まり、それらを連結する。その場合そのグループの長さが2*i増える。
  • g(i+1,g-1,x+2*i) += g*(g-1)*g(i,g,x)

O(N^4)なのでちょっと重いが、なんとか間に合う。

int N,X;
ll mo;

ll from[105][20202];
ll to[105][20202];

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>mo;
	
	from[0][0]=1;
	
	int ma=0;
	for(i=1;i<=N;i++) {
		FOR(j,i+1) ZERO(to[j]);
		FOR(j,i+1) {
			FOR(x,ma+1) if(from[j][x]) {
				// add new island
				(to[j+1][x] += from[j][x])%=mo;
				// add to island
				(to[j][x+i] += from[j][x] * (j*2))%=mo;
				// connect
				if(j>1) (to[j-1][x+2*i] += from[j][x] * (j* (j-1)))%=mo;
				ma=max(ma,x+i);
			}
		}
		swap(from,to);
	}
	
	ll ret=0;
	FOR(i,min(20002,X)) ret += from[1][i]*hcomb(N+1,X-1-i)%mo;
	cout<<ret%mo<<endl;
	
}

まとめ

このテクは他にも使えそうなので覚えておきたい。