yukicoder : No.2048 L(I+D)S

これは知識ゲー？
https://yukicoder.me/problems/no/2048

問題

正整数Nが与えられる。1～Nの順列のうち、LISとLDSの長さの和がNとなるのは何通りか。

解法

以下のヤング図形を考える。

• 1行目の横幅はAマス分
• 2行目の横幅は2マス分
• 3行目以降の横幅は1マス分で、全部でB行ある

A+B=Nである場合、このヤング図形に対する標準タブローは通りある。

ロビンソン・シェンステッド対応より、2つの標準タブローから、LIS/LDS数が一致する順列と1対1対応をとれるので、LIS長がA、LDS長がBとなる数列の個数は上記式の2乗。
あとはA,Bを総当たりしてそれらの和を取ればよい。

int N;
const ll mo=998244353;
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;

	cin>>N;
	
	ll ret=0;
	for(i=2;i<=N-2;i++) {
		ll a=fact[N];
		ll b=fact[i-2]*fact[N-i-2]%mo*i%mo*(N-i)%mo*(N-1)%mo;
		ret+=a*a%mo*modpow(b)%mo*modpow(b)%mo;
	}
	cout<<ret%mo<<endl;
}

まとめ

ヤング図形関係の問題久々に見たな。