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

题解:uoj961【UR #30】赛场设计

很 educational 的题。

题意:给出一个数 \(n\) 和模数,问有多少个 \(n\) 个点的有向图,满足图中无环,且不存在 \(a,b,c\) 满足 \(a\) 不可以到 \(b\)\(b\) 不可以到 \(c\)\(c\) 不可以到 \(a\)

做法:

正着可能可以对这样的图进行描述,但是相当麻烦,我们考虑对不可达关系进行建边,发现这样得到的图比竞赛图还要强,并且和原图是一一对应的,竞赛图的一些性质还在这个图上符合:

  1. 缩点之后是条链。

  2. 点数 \(> 2\) 的强连通分量一定有三元环。

而这个图上的三元环就是原题中的需要满足不存在的条件,所以就要求这个新图缩点后的每个 scc 大小都要 \(\le 2\)

那么考虑 dp,\(dp_{i,j}\) 代表用了 \(i\) 个点,上一个 scc 的大小为为 \(j\) 的,我们这里为了方便,同时除掉了 \(n!\)\(2^{\frac{n(n-1)}2}\),直接转移即可,记得两点之间必有连边,所以有些系数是这样的,如下:

\[dp_{i+1,1} = dp_{i, 1}\frac 1 {2^{i-1}}+dp_{i,2}\frac 1{2^{i-2}} \]

\[dp_{i+2,2} = dp_{i, 1}\frac 1 {2^{2(i-1)}}+dp_{i,2}\frac 1{2^{2(i-2)}} \]

给出代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6 + 5;
int dp[maxn][3], n, mod;
int inv[maxn], revjc[maxn];
int cal(int x, int y) {return revjc[y] * inv[y * (y - 1) / 2 + x * y] % mod;
}
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;
}
signed main() {cin >> n >> mod;inv[0] = 1; revjc[0] = revjc[1] = 1;for (int i = 1; i <= 2 * n; i++)inv[i] = inv[i - 1] * (mod + 1) / 2 % mod;for (int i = 2; i <= 2 * n; i++)revjc[i] = (mod - mod / i) * revjc[mod % i] % mod;for (int i = 2; i <= n; i++)revjc[i] = revjc[i - 1] * revjc[i] % mod;dp[1][1] = cal(0, 1), dp[2][2] = cal(0, 2);for (int i = 1; i <= n; i++) {for (int x = 1; x <= 2; x++)for (int y = 1; y <= 2; y++)dp[i + y][y] = (dp[i + y][y] + dp[i][x] * cal(x, y)) % mod;}int res = (dp[n][1] + dp[n][2]) % mod;for (int i = 1; i <= n; i++)res = res * i % mod;cout << res * qpow(2, n * (n - 1) / 2, mod) % mod << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=36002

相关文章:

  • 位运算快速卷积 快速沃尔什变换 FWT
  • 嵌合抗体:破解二抗选择难题,赋能多重分子检测的核心工具
  • 原来用聊天记录就可以创造数字分身!WeClone项目在Lab4AI平台上的复现
  • 自监督提示优化SPO
  • Java中的注释
  • 实测!不同场景下,哪款 AI IDE 能真正帮你少加班?
  • CSP-S模拟36 2025.10.21
  • 2025 年 AI 编程工具生成效果全景比拼:从技术实力到综合评分
  • 打造AI IDE标杆产品,腾讯CodeBuddy深度全方位解析
  • C语言项目开发常用目录结构 - Invinc
  • 2025年不锈钢水箱厂家权威推荐榜:方形/圆形/消防/生活/保温/承压/装配式/焊接水箱及水塔水罐全解析
  • day03-Coze记忆-对话体验
  • 2025年流量计厂家权威推荐榜单:电磁流量计、超声波流量计、涡街流量计、质量流量计专业制造商深度解析
  • RNDIS让Air8000的USB上网更智能、更快速!
  • 如果k8s有三个calico节点A,B,C 使用bgp模式的话是如何进行BGP对等会话的
  • 10.21
  • home-assistant-Onboarding Home Assistant(入职家庭助理)
  • Day1标签语法
  • home-assistant-Concepts and terminology概念和术语
  • 2025年印染水洗机厂家权威推荐榜:高效水洗设备与环保节能技术深度解析,专业水洗机厂家精选
  • 高级语言程序设计第二次作业
  • 有关K8s calico IPIP模式的一些疑惑和思考
  • 1.正手握拍
  • 2025年角接触轴承厂家推荐排行榜,高精度/高承载/高精密/机床主轴/汽车/定制/可替代进口/高转速/高刚性角接触球轴承公司推荐
  • 7-Zip最新版 7-Zip25.01
  • 2025年精密球轴承厂家权威推荐榜:半导体设备轴承,机床主轴轴承,真空泵轴承,国产高端精密球轴承,晶圆搬运机械手臂不锈钢轴承
  • 结对项目-实现四则运算题目的命令行程序
  • 从易路iBuilder平台看企业人力资源的AI转型升级与变革
  • 从零开始,搭建自己的AI平台写小说
  • UMDF驱动开发入门:创建虚拟设备,从安装到I/O交互全解析