Codeforces #1052 : Div2. F. Bubble Sort

なんかまたややこしい問題設定。
https://codeforces.com/contest/2146/problem/F

問題

整数列Aを引数とする関数sort(A)は、Aをバブルソートする際、何周swapを繰り返すかを意味する。
1～NのPermutation Pに対し、B[i]はsort(P[1....i])とする。
以下の条件をすべて満たすPは何通りか。

• 条件としてタプル(K,L,R)がM個与えられる。
• 各タプルは、BのうちK以下の値の要素数がL以上R以下であることを示す。

解法

C[i]を、A[j]＞A[i]となるj＞iの個数とする。
sort(A)はmax(C)となるし、AとCは全単射の関係となる。
そこでAではなくCを埋めて行くことを考える。

N要素を順に埋めて行くDPだとO(N^2)かかってTLEするが、Mは小さいのでM個の区間に分けその埋め方を考えていこう。

int T,N,M;
const ll mo=998244353;
ll dp[2010][2010];
ll S[2010];

const int NUM_=1400001;
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;
}


ll F(int L,int R,int K) {
	// L～R番目をK以下の値で埋める
	// a番目はa-1以下の値しか取れない
	if(L>K) return modpow(K+1,R-L+1);
	if(R<=K) return fact[R]*factr[L-1]%mo;
	return fact[K]*factr[L-1]%mo*modpow(K+1,R-K)%mo;
}

ll G(int L,int R,int K,int X) {
	ll v=(F(L,R,K)+mo-F(L,R,X))%mo;
	return v;
}

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>>T;
	while(T--) {
		cin>>N>>M;
		map<int,int> mi,ma;
		mi[N]=0;
		ma[N]=N;
		vector<int> pos,vs;
		vector<int> mis,mas;
		FOR(i,M) {
			cin>>x>>y>>k;
			if(ma.count(y)) {
				ma[y]=min(ma[y],x);
			}
			else {
				ma[y]=x;
				mi[y]=0;
			}
			vs.push_back(x);
			vs.push_back(x+1);
			if(k+1<=N) {
				if(mi.count(k+1)) {
					mi[k+1]=max(mi[k+1],x+1);
				}
				else {
					mi[k+1]=x+1;
					ma[k+1]=N;
				}
			}
		}
		pos.push_back(0);
		mis.push_back(0);
		mas.push_back(0);
		vs.push_back(0);
		vs.push_back(1);
		vs.push_back(N);
		sort(ALL(vs));
		vs.erase(unique(ALL(vs)),vs.end());
		FORR2(a,b,mi) {
			pos.push_back(a);
			mis.push_back(lower_bound(ALL(vs),b)-vs.begin());
			mas.push_back(lower_bound(ALL(vs),ma[a])-vs.begin());
		}
		M=pos.size();
		int nv=vs.size();
		FOR(x,M+1) FOR(y,nv+1) dp[x][y]=0;
		dp[0][0]=1;
		FOR(x,M-1) {
			FOR(y,nv+1) S[y+1]=(S[y]+dp[x][y])%mo;
			for(y=mis[x+1];y<=mas[x+1];y++) {
				dp[x+1][y]=dp[x][y]*F(pos[x]+1,pos[x+1],vs[y])%mo;
				if(y) (dp[x+1][y]+=S[y]*G(pos[x]+1,pos[x+1],vs[y],vs[y-1]))%=mo;
			}
		}
		ll ret=0;
		FOR(y,nv+1) ret+=dp[M-1][y];
		cout<<ret%mo<<endl;
		
		
	}
}

まとめ

何考えたらこういうややこしい問題設定思いつくんだろう。