专栏文章

题解：CF2138D Antiamuny and Slider Movement

MMaxBlazeResFire
CF2138D题解参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miny5se9
此快照首次捕获于
2025/12/02 10:16
3 个月前
此快照最后确认于
2025/12/02 10:16
3 个月前
查看原文
Observation1\rm Observation1：拆贡献。对于每个位置 xx，计算每个 xx 有多少种方案使得最终停在 xx。
Observation2\rm Observation2：这要求不能有太多的可选 xx。考虑一次操作（以向左为例）j→xj\rightarrow x，它对 ii 号块位置的影响形如：xi←min⁡{xi,x−(j−i)}x_i\leftarrow\min\{x_i,x-(j-i)\}，是 chkmin\rm chkmin 或者 chkmax\rm chkmax 操作的形式。
也即，枚举 ii 后，它最终能停到的位置最多有 q+1q+1 种，且观察操作，它每一次的参数都只与操作本身有关。把所有 x−(j−i)x-(j-i) 或 xx 或 x+(i−j)x+(i-j) 记为关键点，拿出来排序，记为新数列 tit_i。每次操作形如，把 xix_i 对特定值 tjt_j 进行 chkmin\rm chkmin 或者 chkmax\rm chkmax，或者移动到指定位置。
但还是不好计算最终恰好停留在 tjt_j 上的方案数。考虑转化成对于每个 jj，计算操作完后 xi≤tjx_i\leq t_j 的方案数，然后做差分求得恰好 xi=tjx_i=t_j 的方案数。
考虑怎样排列操作序列可以使得最终 xi≤tjx_i\leq t_j。把所有 chkmax\rm chkmax 操作（有 AA 个）与 chkmin\rm chkmin 操作（有 BB 个），移动到指定位置（有 CC 个）按参数各自排序，记 chkmax\rm chkmax 操作中参数严格大于 tjt_j 的有 aa 个，chkmin\rm chkmin 操作中参数不大于 tjt_j 的有 bb 个，移动到指定位置操作中参数不大于 tjt_j 的有 cc 个，那么在长度为 q=A+B+Cq=A+B+C 的操作序列中，有 a+b+Ca+b+C 个关键位置，a+C−ca+C-c 个红色点和 b+cb+c 个绿色点，形如要求最后一个红色点右侧至少有一个绿色点。这个的方案数就很好计算了，无脑一点就是 (A+B+Ca+b+C)(a+b+C−1a+C−c)(A+B+C−a−b−C)!(a+C−c)!(b+c)!\displaystyle\binom{A+B+C}{a+b+C}\binom{a+b+C-1}{a+C-c}(A+B+C-a-b-C)!(a+C-c)!(b+c)!。
还要根据初始位置的变化，考虑一些方案数为 q!q! 或 00 的特殊情况。
复杂度 O(nqlog⁡q)O(nq\log q)。
CPP
#include<bits/stdc++.h>
using namespace std;

#define MAXN 5005
#define int long long
#define mod 1000000007

int n,m,q,pos[MAXN],J[MAXN],X[MAXN],fac[MAXN],inv[MAXN],ifac[MAXN];
int maxx[MAXN],minn[MAXN],sett[MAXN],A,B,C,Xs[MAXN];
int cnta[MAXN],cntb[MAXN],cntc[MAXN],res[MAXN];

inline int Bino( int n , int m ){ return n >= 0 && m >= 0 && n >= m ? fac[n] * ifac[m] % mod * ifac[n - m] % mod : 0; }
inline void chkadd( int &x , int k ){ x += k; if( x >= mod ) x -= mod; }
inline void chkequ( int &x , int k ){ x = k; if( x >= mod ) x -= mod; }

inline void solve(){
	scanf("%lld%lld%lld",&n,&m,&q);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld",&pos[i]);
	for( int i = 1 ; i <= q ; i ++ ) scanf("%lld%lld",&J[i],&X[i]);
	for( int id = 1 ; id <= n ; id ++ ){
		A = B = C = 0;
		for( int j = 1 ; j <= q ; j ++ ){
			if( J[j] < id ) maxx[++A] = X[j] + ( id - J[j] );
			if( J[j] > id ) minn[++B] = X[j] - ( J[j] - id );
			if( J[j] == id ) sett[++C] = X[j];
		}
		int cnt = 0;
		for( int i = 1 ; i <= A ; i ++ ) Xs[++cnt] = maxx[i];
		for( int i = 1 ; i <= B ; i ++ ) Xs[++cnt] = minn[i];
		for( int i = 1 ; i <= C ; i ++ ) Xs[++cnt] = sett[i];
		Xs[++cnt] = pos[id];
		sort( Xs + 1 , Xs + cnt + 1 );
		cnt = unique( Xs + 1 , Xs + cnt + 1 ) - ( Xs + 1 );
		for( int i = 1 ; i <= A ; i ++ ) maxx[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , maxx[i] ) - Xs;
		for( int i = 1 ; i <= B ; i ++ ) minn[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , minn[i] ) - Xs;
		for( int i = 1 ; i <= C ; i ++ ) sett[i] = lower_bound( Xs + 1 , Xs + cnt + 1 , sett[i] ) - Xs;
		for( int i = 1 ; i <= cnt ; i ++ ) cnta[i] = cntb[i] = cntc[i] = 0;
		for( int i = 1 ; i <= A ; i ++ ) cnta[maxx[i]] ++;
		for( int i = 1 ; i <= B ; i ++ ) cntb[minn[i]] ++;
		for( int i = 1 ; i <= C ; i ++ ) cntc[sett[i]] ++;
		for( int i = 1 ; i <= cnt ; i ++ ){
			cnta[i] += cnta[i - 1],cntb[i] += cntb[i - 1],cntc[i] += cntc[i - 1];
			int a = A - cnta[i],b = cntb[i],c = cntc[i];
			res[i] = Bino( q , a + b + C ) * Bino( a + b + C - 1 , a + C - c ) % mod * fac[q - a - b - C] % mod * fac[a + C - c] % mod * fac[b + c] % mod;
			if( pos[id] > Xs[i] && b + c == 0 ) res[i] = 0;
			if( pos[id] <= Xs[i] && a + C - c == 0 ) res[i] = fac[q];
		}
		int Ans = 0;
		for( int j = cnt ; j >= 1 ; j -- ){
			chkequ( res[j] , res[j] - res[j - 1] + mod );
			chkadd( Ans , res[j] * Xs[j] % mod );
		}
		printf("%lld ",Ans);
	}
	puts("");
}

signed main(){
	fac[0] = 1; for( int i = 1 ; i < MAXN ; i ++ ) fac[i] = fac[i - 1] * i % mod;
	inv[1] = 1; for( int i = 2 ; i < MAXN ; i ++ ) inv[i] = ( mod - mod / i ) * inv[mod % i] % mod;
	ifac[0] = 1; for( int i = 1 ; i < MAXN ; i ++ ) ifac[i] = ifac[i - 1] * inv[i] % mod;
	int testcase; scanf("%lld",&testcase);
	while( testcase -- ) solve();
	return 0;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...