mzx 的动态规划杂题选讲。sto
ARC153 D - Sum of Sum of Digits
P7152 [USACO20DEC] Bovine Genetics G
CF1542E2 Abnormal Permutation Pairs (hard version)
题意
给定 \(n,m\)，求有多少对长度为 \(n\) 的排列 \(p,q\)，满足以下条件：
-
\(p\) 的字典序小于 \(q\)；
-
\(p\) 的逆序对个数 严格大于 \(q\)；
答案对 \(m\) 取模。\(1\le n\le 500\)，\(1\le m\le 10^9\)，不保证 \(m\) 为素数。
解法
发现这个题需要满足的条件有两个，直接一起做的话很困难，可以先思考满足其中一个条件时怎么做。
发现求的 \(p,q\) 是一个排列，而排列有一个很好的性质：在删去一些数后，因为我们只关心它们的相对大小关系，所以剩下的数也可以看做一个排列，这就是一个子问题了。
-
只用满足第一个条件：
- 这个字典序的限制很经典，可以枚举前多少位相同，前面的一样，后面的随便选。
-
只用满足第二个条件：
-
定义 \(f_{i,j}\) 表示有多少个 \(i\) 的排列刚好有 \(j\) 个逆序对。
-
如果你枚举每个位置放哪个数，就需要在状态中记录一个指数级别的维度表示哪些数被选了，这并不利于我们的转移；
-
考虑把这个看做在一个 \(i-1\) 的排列中插入一个 \(i\)。如果插在第 \(k\) 个数之后，就会增加 \(i-1-k\) 个逆序对。转移就是 \(f_{i,j}=\sum\limits_{k=0}^{i-1}f_{i-1,j-(i-1-k)}\)。这个转移是从连续的一段转过来的，可以前缀和优化，时间复杂度 \(O(n^3)\)。
-
现在我们同时考虑两个条件。假设 \(p,q\) 的前 \(i-1\) 位相同。此时，排列可以分成三部分：前 \(i-1\) 位，第 \(i\) 位，后 \(n-i\) 位。注意到 \(p,q\) 第一部分完全相同，所以其与二三部分的逆序对数相同，可以忽略。因此，我们需要考虑的逆序对数只由两部分构成：
-
第 \(i\) 位与后 \(n-i\) 位间的逆序对；
-
后 \(n-i\) 位中的逆序对；
因为排列的性质，后 \(n-i+1\) 位已经是独立的了。
-
假设 \(p,q\) 第 i 位填的是 \(k_1,k_2\)，则 \(p\) 就比 \(q\) 少了 \(k_2-k_1\) 个逆序对。
-
令 \(d=k_2-k_1\)，因为在取出第 \(i\) 位填的数后后 \(n-i\) 位与 \(i\) 位填的数的值没有关系，而逆序对数量只需要满足 \(p\) 比 \(q\) 多至少 \(d\) 个，我们只用枚举第 \(i\) 位的差值 \(d\)。此时，设 \(p\) 第三部分的逆序对数位 \(j\)，则 \(q\) 可选的方案共有 \(\sum\limits_{k=0}^{j-d-1}f_{n-i,k}\) 种。
整理一下，答案就是
\[ans=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{d=1}^{n-i}(n-i-d+1)\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}\sum\limits_{k=0}^{j-d-1}f_{n-i,k} \]其中 \(A_n^{i-1}\) 表示排列数。
这是一个 \(O(n^6)\) 的柿子，我们考虑优化。记 \(g_{i,j}=\sum\limits_{k=0}^jf_{i,k}\)，\(s_{i,j}=\sum\limits_{k=0}^jk\times g_{i,k}\)，\(t_{i,j}=\sum\limits_{k=0}^jg_{i,k}\)。
\[\begin{align} ans&=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{d=1}^{n-i}(n-i-d+1)\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}\sum\limits_{k=0}^{j-d-1}f_{n-i,k}\\ &=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{d=1}^{n-i}(n-i-d+1)\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}g_{n-i,j-d-1}\\ &=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}\sum\limits_{d=1}^{n-i}(n-i-d+1)g_{n-i,j-d-1}\\ &=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}\sum\limits_{d=1}^{n-i}[(j-d-1)+(n-i-j+2)]g_{n-i,j-d-1}\\ &=\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}(n-i-j+2)f_{n-i,j}\sum\limits_{d=1}^{n-i}g_{n-i,j-d-1}+\sum\limits_{i=1}^{n}A_n^{i-1}\sum\limits_{j=0}^{\frac{(n-i)(n-i-1)}{2}}f_{n-i,j}\sum\limits_{d=1}^{n-i}(j-d-1)g_{n-i,j-d-1}\\ \end{align} \]发现前面可以用 \(t\) 数组优化，后面可以用 \(s\) 数组优化。总时间复杂度 \(O(n^3)\)。
\(n^3\) 的数组开不下，需要一边求 \(f,g,s,t\) 的同时统计答案。
实际操作时需要考虑越界等无解的情况，处理比较繁琐，建议分段运算。
code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int n,p,ans,dm[505][505],f[200005],g[200005],s[200005],t[200005];
int askG(int l,int r){
if(l>r)return 0;
if(r<0)return 0;
if(l-1<0)return g[r];
else return (g[r]-g[l-1]+p)%p;
}
int askS(int l,int r){
if(l>r)return 0;
if(r<0)return 0;
if(l-1<0)return s[r];
else return (s[r]-s[l-1]+p)%p;
}
int askT(int l,int r){
if(l>r)return 0;
if(r<0)return 0;
if(l-1<0)return t[r];
else return (t[r]-t[l-1]+p)%p;
}
signed main(){
n=read(),p=read();
for(int i=0;i<=n;i++){
dm[i][0]=1;
for(int j=1;j<=i;j++)dm[i][j]=dm[i][j-1]*(i-j+1)%p;
}
f[0]=1,g[0]=1,s[0]=0,t[0]=1;
for(int i=0;i<=0;i++){
for(int j=0;j<=i+1;j++){
ans=(ans+dm[n][n-i-1]*f[j]%p*askS(0,j-2)%p)%p;
}
for(int j=0;j<=i+1;j++){
ans=(ans+dm[n][n-i-1]*(i-j+2)%p*f[j]%p*askT(0,j-2)%p)%p;
}
for(int j=i+2;j<=i*(i-1)/2;j++){
ans=(ans+dm[n][n-i-1]*f[j]%p*askS(-i+j-1,j-2)%p)%p;
}
for(int j=i+2;j<=i*(i-1)/2;j++){
ans=(ans+dm[n][n-i-1]*(i-j+2)%p*f[j]%p*askT(-i+j-1,j-2)%p)%p;
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=i*(i-1)/2;j++){
f[j]=askG(j-i+1,j);
}
g[0]=f[0];
for(int j=1;j<=(i+1)*((i+1)-1)/2;j++){
g[j]=(g[j-1]+f[j])%p;
}
s[0]=0*g[0];
for(int j=1;j<=(i+1)*((i+1)-1)/2;j++){
s[j]=(s[j-1]+j*g[j]%p)%p;
}
t[0]=g[0];
for(int j=1;j<=(i+1)*((i+1)-1)/2;j++){
t[j]=(t[j-1]+g[j])%p;
}
if(i<n){
for(int j=0;j<=i+1;j++){
ans=(ans+dm[n][n-i-1]*f[j]%p*askS(0,j-2)%p)%p;
}
for(int j=0;j<=i+1;j++){
ans=(ans+dm[n][n-i-1]*(i-j+2)%p*f[j]%p*askT(0,j-2)%p)%p;
}
for(int j=i+2;j<=i*(i-1)/2;j++){
ans=(ans+dm[n][n-i-1]*f[j]%p*askS(-i+j-1,j-2)%p)%p;
}
for(int j=i+2;j<=i*(i-1)/2;j++){
ans=(ans+dm[n][n-i-1]*(i-j+2)%p*f[j]%p*askT(-i+j-1,j-2)%p)%p;
}
}
}
printf("%lld\n",(ans+p)%p);
return 0;
}
总结
-
对于多条件计数问题，通过分类讨论，枚举等方式降低条件的耦合度，独立解决低耦合度的问题并合并成最终问题的答案；
-
设计动态规划时要 考虑阶段本身的转移是否容易，本题转化后的基本问题中，如果按下标位置动态规划，阶段转移需要知道前面比该位置小的数的个数，需要记录的状态为指数级。如果按值的大小从小到大动态规划，转移时只需要枚举当前的数放在当前的哪个下标，需要记录的状态数为常数级；
-
看推柿子的思路；