题解：P9004 [RC-07] Abnormal Permutation Tuples
Shellchen
·
·
题解
这题竟然是多项式复杂度的没想到吧。
打一个 n=4 的表。把所有的排列按字典序排序，逆序对是这样的：
0 1 1 2 2 3 1 2 2 3 3 4 2 3 3 4 4 5 3 4 4 5 5 6
可以注意到这玩意能写成这样：
0 1 1 2 2 3/1 2 2 3 3 4/2 3 3 4 4 5/3 4 4 5 5 6
分成这样四块，可以发现每块都是几乎一样的，只是分别加上了 0,1,2,3，很明显是排列第一位对逆序对数的贡献。并且第一个块是 n=3 的表。
直接考虑 DP，设 dp_{i,a,b,c,j} 表示 i 阶排列，选择的排列序列开头的逆序对数是 a，结尾是 b，总共有 c 个排列，且当前考虑到排列的第 j 个块。
那么可以把前面的和当前块拼起来，有转移（有点长我就放行间公式了）：
dp_{i,a,e,c+f,j}\gets dp_{i,a,b,c,j-1}\times dp_{i-1,d-j+1,e-j+1,f,i-1}[b>d]
其中 d,e,f 是枚举的，表示当前块的最大值和最小值，以及个数。
:::info[对转移式的解释]
两个序列拼在一起，最大值显然是 a 最小值显然是 e 因为序列的逆序对数是降序的。排列个数显然是 c+f。
:::
同时，序列可以直接在这个块开头，前面没有东西。
$$
dp_{i,d,e,c+f,j}\gets dp_{i-1,d-j+1,e-j+1,f,i-1}
$$
解释和上面类似。
$j$ 显然可以滚动数组掉，DP 数组可以少一维。
$i,j$ 是 $O(n)$ 的，$a,b,d,e$ 是 $O(n^2)$，$c,f$ 是 $O(m)$，全部乘起来可以得到复杂度 $O(n^{10}m^2)$。显然是过不了的。
发现你还可以前缀和优化掉 $b$，复杂度变成了 $O(n^8m^2)$。然后你会发现这个东西常数极其小，随便剪枝一下就过了！具体可以看代码。
洛谷机子比较慢，可能卡常会比较难受。
:::success[code]
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned int
#define inf 1e18
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf 1e9
#define infl 1e18
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
#define fileio(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N=1e6+10,mod=1e9+7;
int n,m,p;
int ff[25][110][110][35];//i 阶排列，以几个逆序对数开头，几个逆序对数结尾的几链数量
int g[25][110][110][35];
int ss[25][110][110][35];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m>>p;
ff[1][0][0][1]=1;
for(int i=2;i<=n;i++)
{
int s=i*(i-1)/2,t=(i-1)*(i-2)/2;
for(int j=1;j<=i;j++)
{
memset(g[i],0,sizeof(g[i]));
for(int d=j-1;d<s;d++) for(int f=1;f<m;f++)
for(int e=j-1;e<=d;e++) if(ff[i-1][d-j+1][e-j+1][f])
for(int c=1;c+f<=m;c++) for(int a=d+1;a<=s;a++) if(ss[i][a][a][c]!=ss[i][a][d][c])
(g[i][a][e][f+c]+=(ss[i][a][a][c]-ss[i][a][d][c]+p)*ff[i-1][d-j+1][e-j+1][f])%=p;
for(int d=j-1;d<=t+j-1;d++) for(int e=j-1;e<=d;e++) for(int f=1;f<=m;f++)
g[i][d][e][f]+=ff[i-1][d-j+1][e-j+1][f];
for(int d=0;d<=s;d++) for(int e=0;e<=d;e++) for(int f=1;f<=m;f++)
(ff[i][d][e][f]+=g[i][d][e][f])%=p;
for(int a=0;a<=s;a++) for(int c=1;c<=m;c++) ss[i][a][0][c]=ff[i][a][0][c];
for(int a=0;a<=s;a++) for(int b=1;b<=a;b++) for(int c=1;c<=m;c++) ss[i][a][b][c]=(ss[i][a][b-1][c]+ff[i][a][b][c])%p;
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
int ans=0;
for(int a=0;a<=i*(i-1)/2;a++) for(int b=0;b<=a;b++) (ans+=ff[i][a][b][j])%=p;
cout<<ans<<" \n"[j==m];
}
return 0;
}
```
:::