「Positions in Permutations」Solution

本文主要是介绍「Positions in Permutations」Solution，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简述题意

给定 $n,m$，对于一个长度为 $n$ 的排列 $p$，有函数：$$F(p)=\sum _{i=1}^n[\left|p_i-i\right|=1]$$求有多少个排列满足 $F(p)=m$，答案对 $10^9+7$ 取模。

• $1\le m\le n\le 10^3$

思路

看到这类 “恰好等于” 的问题，很自然想到二项式反演。不妨令 $f(i)$ 为 $F(p)\ge i$ 的方案数，令 $g(i)$ 为 $F(p)=i$ 的方案数，根据二项式反演得：

$$g(m)=\sum _{i=m}^{n}f(i)\times C_m^i\times -1^{i-m}$$

考虑如何求出 $f(i)$。注意到此题，$F(p)$ 实质是在统计有多少 $i$ 满足：$p_i=i+1$ 或 $p_i=i-1$。考虑去除排列的限制，即可以使用任意数任意次，那么显然有 $f(i)=C_n^i\times (n-i)!\times 2^i$。如果我们加上排列的限制，观察上述式子中的哪些情况变得不合法：

• $p_1=0$
• $p_n=n+1$
• $p_{i-1}=i$ 且 $p_{i+1}=i$

难点便在于该如何规避掉上述不合法的情况。假设我们钦定满足条件的 $i$ 组成的集合 $S$，那么我们只关心集合中的 $i$ 位置的取值，剩下未在集合中的位置（即有无贡献皆可）随意乱填即可。

注意到：如果我们处理到第 $i$ 个位置，且 $i$ 在我们钦定的集合 $S$ 里，那么我们只关心 $i-1$ 和 $i+1$ 这两个数在之前是否被选取，因为我们只能在 $i$ 位置上填这两个数。即，当前被使用掉的数，一定是某个 $i$ 加上 $1$ 或减去 $1$ 的结果。如果当前位置填 $i-1$，那么 $i+1$ 在之前一定未出现过，这启发我们 $\text{DP}$。

不妨令 $d{p}_{i,j,0/1,0/1}$ 表示处理到第 $i$ 个位置，钦定 $j$ 个位置满足条件，且 $i$ 是/否 被选取，$i+1$ 是/否 被选取的方案数。
注意：我们肯定不会定义 $i-1$ 是/否 出现，$i+1$ 是/否 出现这样的状态，否则会产生状态上的冲突，而且会漏掉很多情况。
考虑分类转移：

• 当前位置填 $i-1$，那么 $i+1$ 一定未被选取。
  $d{p}_{i,j,0,0}=d{p}_{i-1,j-1,0,0}$，$d{p}_{i,j,1,0}=d{p}_{i-1,j-1,0,1}$
• 当前位置填 $i+1$，$i-1$ 有可能被选取。
  $d{p}_{i,j,0,1}=d{p}_{i-1,j-1,0,0}+d{p}_{i-1,j-1,1,0}$，$d{p}_{i,j,1,1}=d{p}_{i-1,j-1,0,1}+d{p}_{i-1,j-1,1,1}$
• 当前位置不作贡献。
  $d{p}_{i,j,0,0}=d{p}_{i-1,j,0,0}+d{p}_{i-1,j,1,0}$，$d{p}_{i,j,1,0}=d{p}_{i-1,j,0,1}+d{p}_{i-1,j,1,1}$

注意边界条件：$d{p}_{1,0,0,0}=d{p}_{1,1,0,1}=1$。

暴力 $O(n^2)$ 转移得到 $dp$ 值，然后有：
$$f(i)=(d{p}_{n,i,0,0}+d{p}_{n,i,1,0})\times (n-i)!$$

得出 $f(i)$ 的值以后，套用二项式反演即可。

代码

#include<bits/stdc++.h>
#define int long long
const int MAXN = 1e3 + 5 , MOD = 1e9 + 7;
using namespace std;
int n , m , dp[MAXN][MAXN][2][2] , ans , jc[MAXN];
int qpow(int base , int k) {int res = 1;while(k) {if (k & 1) res = res * base % MOD;base = base * base % MOD;k >>= 1;}return res;
}
int inv(int x) {return qpow(x , MOD - 2);};
int C(int x , int y) {return jc[x] * inv(jc[y]) % MOD * inv(jc[x - y]) % MOD;}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr) , cout.tie(nullptr);cin >> n >> m;jc[0] = 1;for (int i = 1 ; i <= n ; i ++) jc[i] = jc[i - 1] * i % MOD;dp[1][0][0][0] = dp[1][1][0][1] = 1;for (int i = 2 ; i <= n ; i ++) {for (int j = 0 ; j <= i ; j ++) {// 选 i - 1dp[i][j][0][0] = dp[i - 1][j - 1][0][0] , dp[i][j][1][0] = dp[i - 1][j - 1][0][1];// 选 i + 1dp[i][j][0][1] = (dp[i - 1][j - 1][0][0] + dp[i - 1][j - 1][1][0]) % MOD , dp[i][j][1][1] = (dp[i - 1][j - 1][0][1] + dp[i - 1][j - 1][1][1]) % MOD;// 不产生贡献dp[i][j][1][0] = (dp[i][j][1][0] + dp[i - 1][j][0][1] + dp[i - 1][j][1][1]) % MOD;dp[i][j][0][0] = (dp[i][j][0][0] + dp[i - 1][j][0][0] + dp[i - 1][j][1][0]) % MOD;}}for (int i = m ; i <= n ; i ++) ans = (ans + (dp[n][i][1][0] + dp[n][i][0][0]) % MOD * jc[n - i] % MOD * C(i , m) % MOD * ((i - m & 1) ? -1 : 1) % MOD + MOD) % MOD; // 二项式反演cout << ans;return 0;
}

这篇关于「Positions in Permutations」Solution的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---