loj 6077 「2017 山东一轮集训 Day7」逆序对
一个经典问题
我们一个一个加入元素,第i个贡献的逆序对数量在区间\([0,i-1]\)内
问题也就是有多少个排列\(x\)满足:
\[\sum _{i}x_i=k\ |\ x_i\in [0,i-1] \]可以考虑容斥:
如果有j个不满足条件,也就是\(x_i\geq i\)
我们可以将不满足条件的\(x_i\)都减去\(i\)。
然后剩下的插板法分配。
对于一对\(i,j\)我们要知道有多少个排列\(p\)满足:
\[\begin{align*} & (1). |p|=i\\ & (2). \sum p_i=j\\ & (3). \forall k\in[2,i],p_{k}>p_{k-1}\\ & (4). \forall k,p_{k}\in [1,n] \end {align*} \]我们可以设\(dp_{i,j}\)表示满足条件\((i,j)\)的方案数。
有两种转移:
- 整体+1,\(dp_{i,j}\leftarrow dp_{i,j-i}\)
- 整体+1,然后在开头添加一个1:\(dp_{i,j}\leftarrow dp_{i-1,j-i}\)
这样我们就可以满足前三个限制了,第四个限制怎么办呢?
如果我们在恰好有一个元素\(>n\)的时候就将他减去,就会方便很多了。
则还有一个转移:
- \(dp_{i,j}\leftarrow -dp_{i-1,j-(n+1)}\)
可以发现\(i\leq \sqrt{n}\),所以时间复杂度为\(O(\sqrt n\times k)\)
/*
{
######################
# Author #
# Gary #
# 2020 #
######################
*/
#include <bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
//inline int read(){
// int x=0;
// char ch=getchar();
// while(ch<'0'||ch>'9'){
// ch=getchar();
// }
// while(ch>='0'&&ch<='9'){
// x=(x<<1)+(x<<3)+(ch^48);
// ch=getchar();
// }
// return x;
//}
const int INF = 0x3f3f3f3f;
typedef pair<int, int> mp;
/*}
*/
const int MOD = 1e9 + 7;
int n, k;
const int SQRT = 450;
const int MAXN = 1e5 + 20;
int dp[SQRT + 1][MAXN + 1]; //取了i个,和为j
int fact[MAXN + MAXN];
LL quick(LL A, LL B) {
if (B == 0)
return 1;
LL tmp = quick(A, B >> 1);
tmp *= tmp;
tmp %= MOD;
if (B & 1)
tmp *= A, tmp %= MOD;
return tmp;
}
int inv(int x) {
return quick(x, MOD - 2);
}
void add(int &A, int B) {
A += B;
if (A >= MOD)
A -= MOD;
}
int c(int A, int B) {
return 1ll * fact[A] * inv(fact[B]) % MOD * inv(fact[A - B]) % MOD;
}
int main() {
scanf("%d%d", &n, &k);
dp[0][0] = 1;
rb(i, 1, SQRT) {
rb(j, i, k) {
dp[i][j] = (dp[i][j - i] + dp[i - 1][j - i]) % MOD;
if (j > n) {
add(dp[i][j], MOD - dp[i - 1][j - (n + 1)]);
}
}
}
fact[0] = 1;
rb(i, 1, 200000) {
fact[i] = 1ll * fact[i - 1] * i % MOD;
}
int rest = 0;
rb(i, 0, k) {
int tmp = c(k - i + n - 1, n - 1);
rb(j, 0, SQRT) {
int have = 1ll * tmp * dp[j][i] % MOD;
if (j & 1) {
have = MOD - have;
}
add(rest, have);
}
}
cout << rest << endl;
return 0;
}