描述
题解
乍一看,逆序数,差点不分青红皂白的就要写归排,还好收住了势头,仔细一看,是dp,然而,我看得出事dp,却因为自己dp用的不够灵活而始终推不出……
看了相关讨论中Cppowboy的题解,顿悟,好牛逼的说,赞一下~~~
设f(n,k)表示n个数的排列中逆序数个数为k的排列数。
最大的数n可能会排在第n-i位,从而产生i个与n有关的逆序对,去掉n之后,剩下的n-1个数的排列有k-i个逆序对。
所以,
f(n, k) = sum(f(n - 1, k - i))(0 <= i < n)
同理有,
f(n, k - 1) = sum(f(n - 1, k - 1 - i))(0 <= i < n)
两式相减,可得,
f(n, k) - f(n, k - 1) = f(n - 1, k) - f(n - 1, k - n)
递推公式为,
f(n, k) = f(n, k - 1) + f(n - 1, k) - f(n - 1, k - n)
然后动态规划可得。
碉堡了,这里需要注意的是,可以1000 * 20000
是可以开出来的,但是因为我一开始逗逼了直接开的long long
数组,所以爆内存了,改成int
就好了,想进一步优化可以改成滚动数组。
代码
#include <iostream>
using namespace std;
const int MAXN = 1e3 + 10;
const int MAXK = 2e4 + 10;
const int MOD = 1e9 + 7;
int dp[MAXN][MAXK]; // dp[n][k]表示n个数的排列中逆序数个数为k的排列数
void init()
{
// 逆序数为0的排列为正序
for (int i = 1; i < MAXN; i++)
{
dp[i][0] = 1;
}
for (int i = 2; i < MAXN; i++)
{
int up = i * (i - 1) / 2;
for (int j = 1; j <= up && j < MAXK; j++)
{
dp[i][j] = ((dp[i][j - 1] + dp[i - 1][j] - (j - i >= 0 ? dp[i - 1][j - i] : 0)) % MOD + MOD) % MOD;
}
}
}
int main(int argc, const char * argv[])
{
init();
int T;
cin >> T;
int n, k;
while (T--)
{
cin >> n >> k;
cout << dp[n][k] << '\n';
}
return 0;
}