JZOJ 6809. 【2020.10.29提高組模擬】不難題

題目大意

• 有 K K K個 1 ? N 1-N 1?N的排列，每次可以挑選一個佇列取出隊首，但不能連續取出 K K K個相同的數，要求取出每個區間 [ l , r ] [l,r] [l,r]中排列且不能連續取出 r ? l + 1 r-l+1 r?l+1個相同的數的方案數，
• N , K ≤ 300 N,K\leq 300 N,K≤300

題解

• 這題可以聯想到平面上只能向右向上走，要求到達某個點且有若干個點不能經過的方案數，
• 可以用容斥來做設 f i f_i fi?表示僅僅經過了第 i i i個不能經過的點的方案數，用總方案數減去其他 f j f_j fj?即為 f i f_i fi?，簡單組合數計算即可，
• 這題也是同理，但維度變成了 K K K維，同樣設 f i f_i fi?表示僅有 i i i連續出現了若干次，那么可以列舉 f j f_j fj?轉移到 f i f_i fi?，當然要注意這里不只是組合數，而是先要到達每個 i i i前一個的位置，然后再乘階乘，暴力做是 O ( N 2 K 3 ) O(N^2K^3) O(N2K3)的，中間計算簡單優化一下可以達到 O ( N 2 K 2 ) O(N^2K^2) O(N2K2)，仍舊是過不了，
• 發現題目規定了是隨機的，也就是區間跨度越大，可以轉移的量就會越少，那么直接暴力把每次可以轉移的記錄下來，就可以過了，
• 注意區間右端點最好要從左端點 + 1 +1 +1開始列舉，不然常數大可能過不了，另外可以盡量減少模運算的次數，

代碼

#include<cstdio>
#include<queue>
using namespace std;
#define N 310
#define ll long long
#define md 1000000007
int a[N][N], p[N][N];
ll F[N * N], G[N * N], f[N];
int Sum[N][N], S[N][N], sum[N], s[N];
queue<int> q[N];
ll C(int x, int y) {
	return F[x] * G[y] % md * G[x - y] % md;
}
ll ksm(ll x, ll y) {
	if(!y) return 1;
	ll l = ksm(x, y / 2);
	if(y % 2) return l * l % md * x % md;
	return l * l % md;
}
int main() {
	int n, m, i, j, k, l, h, x;
	scanf("%d%d", &m, &n);
	F[0] = 1;
	for(i = 1; i < N * N; i++) F[i] = F[i - 1] * i % md;
	G[N * N - 1] = ksm(F[N * N - 1], md - 2);
	for(i = N * N - 2; i >= 0; i--) G[i] = G[i + 1] * (i + 1) % md;
	for(i = 1; i <= m; i++) {
		for(j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
			p[i][a[i][j]] = j;
		}
		a[i][n + 1] = p[i][n + 1] = n + 1;
	}
	ll ans = 0, tot;
	for(i = 1; i < m; i++) {
		for(k = 1; k <= n + 1; k++) sum[k] = p[i][k] - 1, s[k] = 1;
		for(k = 1; k <= n + 1; k++)
			for(l = 1; l < k; l++) if(p[i + 1][a[i][l]] < p[i + 1][a[i][k]]) q[a[i][k]].push(a[i][l]), Sum[a[i][k]][a[i][l]] = k - l - 1, S[a[i][k]][a[i][l]] = 1;
		for(j = i + 1; j <= m; j++) {
			for(h = 1; h <= n + 1; h++) {
				k = a[i][h];
				s[k] = s[k] * C(sum[k] + p[j][k] - 1, sum[k]) % md;
				sum[k] += p[j][k] - 1;
				f[k] = s[k] * F[j - i + 1] % md;
				x = q[k].size(), tot = 0;
				while(x--) {
					l = q[k].front();
					q[k].pop();
					S[k][l] = S[k][l] * C(Sum[k][l] + p[j][k] - p[j][l] - 1, Sum[k][l]) % md;
					Sum[k][l] += p[j][k] - p[j][l] - 1;
					tot += f[l] * S[k][l] % md;
					if(p[j + 1][l] < p[j + 1][k]) q[k].push(l);
				}
				f[k] = (f[k] - tot % md * F[j - i + 1] % md + md) % md;
			}
			ans += f[n + 1] * G[j - i + 1] % md;
		}
	}
	printf("%lld\n", ans % md);
	return 0;
}