怎么会有这么离谱的题目啊。
【模板】前缀和优化 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;
}