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

题解:qoj6170 凸多边形正则划分问题

题意:给定 \(n,k\),求 \(nk-2(n-1)\) 边形的 \(k\) 角剖分数量,\(n\le1.1\times10^6\)

做法:

前置知识:

  • 多项式复合逆:如果 \(F(G(x)) = G(F(x))=x\),则称 \(F,G\) 互为复合逆。

  • 拉格朗日反演公式:设 \(F\) 的复合逆为 \(G\),那么我们有

\[[x^n]F=\frac1 n[x^{n-1}](\frac{x}{G})^n \]

证明:因为 \(x=F(G(x))\),所以有 \(x = \sum\limits_{i=1}^nf_iG(x)^i\)

两边求导,得到 \(1=\sum\limits_{i=1}^nif_iG(x)^{i-1}G'(x)\)

为了得到 \(f_n\),我们考虑对两边除掉 \(G(x)^n\),得到 \(\frac{1}{G(x)^n}=\sum\limits_{i=1}^nif_i{G(x)^{i-1-n}}G'(x)\)

把这个 \(G(x)\) 塞进去再一起导,可以得到右式为 \((\sum\limits_{i=1}^n\frac{if_i}{i-n}(G(x)^{i-n})'[i\not=n])+nf_n\frac{G'(x)}{G(x)}\)

我们考虑取 \(x^{-1}\) 的系数,注意到对于一个多项式求导一定不会出现 \(x^{-1}\) 这一项,所以只能由最后这个 \(nf_n\frac{G'(x)}{G(x)}\) 提供,这样将这一项暴力拆开就得到 $$[x^{-1}]\frac{G'(x)}{G(x)}=1$$,往回带计算就可以得到我们需要证明的东西。


然后是本题做法。

先考虑从小情况入手,比如 \(k=3\),我们知道这个东西是卡塔兰数。考虑我们是如何解出来这个东西是卡塔兰数的,我们发现我们应该是直接考虑 \((1,2)\) 这一条边所在的多边形,把所有方案加总得到的。

那么对于更大的 \(k\) 同样计算,我们直接枚举剩余的部分分别划分为多少个 \(k\) 边形,可以写出柿子:$$a_n = \sum\limits_{x_1+x_2+\cdots x_{k-1}=n-1}\prod a_{x_i}$$。很容易写出来生成函数:$$F=1+xF^{k-1}$$。

如果 \(n\) 比较小感觉是可以递推计算的。但是 \(n\) 很大,到这里不会做了,不过我们看到有个前置知识拉格朗日反演,我们直接上拉格朗日反演:

\[[x^n]F=\frac1n[x^{n-1}](\frac{x}{G})^n \]

这里 \(G\)\(F\) 的复合逆,我们发现我们不会快速求复合逆(可能是可以的但是不需要),我们注意到 \(F=1+xF^{k-1}\) 这里有一个 \(x\),所以我们直接挪一下,可以算出来 \(G=\frac{x-1}{x^{k-1}}\)。直接带入可以得到:

\[[x^n]F = \frac{1}{n}[x^{n-1-kn}](x-1)^{-n} \]

对于这个柿子直接用广义二项式定理展开即可,答案为 \(\frac1n(-1)^{(k-2)n+1}\frac{(-n)^{\underline{(k-2)n+1}}}{((k-2)n+1)!}=\frac{(kn)!}{n!((k-1)n+1)!}\)

对着这个柿子做就可以了,复杂度 \(O(n)\)

代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1.1e6 + 5, N = 1.1e6, mod = 1e9 + 7;
int revjc[maxn], n, k;
void prepare() {revjc[0] = revjc[1] = 1;for (int i = 2; i <= 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;
}
signed main() {int res = 0;prepare();while(cin >> n >> k) {int ans = revjc[n];for (int i = (k - 2) * n + 2; i <= (k - 1) * n; i++)ans = ans * i % mod;res = (res + ans) % mod;}cout << res << endl;return 0;
}
http://www.hskmm.com/?act=detail&tid=26578

相关文章:

  • Ynoi
  • 2025 铅板源头厂家最新推荐排行榜:聚焦防辐射铅门 / 放射科防护 / 高纯度铅皮,深挖性价比与适配性
  • 2025 年国内电容厂家最新推荐排行榜:聚焦固态 / 高压 / 安规 / CBB / 超级电容多品类,精选优质厂商助力企业精准采购选型
  • 2025 年 MOS 管厂家最新推荐排行榜权威发布,覆盖高压 / 低压 / 大功率 / N 型等类型,助力企业高效采购精准选型
  • Chrome浏览器插件开发
  • 2025 年最新波形护栏厂家推荐排行榜:聚焦国内优质厂商技术优势与服务能力,助力采购方精准选型 三波/二波/双波/喷塑/公路/热浸锌/浸塑波形护栏厂家推荐
  • linux 中paste命令实现按照指定列数输出文件
  • Transformer原理解析及中文项目实践(微课视频版)
  • ROS 2机器人操作系统与Gazebo机器人仿真
  • 2025 年次氯酸钠发生器厂家最新推荐榜:覆盖电解法 / 食盐电解等类型,聚焦专利技术与成本优势的品牌深度解析水厂/大型/小型/食盐电解产生次氯酸钠发生器厂家推荐
  • 2025 年二氧化氯发生器厂家最新推荐排行榜:电解式设备厂家综合实力测评及优质企业选购指南电解/电解法/电解食盐/电解盐二氧化氯发生器厂家推荐
  • 2025 年章丘二手磁选机服务公司最新推荐榜单:含回收置换 / 全型号设备及优质售后企业权威排行
  • Navicat配置MySQL自动备份
  • 2025 年最新铝镁锰板厂商口碑排行榜:实力厂家推荐及 100 万㎡工程案例与 20 年质保深度解读铝镁锰板屋面板/保温板/卷/墙面板 铝镁锰板金属屋面板
  • 2025 年国内铝板厂家最新推荐排行榜:1-7 系主流铝板企业实力测评及优选指南1060/1100/3003/3004/5052/5083/6061/6063/6082铝板厂家推荐
  • 2025 年染井吉野樱种植服务公司最新推荐排行榜:苗木分枝点规格详解与景观适配指南及优质企业榜单染井吉野樱花苗/五公分染井吉野樱/十公分染井吉野樱/染井吉野樱批发公司推荐
  • 2025 年国内磁选机厂家最新推荐排行榜:立环 / 高梯度 / 油冷立环磁选机优质厂商实力解析
  • 2025 年北京红旗国悦经销商最新推荐排行榜:行业标杆与新锐品牌齐聚,购车选品指南重磅发布北京丰田考斯特/北京红旗国悦12座/北京考斯特4S店/北京丰田柯斯达/北京考斯特商务车经销商推荐
  • LINUX之TCP内核参数解析
  • 焦糖饼干头文件c++最新同步
  • 2025 年最新三维扫描仪厂家权威推荐排行榜:空间 / 高精度 / 手持激光等类型设备优选企业全解析工业/便携式/拍照式/蓝光三维扫描仪厂家推荐
  • 2025 年上海刑事辩护律师 / 刑事案件律师 / 刑事诉讼律师 / 刑事犯罪律师 / 刑事纠纷律师事务所推荐:徐海燕律师团队专业法律服务
  • 垂起固定翼无人机应用及科技分析
  • 2025 年可行性研究报告公司最新推荐排行榜:权威筛选国内实力机构,助力企业精准选型
  • 2025 年离散制造领域 MES 厂商最新推荐榜单:全面解析头部服务商实力,助力企业数智化转型mes制造执行系统/mes系统 mes软件/mes生产制造执行系统/mes生产管理系统厂商推荐
  • 2025螺杆泵厂家最新推荐榜:高效耐用与专业定制实力之选
  • 稳时复位仿真攻略
  • 2025 年硫化仪厂家最新推荐排行榜:聚焦实力厂家技术亮点、售后保障及适配场景指南无转子/橡胶硫化仪/硫化仪门尼粘度仪/有转子硫化仪厂家推荐
  • 2025 年 WMS 公司最新推荐排行榜:全面盘点品牌核心技术优势助力仓储效率提升 28%+ 及选型指南 wms仓库管理软件/wms仓库管理系统软件/wms出入库管理系统公司推荐
  • T/CCSA 663-2025《医疗科研云平台科技要求》标准解读与深度分析