怎么会有这么离谱的题目啊。
【模板】前缀和优化 dp。
思路
考虑一个基本的东西。
由于要求字典序的限制。
我们可以枚举最长公共前缀计算。
考虑如何求长度为 \(i\) 的排列有 \(j\) 个逆序对的数量。
设 \(dp_{i,j}\)。
\[dp_{i,j}=\sum_{k=0}^{i-1}dp_{i-1,j-k}
\]
就是枚举新的数放在那里。
不难看出可以前缀和优化。
\[dp_{i,j}=g_{i-1,j-k}-g_{i-1,j-i}
\]
就可以 \(O(n^3)\) 计算。
到这里都是比较简单的。
考虑如何算答案。
首先列出较为朴素的 \(\text{dp}\)。
枚举最长公共前缀长度 \(i\)，第 \(i+1\) 位两个排列分别放 \(x,y\)，后面 \(n-i-1\) 位分别会有 \(s,t\) 个逆序对。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{x=1}^n\sum_{y=x+1}^{n-i}\sum_{s=0}^{\binom{n-i+1}{2}}\sum_{t=0}^{\binom{n-i+1}{2}}[s+x-1>t+y-1] dp_{n-i-1,s}\times dp_{n-i-1,t}
\]
稍微整理一下。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{x=1}^n\sum_{y=x+1}^{n-i}\sum_{s=0}^{\binom{n-i+1}{2}}\sum_{t=0}^{s+x-y-1}dp_{n-i-1,s}\times dp_{n-i-1,t}
\]
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{x=1}^n\sum_{y=x+1}^{n-i}\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\sum_{t=0}^{s+x-y-1}dp_{n-i-1,t}
\]
发现又可以前缀和优化。
设 \(g_{i,j}=\sum_{k=0}^j dp_{i,j}\)。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{x=1}^n\sum_{y=x+1}^{n-i}\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\times g_{n-i-1,s+x-y-1}
\]
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\sum_{x=1}^n\sum_{y=x+1}^{n-i}g_{n-i-1,s+x-y-1}
\]
这个时候，我发现了后面只与 \(x-y\) 有关，那么可以枚举 \(x-y=j\)。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\sum_{j=1}^{n-i-1}(n-i-j)\times g_{n-i-1,s+x-y-1}
\]
这个式子已经可以 \(O(n^4)\) 算了，可以通关简单版本。
但如何把它优化成 \(O(n^3)\)，我确实没有想到，如果有大佬会，可以教教我。
然后就发现我们走了很没有前途的一步，我也在这里卡了很久。
那么我们不得不往回退一步。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\sum_{x=1}^{n-i}\sum_{y=x+1}^{n-i}g_{n-i-1,s+x-y-1}
\]
我们考虑继续前缀和优化。
设 \(h_{i,j}=\sum_{k=0}^jg_{i,k}\)。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}\sum_{x=1}^{n-i}h_{n-i-1,s-2}-h_{n-i-1,s+x-n+i-1}
\]
发现这玩意还可以前缀和优化。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}((n-i)\times h_{n-i-1,s-2}-\sum_{x=1}^{n-i}h_{n-i-1,s+x-n+i-1})
\]
设 \(f_{i,j}=\sum_{k=0}^jh_{i,k}\)。
设 \(l=s+i-n-1,r=s-2\)。
\[\sum_{i=0}^{n-1}\binom{n}{i}i!\sum_{s=0}^{\binom{n-i+1}{2}}dp_{n-i-1,s}((n-i)\times h_{n-i-1,s-2}-(f_{n-i-1,r}-f_{n-i-1,l-1}))
\]
然后就做完了。
可能有一些边界情况需要来判断。
Code
/**
* @file 1542E1.cpp
* @author mfeitveer
* @date 2023-11-14
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 510;
const int M = 124760;
int n, m, mod, c[N][N], vis[N][N], g[M], h[M], f[M], dp[N][M];
inline int add(int x, int y)
{ return x + y + (x + y >= mod ? -mod : 0); }
inline void init(int now)
{
fro(j, 0, 124750) g[j] = dp[now][j];
fro(j, 1, 124750) g[j] = add(g[j], g[j - 1]);
fro(j, 0, 124750) h[j] = g[j];
fro(j, 1, 124750) h[j] = add(h[j], h[j - 1]);
fro(j, 0, 124750) f[j] = h[j];
fro(j, 1, 124750) f[j] = add(f[j], f[j - 1]);
}
inline int C(int x, int y)
{
if(x < y) return 0;
if(y == 0 || x == y) return 1;
if(vis[x][y]) return c[x][y]; vis[x][y] = 1;
return c[x][y] = (C(x - 1, y - 1) + C(x - 1, y)) % mod;
}
inline int ask(int l, int r)
{
if(l - 1 < 0) return g[r];
return (g[r] - g[l - 1] + mod) % mod;
}
inline void init()
{
dp[0][0] = 1;
fro(i, 1, 500)
{
init(i - 1);
fro(j, 0, 124750) dp[i][j] = ask(j - i + 1, j);
}
}
inline void solve()
{
i64 ans = 0, num = 1;
fro(i, 0, n - 1)
{
i64 res = 0; init(n - i - 1);
fro(s, 2, (n - i - 1) * (n - i - 2) / 2)
{
i64 res1 = 1ll * h[s - 2] * (n - i) % mod;
int ls = s + i - n - 1;
i64 res2 = f[s - 2] - (ls <= 0 ? 0 : f[ls - 1]);
res2 = (res2 % mod + mod) % mod;
(res += (res1 - res2 + mod) * dp[n - i - 1][s]) %= mod;
}
(ans += res * num) %= mod, num = num * (n - i) % mod;
}
cout << ans << endl;
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 1024;
assert(Mib<=Lim), cerr << " Memory: " << Mib << "\n";
cin >> n >> mod;
init(), solve();
return 0;
}
- 题解 Permutation Abnormal version 1542E题解permutation abnormal version 题解 前缀permutation abnormal permutation problem version 1909f permutation codeforces problem version 题解permutation 167d good 题解permutation another problem 题解permutation p7972 2021 题解permutation 213e two 线段 题解permutation separation 题解permutation oddness 134f