K-Inversion Permutations 题解

I have no reason for giving up.

link
一道不错的题。
先考虑 \(n^2\) 做法,比较显然,将数字从小到大插入,直接做 dp 即可。
我们将上面的插入过程抽象化。记 \([l,r]\) 为在 \(l\sim r\) 中选一个数。
则即求:\(\sum_{i=1}^n[0,i-1]=k\) 的方案总数。发现这就是一个多重集排列的板子。(多重集排列例题
但是暴力容斥时间会直接飞起来。但你考虑我们容斥 dfs 搜完总和为 \(s\),那么贡献就要改变 \(f*\binom {n-1} {n-1+k-s}\)。既然式子都写得出来,何必爆搜算?我们能不能直接合并同类项呢?
所以现在我们的问题就转化为了如何快速求出在 \(0\sim n-1\) 中选数,使其总和为 \(s\) 的总贡献。其中如果有偶数个数,系数为 \(1\),否则为 \(-1\)。
考虑 dp,设 \(dp[i][j]\) 为选了 \(i\) 个数,总和为 \(j\) 的方案。发现这里的第一维 \(\le 2\sqrt s\)。(因为最小为 \(0+1+2+3+...\))
考虑一个很套路的转移,每次我们要么使当前选的数加 \(1\),要么新加入一个 \(0\),再全部加 \(1\)。可以证明这样弄出来的序列是单调递减的。这里运用了 dp 中直接构造答案序列的思想。
那么如果不考虑这个最大选的数 \(\le n\) 的限制,我们会容易地得到方程式:\(dp[i][j]=dp[i-1][j-i]+dp[i][j-i]\)。
考虑这个限制,发现 dp 中我们不方便快速地得到第一个数(即最大的数)\(>n\) 的数量。
但最方便地,肯定是想在最大值成为 \(n+1\) 时就将这种情况灭了。那么如果第一个数为 \(n+1\),有多少种方案?发现方案数为 \(dp[i-1][j-(n+1)]\),即我限制第一个必须为 \(n+1\),剩下的必须 \(\le n\),分配 \(j-(n+1)\) 个数,刚好符合 \(dp[i-1][j-(n+1)]\) 的定义。
则 \(dp[i][j]=dp[i][j]=dp[i-1][j-i]+dp[i][j-i]-dp[i-1][j-(n+1)]\)。
然后处理出 dp 后直接容斥即可。
时间复杂度:\(\mathcal {O}(n\sqrt n)\)。

#include <algorithm>
#include <cmath>
#include <cstring>
#define LL long long
using namespace std;
const int MAXN = 1e5 + 5, Mod = 1e9 + 7;
int n, k, dp[800][MAXN], t, jc[MAXN << 1], inv[MAXN << 1], ans;
int Qpow(int x, int y) {
	int ans = 1;
	for(; y; y >>= 1) {
		if(y & 1) ans = (LL)ans * x % Mod;
		x = (LL)x * x % Mod;
	}
	return ans;
} 
int C(int x, int y) { return x < y ? 0 : (LL)jc[x] * inv[y] % Mod * inv[x - y] % Mod; }
int main() {
	scanf("%d%d", &n, &k); t = 2 * sqrt(k); jc[0] = 1;
	for(int i = 1; i <= n + k; i ++) jc[i] = (LL)jc[i - 1] * i % Mod; 
	inv[n + k] = Qpow(jc[n + k], Mod - 2);
	for(int i = n + k - 1; i >= 0; i --) inv[i] = (LL)inv[i + 1] * (i + 1) % Mod;
	dp[0][0] = 1;
	for(int i = 1; i <= t; i ++) {
		for(int j = 1; j <= k; j ++) {
			if(j >= i) dp[i][j] += dp[i][j - i];
			if(dp[i][j] >= Mod) dp[i][j] -= Mod;
			if(j >= i) dp[i][j] += dp[i - 1][j - i];
			if(dp[i][j] >= Mod) dp[i][j] -= Mod;
			if(j >= n + 1) dp[i][j] = (dp[i][j] - dp[i - 1][j - n - 1] + Mod) % Mod;
		}
	}
	for(int i = 0; i <= t; i ++) {
		for(int j = 0; j <= k; j ++) {
			ans = (ans + ((i & 1) ? -1 : 1) * dp[i][j] * (LL)C(n - 1 + k - j, n - 1)) % Mod;
		}
	}
	printf("%d", (ans + Mod) % Mod);
	return 0;
}
上一篇:#每日一读 字典反转


下一篇:c语言typedef关键字的理解