AtCoder ABC #378 : G - Everlasting LIDS

久々にこれ使った。
https://atcoder.jp/contests/abc378/tasks/abc378_g

問題

整数A,Bが与えられる。
1～(A*B-1)のPermutationのうち、LIS長がA、LDS長がBで、末尾にどんな値を加えても、LIS長やLDS長が変化しないものは何通りか。

解法

ロビンソン・シェンステッド対応を使う。
A*Bのグリッドから、右下1マスを除いたタブローのマスに値を埋めることを考える。

タブローTのR行C列目をT(R,C)とすると、

• T(r,c)＜T(r+1,c)
• T(r,c)＜T(r,c+1)

となるように1～(A*B-1)に値を埋めることを考える。

その際、2つのタブローの組み合わせの積が解となるが、片方は「1要素追加するとA*Bの形になる」という条件が含まれる。
そこで以下の条件を追加して考えよう。

• T(r,A-1)＞T(r+1,A)

すでに埋まったマスの状態はO(Binom(A+B,B))通りぐらいなので、総当たりしながらDPで数え上げて行けばよい。

int A,B;
ll mo;
ll P[120];
map<ll,ll> memo;
int V[12];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>mo;
	if(A<B) swap(A,B);
	P[0]=1;
	FOR(i,B+2) P[i+1]=P[i]*(A+1);
	ll ret=1;
	FOR(x,2) {
	
		memo.clear();
		memo[0]=1;
		while(memo.size()) {
			ll k=memo.begin()->first;
			ll v=memo.begin()->second%mo;
			memo.erase(memo.begin());
			int sum=0;
			FOR(i,B) {
				V[i]=k/P[i]%(A+1);
				sum+=V[i];
			}
			if(sum==A*B-1) {
				ret=ret*(v%mo)%mo;
				break;
			}
			FOR(i,B) {
				if(V[i]==A) continue;
				if(i&&V[i]==V[i-1]) continue;
				if(x&&i<B-1&&V[i]==A-1&&V[i+1]<A-1) continue;
				memo[k+P[i]]+=v;
			}
		}
	}
	cout<<ret<<endl;
	
}

まとめ

今後またロビンソン・シェンステッド対応出てもすぐ思い出せるかな…。