Codeforces #789 : Div1 D. Tokitsukaze and Permutations

問題文がちょっと読みにくいな…。
https://codeforces.com/contest/1677/problem/D

問題

1～NのPermutation Pと整数Kがあったとする。
まず、Pに対し以下をK回行う。

• i=1～(N-1)に対し、P[i]＞P[i+1]ならswapする。

さらに、Pから整数列Vを作る。
V[i]は、P[j]＞P[i]となるjの個数とする。

今Vが与えられる。ただし、一部の値は不定とする。
条件を満たすPは何通りか。

解法

末尾K要素は、初期状態が何であれK回の処理で(N-K+1)～Nにそろえられてしまう。
よって、まずそれらK!通りはどうであれ以後の処理に影響を与えない。

あとはiが小さい順に、以下を掛けていく。

• 末尾K要素は、V[i]=0でなければならない。
• それ以外、V[i]=0なら、その要素は(K+1)通りの要素が入りうる。
• それ以外、V[i]が不定なら、その要素は(i+K+1)通りの要素が入りうる。

int T,N,K;
ll V[1010101];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&K);
		FOR(i,N) {
			scanf("%d",&x);
			V[i]=x;
		}
		ll ret=1;
		FOR(i,N) {
			if(i+K>=N) {
				if(V[i]>0) ret=0;
			}
			else {
				if(V[i]==-1) {
					ret=ret*(i+K+1)%mo;
				}
				else if(V[i]==0) {
					ret=ret*(K+1)%mo;
				}
			}
		}
		FOR(i,K) ret=ret*(i+1)%mo;
		cout<<ret<<endl;
		
	}
	
}

まとめ

本番は実験で解いてしまったな…。