我是容斥低低手,该训容斥了。
题意:给出 \(n\),计算对于 \(x,y\in[0,n)\),有多少个排列满足:
\[\sum_{i=1}^{n-1}[p_i<p_{i+1}] = x
\]
\[\sum_{i=1}^{n-1}[p_{i}^{-1}<p_{i+1}^{-1}] = y
\]
\(n\le 500\)。
做法:
考虑只有一个限制我们应该用容斥做一做,很经典的求欧拉数。
两个限制怎么做?我们考虑还是在排列和逆排列中钦定 \(i,j\) 个上升得到 \(f_{i,j}\) 种排列,然后对两位分别容斥得到答案。
现在就是我至少有这么多个上升怎么做,考虑至少 \(i\) 个上升转化成至多 \(n-i\) 个上升连续段。每次我们加入逆排列中的第 \(k\) 个连续段,那么对于我原排列的每个连续段应该都加入了一个前缀,假设对第 \(l\) 个连续段加入了 \(a_{k,l}\) 个数,那么就意味着,如果我能确定一个 \(a\),那么我就可以唯一确定一个排列。
那么接下来就很简单了,我们知道 \(a\) 中所有元素的和为 \(n\),同时不能出现一行或者一列为 \(0\),直接容斥就可以了。钦定有多少个行列为 \(0\) 然后组合数算一算就可以。
具体的容斥细节见代码。
复杂度 \(O(n^3)\)。
代码(因为写这个容斥思路特别混乱所以容斥的顺序相当神秘,直接贺了别人的实现):
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 505;
int dp[4][maxn][maxn], mod, C[maxn * maxn], t[maxn], Comb[maxn][maxn];
int n;
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p, k >>= 1;}return res;
}
int add(int x, int y) {x = x + y;if(x < mod)x += mod;if(x >= mod)x -= mod;return x;
}
signed main() {cin >> n >> mod;C[0] = 1;for (int i = 1; i <= n * n; i++)C[i] = C[i - 1] * (i + n) % mod * qpow(i, mod - 2, mod) % mod;Comb[0][0] = 1;for (int i = 1; i <= n; i++) {Comb[i][0] = 1;for (int j = 1; j <= i; j++)Comb[i][j] = add(Comb[i - 1][j - 1], Comb[i - 1][j]);}for (int i = 1; i <= n; i++) { // 枚举多少个行for (int j = 1; j <= n; j++) // 枚举多少个列t[j] = C[i * j - 1];// 有可能有更多的空列for (int j = 0; j < n; j++) { // 枚举多少个上升int tp = n - j; // 实际有多少个上升段for (int k = 0; k <= tp; k++) dp[0][i][j] = add(dp[0][i][j], (((tp - k) & 1) ? -1 : 1) * Comb[tp][k] * t[k] % mod);}}for (int i = 1; i <= n; i++) for (int j = 0; j < n; j++) // 先把列的答案直接容斥掉,有这么多连续上升段,但是段之间可能存在上升for (int k = 0; k <= j; k++) dp[1][i][k] = add(dp[1][i][k], (((j - k) & 1) ? -1 : 1) * Comb[j][k] * dp[0][i][j] % mod);for (int i = 0; i < n; i++) // 列for (int j = 1; j <= n; j++) // 行for (int k = j; k <= n; k++) // 扔掉空行dp[2][k][i] = add(dp[2][k][i], (((k - j) & 1) ? -1 : 1) * Comb[k][j] * dp[1][j][i] % mod);for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) // 上升段转上升个数,同时容斥更多的for (int k = 0; k <= j; k++) dp[3][k][i] = add(dp[3][k][i], (((j - k) & 1) ? -1 : 1) * Comb[j][k] * dp[2][n - j][i] % mod);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cout << dp[3][i][j] << (j == n - 1 ? '\n' : ' ');return 0;
}