【ybtoj高效进阶 21277】逆序对数(数学)(DP)
逆序对数
题目链接:ybtoj高效进阶 21277
题目大意
问你有多少个长度为 n 的排列的逆序对个数是 n。
思路
你考虑不断加入越来越大的数,那每次给逆序对个数的贡献区间就是
0
∼
i
−
1
0\sim i-1
0∼i−1。
总的来讲,每次贡献的上界是
1
,
2
,
.
.
,
n
−
1
1,2,..,n-1
1,2,..,n−1。
然后 DP 当然会超时,考虑小小容斥一下。
考虑到要的个数和是
n
n
n,相对
n
(
n
+
1
)
/
2
n(n+1)/2
n(n+1)/2 很小,考虑从这里下手。
设
f
i
,
j
f_{i,j}
fi,j 为有至少
i
i
i 个超过限制,当前的和是
j
j
j 的方案数。
那不难想到答案就是容斥一下,如果
i
i
i 是奇数对答案的贡献就是负的,否则是正的。
那当然这个是排好序的,剩下的部分没有排序,我们就直接暴力出来
n
−
i
n-i
n−i 个位置。
根据插板法:
C
(
n
−
1
)
+
n
−
1
n
−
1
C^{n-1}_{(n-1)+n-1}
C(n−1)+n−1n−1
考虑每次新放一个数,放不超过限制的还是超过限制的。
然后你考虑怎么一搞:把所有数都加一个,然后再前面放
1
1
1 或者
2
2
2。
那每次增加的就是
i
i
i 或者
i
+
1
i+1
i+1。
而且从
i
,
j
i,j
i,j,不超过限制就是转移到
i
,
j
+
i
i,j+i
i,j+i,超过限制就是转移到
i
+
1
,
j
+
i
+
1
i+1,j+i+1
i+1,j+i+1。
然后搞一搞即可。
代码
#include<cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
int n;
ll f[501][100001], jc[200001], inv[200001];
ll get_c[100001], ans;
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
ll C(int x, int y) {
if (x < y) return 0;
return jc[x] * inv[y] % mo * inv[x - y] % mo;
}
int main() {
// freopen("pairs.in", "r", stdin);
// freopen("pairs.out", "w", stdout);
scanf("%d", &n);
jc[0] = 1;//预处理
for (int i = 1; i <= 2 * n; i++) jc[i] = jc[i - 1] * i % mo;
inv[2 * n] = ksm(jc[2 * n], mo - 2);
for (int i = 2 * n - 1; i >= 0; i--)
inv[i] = inv[i + 1] * (i + 1) % mo;
for (int i = 0; i <= n; i++)
get_c[i] = C(i + n - 1, n - 1);
ans = get_c[n];
f[1][1] = 1;
for (int j = 1; j * (j + 1) / 2 <= n; j++)//DP
for (int i = 1; i <= n; i++) {
if (j & 1) ans = (ans + mo - f[j][i] * get_c[n - i] % mo) % mo;
else ans = (ans + f[j][i] * get_c[n - i] % mo) % mo;
if (i + j <= n) f[j][i + j] = (f[j][i + j] + f[j][i]) % mo;
if (i + j < n) f[j + 1][i + j + 1] = (f[j + 1][i + j + 1] + f[j][i]) % mo;
}
printf("%lld", ans);
return 0;
}
相关文章
- 2021Android目前最稳定和高效的UI适配方案!附赠课程+题库
- 解读建筑建材行业市场运行形势,用“互联网”理念谋划高效运转的产业生态链
- Android一种高效压缩图片的方法
- ConcurrentQueue<T>高效的线程安全的队列
- 【ybt高效进阶6-3-3】线性求逆元(数学)
- 【ybt高效进阶3-4-1】【luogu P3387】有向图缩点 / 【模板】缩点
- 【ybt金牌导航1-1-1】【ybt高效进阶6-6-3】路径长度
- 【ybt高效进阶6-1-1】序列的第k个数(快速幂)
- 【YBTOJ高效进阶 21190】【ybt金牌导航8-4-6】欧拉函数 / 函数求和(数学)(DP)
- 【ybtoj高效进阶 21286】等差数列(数学)(分类讨论)
- 【ybtoj高效进阶 21262】头文字 D(线段树)(数学)
- 【ybt高效进阶6-4-3】【luogu P2480】古代猪文(数学)(EXCRT / CRT)(Lucas定理)(欧拉定理)
- 【ybt高效进阶6-3-3】线性求逆元(数学)
- 【ybt高效进阶6-3-2】约数之和(逆元)(数学)
- 【ybt高效进阶6-2-3】不定方程(数学)
- 【ybt高效进阶6-5-2】数字游戏(博弈论)
- 【ybt高效进阶强化训练1-1-5】国际象棋(DP)(高精)
- 【ybt高效进阶1-1-4】【luogu P1057】传球游戏
- 【ybt高效进阶5-2-2】【luogu P4170】木板涂色 / 涂色
- 【YBTOJ高效进阶 21189】最短距离(最短路)(最小生成树)
- 【ybt高效进阶3-3-4】【luogu P4009】汽车加油 / 汽车加油行驶问题
- 【ybt高效进阶3-1-4】【luogu P2024】食物链
- 【ybtoj高效进阶 21186】道路航线(二分)(bfs)
- 【ybt高效进阶1-5-5】电路维修
- 【ybt高效进阶2-5-4】屏蔽词删除
- 【ybt高效进阶2-1-3】单词替换
- 【高效开发工具系列】maven学习