当前位置: 首页 > news >正文

题解:qoj7759 Permutation Counting 2

我是容斥低低手,该训容斥了。

题意:给出 \(n\),计算对于 \(x,y\in[0,n)\),有多少个排列满足:

\[\sum_{i=1}^{n-1}[p_i<p_{i+1}] = x \]

\[\sum_{i=1}^{n-1}[p_{i}^{-1}<p_{i+1}^{-1}] = y \]

\(n\le 500\)

做法:

考虑只有一个限制我们应该用容斥做一做,很经典的求欧拉数。

两个限制怎么做?我们考虑还是在排列和逆排列中钦定 \(i,j\) 个上升得到 \(f_{i,j}\) 种排列,然后对两位分别容斥得到答案。

现在就是我至少有这么多个上升怎么做,考虑至少 \(i\) 个上升转化成至多 \(n-i\) 个上升连续段。每次我们加入逆排列中的第 \(k\) 个连续段,那么对于我原排列的每个连续段应该都加入了一个前缀,假设对第 \(l\) 个连续段加入了 \(a_{k,l}\) 个数,那么就意味着,如果我能确定一个 \(a\),那么我就可以唯一确定一个排列。

那么接下来就很简单了,我们知道 \(a\) 中所有元素的和为 \(n\),同时不能出现一行或者一列为 \(0\),直接容斥就可以了。钦定有多少个行列为 \(0\) 然后组合数算一算就可以。

具体的容斥细节见代码。

复杂度 \(O(n^3)\)

代码(因为写这个容斥思路特别混乱所以容斥的顺序相当神秘,直接贺了别人的实现):

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 505;
int dp[4][maxn][maxn], mod, C[maxn * maxn], t[maxn], Comb[maxn][maxn];
int n;
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p, k >>= 1;}return res;
}
int add(int x, int y) {x = x + y;if(x < mod)x += mod;if(x >= mod)x -= mod;return x;
}
signed main() {cin >> n >> mod;C[0] = 1;for (int i = 1; i <= n * n; i++)C[i] = C[i - 1] * (i + n) % mod * qpow(i, mod - 2, mod) % mod;Comb[0][0] = 1;for (int i = 1; i <= n; i++) {Comb[i][0] = 1;for (int j = 1; j <= i; j++)Comb[i][j] = add(Comb[i - 1][j - 1], Comb[i - 1][j]);}for (int i = 1; i <= n; i++) { // 枚举多少个行for (int j = 1; j <= n; j++) // 枚举多少个列t[j] = C[i * j - 1];// 有可能有更多的空列for (int j = 0; j < n; j++) { // 枚举多少个上升int tp = n - j; // 实际有多少个上升段for (int k = 0; k <= tp; k++) dp[0][i][j] = add(dp[0][i][j], (((tp - k) & 1) ? -1 : 1) * Comb[tp][k] * t[k] % mod);}}for (int i = 1; i <= n; i++) for (int j = 0; j < n; j++)  // 先把列的答案直接容斥掉,有这么多连续上升段,但是段之间可能存在上升for (int k = 0; k <= j; k++) dp[1][i][k] = add(dp[1][i][k], (((j - k) & 1) ? -1 : 1) * Comb[j][k] * dp[0][i][j] % mod);for (int i = 0; i < n; i++)  // 列for (int j = 1; j <= n; j++)  // 行for (int k = j; k <= n; k++)  // 扔掉空行dp[2][k][i] = add(dp[2][k][i], (((k - j) & 1) ? -1 : 1) * Comb[k][j] * dp[1][j][i] % mod);for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)  // 上升段转上升个数,同时容斥更多的for (int k = 0; k <= j; k++) dp[3][k][i] = add(dp[3][k][i], (((j - k) & 1) ? -1 : 1) * Comb[j][k] * dp[2][n - j][i] % mod);for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cout << dp[3][i][j] << (j == n - 1 ? '\n' : ' ');return 0;
}
http://www.hskmm.com/?act=detail&tid=29133

相关文章:

  • WAV 转 flac 格式
  • EtherCAT芯片没有倍福授权的风险
  • 为何是「对话式」智能体?因为人类本能丨对话式智能体专场,Convo AIRTE2025
  • 2014-2024高考真题考点分布详细分析(另附完整高考真题下载) - 详解
  • P4147 玉蟾宫(最大子矩形)
  • 2025 年 10 月西安房屋鉴定公司最新推荐排行榜:覆盖房屋安全评估、结构检测、承载力鉴定、危房鉴定领域,助您选专业机构
  • 完整教程:HAProxy 完整指南:简介、负载均衡原理与安装配置
  • K
  • 阿里发布「夸克 AI 眼镜」:融合阿里购物、地图、支付生态;苹果拟收购计算机视觉初创 Prompt AI丨日报
  • 在AI技术唾手可得的时代,挖掘新需求成为制胜关键——某知名AI聊天框架需求探索
  • 数论学习之路
  • 生成式AI实现多模态信息检索技术突破
  • 在运维工作中,如何过滤某个目录在那边什么路径下面?
  • 完整教程:安卓中,kotlin如何写app界面?
  • 移动固态硬盘插入电脑后提示“应该格式化”或“文件系统损坏”如何修复?
  • PHP 15 个高效开发的小技巧
  • AI元人文构想研究:人类拥抱AI的文明新范式
  • 【汇编】汇编语言运行过程
  • 电感式传感器 - 实践
  • CSP-J/S2024第二轮提高级题目知识构成分析报告
  • 浅层 CNN 的瓶颈:用 LeNet 实测不同数据集
  • 文本派 - 停服公告 2025
  • lCode题库
  • Arista cEOS 4.35.0F 发布 - 针对云原生环境设计的容器化网络操作系统
  • Arista vEOS 4.35.0F 发布 - 虚拟化的数据中心和云网络可扩展操作系统
  • 因果机器学习的技术发展与挑战
  • CSP-S 考前集训
  • Arista EOS 4.35.0F 发布 - 适用于下一代数据中心和云网络的可扩展操作系统
  • 20251011 总结
  • 上课讲的部分 qoj 题记录