[2023杭电多校5 1005] Snake (生成函数)

news/2023/12/5 23:15:47

题意

n n n 个标号为 1 , 2 , ⋯ , n 1,2,\cdots,n 1,2,,n 的球,放到 m m m 个无标号盒子 (盒内顺序有标号),且每个盒子球数不超过 k k k,求方案数对 998 244 353 998\,244\,353 998244353 取模。

1 ≤ m , k ≤ n ≤ 1 0 6 1 \le m,k \le n \le 10 ^ 6 1m,kn106

分析:

考虑每个盒子内球的生成函数 ∑ i = 1 k x i \sum\limits_{i = 1} ^ {k}x ^ i i=1kxi,那么 m m m 个盒子的生成函数就为 ( ∑ i = 1 k x i ) m \left( \sum\limits_{i = 1} ^ {k}x ^ i\right) ^ m (i=1kxi)m,那么方案数就为第 n n n 项系数

由于球带标号,所以需要对答案全排列,也就是乘 n ! n! n!,又由于盒子不带标号,所以要对答案除 m ! m! m!,那么答案为

n ! m ! × [ x n ] ( ∑ i = 1 k x i ) m \frac{n!}{m!} \times [x ^ n]\left( \sum\limits_{i = 1} ^ {k}x ^ i\right) ^ m m!n!×[xn](i=1kxi)m

1 0 6 10 ^ 6 106 用多项式快速幂会超时,考虑

( ∑ i = 1 k x i ) m = x m ( ∑ i = 0 k − 1 x i ) m = x m ( 1 − x k ) m ( 1 − x ) m \left( \sum\limits_{i = 1} ^ {k}x ^ i\right) ^ m= x ^ m \left( \sum\limits_{i = 0} ^ {k - 1}x ^ i\right) ^ m = x ^ m \frac{(1 -x ^ k)^m}{(1 - x) ^ m} (i=1kxi)m=xm(i=0k1xi)m=xm(1x)m(1xk)m

转为求 [ x n − m ] ( 1 − x k ) m ( 1 − x ) m [x^{n - m}] \dfrac{(1 -x ^ k)^m}{(1 - x) ^ m} [xnm](1x)m(1xk)m 其中

( 1 − x k ) m = ∑ i = 0 m ( m i ) × ( − 1 ) i × x i × k 1 ( 1 − x ) m = ∑ i = 0 ∞ ( m − 1 + i m − 1 ) × x i (1 - x ^ k) ^ m = \sum_{i = 0} ^ {m}\binom{m}{i} \times (-1) ^ i \times x ^ {i \times k} \\ \frac{1}{(1 - x) ^ m} = \sum_{i = 0} ^ {\infty} \binom{m - 1 + i}{m - 1} \times x ^ i (1xk)m=i=0m(im)×(1)i×xi×k(1x)m1=i=0(m1m1+i)×xi

于是枚举第一个式子的 i i i,那么只需要求第二个式子的 n − m − i × k n - m - i \times k nmi×k 项系数即可。预处理组合数即可。

代码:

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int mod = 998244353;
template<class T>
T power(T a, int b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}
template<int mod>
struct ModInt {int x;ModInt() : x(0) {}ModInt(i64 y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}ModInt &operator+=(const ModInt &p) {if ((x += p.x) >= mod) x -= mod;return *this;}ModInt &operator-=(const ModInt &p) {if ((x += mod - p.x) >= mod) x -= mod;return *this;}ModInt &operator*=(const ModInt &p) {x = (int)(1LL * x * p.x % mod);return *this;}ModInt &operator/=(const ModInt &p) {*this *= p.inv();return *this;}ModInt operator-() const {return ModInt(-x);}ModInt operator+(const ModInt &p) const {return ModInt(*this) += p;}ModInt operator-(const ModInt &p) const {return ModInt(*this) -= p;}ModInt operator*(const ModInt &p) const {return ModInt(*this) *= p;}ModInt operator/(const ModInt &p) const {return ModInt(*this) /= p;}bool operator==(const ModInt &p) const {return x == p.x;}bool operator!=(const ModInt &p) const {return x != p.x;}ModInt inv() const {int a = x, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}return ModInt(u);}ModInt pow(i64 n) const {ModInt res(1), mul(x);while (n > 0) {if (n & 1) res *= mul;mul *= mul;n >>= 1;}return res;}friend ostream &operator<<(ostream &os, const ModInt &p) {return os << p.x;}friend istream &operator>>(istream &is, ModInt &a) {i64 t;is >> t;a = ModInt<mod>(t);return (is);}int val() const {return x;}static constexpr int val_mod() {return mod;}
};
using Z = ModInt<mod>;
vector<Z> fact, infact;
void init(int n) {fact.resize(n + 1), infact.resize(n + 1);fact[0] = infact[0] = 1;for (int i = 1; i <= n; i ++) {fact[i] = fact[i - 1] * i;}infact[n] = fact[n].inv();for (int i = n; i; i --) {infact[i - 1] = infact[i] * i;}
}
Z C(int n, int m) {if (n < 0 || m < 0 || n < m) return Z(0);return fact[n] * infact[n - m] * infact[m];
}
void solve() {int n, m, k;cin >> n >> m >> k;Z ans;for (int i = 0; i <= m; i ++) {Z f = i & 1 ? Z(-1) : Z(1);ans += f * C(m, i) * C(n - k * i - 1, m - 1);}cout << ans * fact[n] / fact[m] << "\n";
}
signed main() {init(1e6);cin.tie(0) -> sync_with_stdio(0);int T;cin >> T;while (T --) {solve();}
}

http://www.ppmy.cn/news/998739.html

相关文章

【基础理论】了解点过程

Maximum tsunami wave height generated by the 16 Sept. 2015 Chile earthquake, from the International Tsunami Information Center. Posted by Austin Elliott 一、说明 在这个世界上&#xff0c;会发生许多事件&#xff0c;其趋势可能遵循一种模式。在这篇博客中&#…

Java对象克隆

1.为什么要对象克隆&#xff1f; 因为直接new创建的对象&#xff0c;对象中的属性都是初始化的值&#xff0c;如果要使创建出来的对象要保存当前对象的状态&#xff0c;就要使用克隆了。 2.浅克隆 在浅克隆中&#xff0c;如果原型对象中的属性包含有引用变量&#xff0c;则将…

全新升级!腾讯云大数据 ES Serverless 服务开启日志分析新体验

2023年8月1号&#xff0c;腾讯云大数据 ES Serverless服务重磅发布&#xff0c;拥有自动弹性、完全免运维、极致成本、Elastic Stack生态兼容、灵活易用、稳定可靠等优势特性&#xff0c;提供开箱即用的云端Elasticsearch体验&#xff0c;助力企业高效上云&#xff01; 自建El…

Python Web开发(详细教程)

前言 PythonWeb开发是使用Python语言进行Web应用程序开发的过程。Python是一种简洁、易读且功能强大的编程语言&#xff0c;因此在Web开发领域广受欢迎。 一、PythonWeb开发简介 PythonWeb开发可以涵盖多个方面&#xff0c;包括服务器端开发、数据库管理、前端设计和API开发…

【ONE·Linux || 基础IO(一)】

总言 文件输入与输出相关介绍&#xff1a;语言层面/系统层面文件调用接口举例、文件描述符、重定向说明、缓冲区理解。 文章目录 总言1、文件输入与输出1.1、预备知识1.2、语言层面&#xff1a;回归C语言中文件相关接口1.2.1、打开文件和关闭文件&#xff1a;对当前路径的理解…

【TypeScript】类型断言的基本使用

类型断言的概念 有些时候开发者比TS本身更清楚当前的类型是什么&#xff0c;可以使用断言&#xff08;as&#xff09;让类型更加精确和具体。 类型断言&#xff08;Type Assertion&#xff09;表示可以用来手动指定一个值的类型。 类型断言语法&#xff1a; 值 as 类型 或 <…

无脑入门pytorch系列(一)—— nn.embedding

本系列教程适用于没有任何pytorch的同学&#xff08;简单的python语法还是要的&#xff09;&#xff0c;从代码的表层出发挖掘代码的深层含义&#xff0c;理解具体的意思和内涵。pytorch的很多函数看着非常简单&#xff0c;但是其中包含了很多内容&#xff0c;不了解其中的意思…

LeetCode_双指针_中等_143.重排链表

目录 1.题目2.思路3.代码实现&#xff08;Java&#xff09; 1.题目 给定一个单链表 L 的头节点 head &#xff0c;单链表 L 表示为&#xff1a; L0 → L1 → … → L~n - 1~ → Ln 请将其重新排列后变为&#xff1a; L0 → Ln → L1 → L~n - 1~ → L2 → L~n - 2~ → … 不…

快速搭建单机RocketMQ服务(开发环境)

一、什么是RocketMQ ​ RocketMQ是阿里巴巴开源的一个消息中间件&#xff0c;在阿里内部历经了双十一等很多高并发场景的考验&#xff0c;能够处理亿万级别的消息。2016年开源后捐赠给Apache&#xff0c;现在是Apache的一个顶级项目。 早期阿里使用ActiveMQ&#xff0c…

Node版本的切换之Window

步骤一&#xff1a;按健winR窗口&#xff0c;键盘输入cmd,然后回车。 步骤二&#xff1a; 输入where node&#xff0c;显示 步骤三&#xff1a;进入node.exe目录&#xff0c;并且删除父目录文件夹即&#xff1a;nodejs文件夹 步骤四&#xff1a;从官网下载版本管理并安装&#…

【Golang】基于录制,自动生成go test接口自动化用例

目录 背景 框架 ginkgo初始化 抓包&运行脚本 目录说明 ∮./business ∮./conf ∮./utils ∮./testcase testcase 用例目录结构规则 示例 实现思路 解析Har数据 定义结构体 解析到json 转换请求数据 转换请求 转换请求参数 写业务请求数据 写gotest测试…

好用的低代码开发平台是什么样的?

一、好用的低代码开发平台是什么样的&#xff1f; 从企业角度来说&#xff0c;优化流程&#xff0c;提升企业运行效率&#xff1b;节省成本&#xff0c;提高企业效益&#xff1b;维护方便&#xff0c;即改即用&#xff1b;一键升级&#xff0c;方便实用&#xff1b; 从开发者角…

DevOps系列文章之 Docker 安装 NFS 服务器

Docker 安装 NFS 服务器 环境&#xff1a; 192.186.2.105 NFS 服务器 192.168.2.106 Client 客户端 安装 一、服务器端 https://github.com/f-u-z-z-l-e/docker-nfs-server 1、创建目录 mkdir /nfsdata mkdir -p /docker/nfs/2、启动脚本 vim start.sh# 内容 docker run …

运维高级--tomcat和jpress

1. 简述静态网页和动态网页的区别。 静态网页&#xff1a;事先创建好的网页&#xff0c;通常通过HTML、CSS和JavaScript等静态文件组成&#xff0c;不需要和服务器进行交互&#xff0c;加载速度快 动态网页&#xff1a;根据用户需求动态生成网页&#xff0c;动态网页通常使用…

【docker】Windows11系统下安装并配置阿里云镜像加速

【docker】Windows11系统下安装并配置阿里云镜像加速 提示:博主取舍了很多大佬的博文并亲测有效,分享笔记邀大家共同学习讨论 文章目录 【docker】Windows11系统下安装并配置阿里云镜像加速一、查看Windows环境是否支持docker二、 启动Hyper-V三、 官网下载安装Docker应用和数据…

音乐节《迷笛音乐节》游玩感

上周&#xff0c;去了烟台&#xff0c;参加音乐节&#xff0c;以前从未参加过&#xff0c;所以趁着本周六周日双休的时候&#xff0c;去游玩了一次。&#xff08;1&#xff09;一种新奇体验 对于自己来说&#xff0c;参加音乐节还是一种新奇的体验的&#xff0c;也是疫情放开了…

关于样本方差为什么除以 n-1

今天上午集训摸鱼看到同学给我发的这个问题感觉挺有意思的 感性理解 这一部分的内容仅代表本蒟蒻没看严谨证明之前的个人见解&#xff0c;如果您想看严谨的证明&#xff0c;请翻到下一部分 还是先把图放上来罢省的有人不知道讲的什么东西 呃我知道这是生物竞赛的东西&#…

机器学习笔记之优化算法(六)线搜索方法(步长角度;非精确搜索;Glodstein Condition)

机器学习笔记之优化算法——线搜索方法[步长角度&#xff0c;非精确搜索&#xff0c;Glodstein Condition] 引言回顾&#xff1a; Armijo Condition \text{Armijo Condition} Armijo Condition关于 Armijo Condition \text{Armijo Condition} Armijo Condition的弊端 Glodstein…

2023年第四届“华数杯”数学建模思路 - 复盘:光照强度计算的优化模型

文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米&#xff0c;宽为12米&#xff0…

【技巧】学术Poster的制作要点,详细!

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 内容零零散散均收集自网上&#xff0c;有点杂忘了引用。 内容技巧 https://posts.careerengine.us/p/5dac3e628c131b0541dd9171 展示内容包括&#xff08;将信息分块&#xff09; 可选择性删减&#xff0c;注意…
最新文章