Solution -「CF 908G」New Year and Original Order
\(\mathcal{Description}\)
Link.
对于 \(x\in\mathbb N^*\),令 \(s(x)\) 表示将 \(x\) 十进制下的各位数码排序后得到的十进制数的值。求 \(\sum_{i=1}^X s(i)\) 对 \((10^9+7)\) 取模的结果。
\(X\le10^{700}\)。
\(\mathcal{Solution}\)
下记 \(m=10\)(进制),\(n=\lceil\log_mX\rceil\)。
\(\mathcal{Case~1}\)
市面上的题解做法。
考虑到“数码有序”的特性:\(\forall x,~s(x)\) 可以表示为若干个 \(11\dots1\) 之和。对于 \(d\in[1,9]\),\(d\) 显然在 \(s(x)\) 中占有连续的一段,那么 \(s(x)\) 有形如 \(\sum_d \underbrace{dd\dots d}_a\underbrace{00\dots0}_b\) 的形式,其中 \(a\) 表示 \(d\) 的个数,\(b\) 表示大于 \(d\) 的数码个数。根据上述特性,它可以转化为 \(\sum_d\underbrace{11\dots1}_a\underbrace{11\dots1}_b\),就能直接 DP 计算啦。
令 \(f_d(i,j,0/1)\) 表示当前的 \(x\) 填到了从高到低第 \(i\) 位,且有 \(j\) 个数码大于等于 \(d\),是否被 \(X\) 限制的方案数,转移枚举第 \(i+1\) 位所填的数码即可。最终答案为
\]
复杂度 \(\mathcal O(m^2n^2)\)。
\(\mathcal{Case~2}\)
一种粗暴但是实用的 GF 做法。
本节记 \(v_i=\underbrace{11\dots1}_i\)。
对于上界 \(X\),不管什么做法都很难带着这种限制算。考虑枚举 \(x\) 中从高到低第一个严格小于 \(X\) 的数码位置 \(p\) —— 即 \(x\) 的第 \(1\sim p-1\) 位与 \(X\) 相同,第 \(p\) 位小于 \(X\)。同时,记 \(c_i\) 示 \(X\) 的 \(1\sim p-1\) 位中数码 \(i\) 的出现次数,它们在 \(x\) 中亦出现,且位置已经固定。当然,还需要枚举第 \(p\) 位的值。
注意到 \(x\) 的第 \(p+1\sim n\) 位已经不必担心限制,可以用单纯的计数 DP 而非数位 DP 进行求解。我们以 \(1\sim 9\) 的顺序将数码填入这 \(n-p\) 个位置中,没填的位置视为 \(0\)(不影响 \(s(x)\) 的值),设 DP 状态:
- \(g_{i,j}\) 表示用 \(1\sim i\) 的数码填 \(j\) 个位置的方案数;
- \(f_{i,j}\) 表示用 \(1\sim i\) 的数码填 \(j\) 个位置,得到的所有 \(x\) 的 \(s(x)\) 之和。(再次强调,没填的位置视为 \(0\))。
对于 \(g_{i,j}\) 的转移,枚举数码 \(i\) 的个数,得到
\]
对于 \(f_{i,j}\) 的转移,数码 \(i\) 会把 \(s(x)\) 本来的值整体向高位位移(因为 \(s(x)\) 当时只有 \(1\sim i-1\) 的数码,都小于 \(i\)),然后低位补上 \(dd\dots d\)。具体有
\]
我们可以用它们表示出当前 \(p\) 对答案的贡献 \(\text{ans}_p\) 为:
\]
注意 \(f_{m-1,k}\) 中的 \(k\) 只考虑了内部选位置的方案,所以外面还得带一个组合数。
DP 在此告一段落,如此暴力求答案的复杂度是枚举前缀的 \(\mathcal O(nm)\) 套 DP 的 \(\mathcal O(n^2m)\) 即 \(\mathcal O(m^2n^3)\) 的。
接下来引入 EGF,令
F_i(x)=\sum_{j=0}^{n-p-1}f_{i,j}x^j
\]
尝试化简它们,从递推式入手:
\Rightarrow~~~~\frac{g_{i,j}}{j!}=\sum_{k=0}^j\frac{g_{i-1,j-k}}{(j-k)!}\cdot\frac{1}{k!}
\]
后者很显然是一个卷积形式,套入 EGF 就有:
\Rightarrow~~~~G_i(x)=e^xG_{i-1}(x)\\
\Rightarrow~~~~G_i(x)=e^{ix}
\]
类似的,对于 \(F\) 有
\Rightarrow~~~~\frac{f_{i,j}}{j!}=\sum_{k=0}^j\left(\frac{m^{c_i}m^k}{k!}\cdot\frac{f_{i-1,j-k}}{(j-k)!}+i\cdot\frac{g_{i-1,j-k}}{(j-k)!}\cdot\frac{m^{c_i}v_k+v_{c_i}}{k!}\right)\\
\Rightarrow~~~~F_i(x)=m^{c_i}e^{mx}F_{i-1}(x)+iG_{i-1}(x)\left(m^{c_i}V(x)+v_{c_i}e^x\right),~~~~\text{let }V(x)=\sum_{i=0}^{+\infty}v_ix^i\\
\Rightarrow~~~~F_i(x)=m^{c_i}e^{mx}F_{i-1}(x)+ie^{(i-1)x}(m^{c_i}V(x)+v_{c_i}e^x)
\]
发现这是关于 \(F_i(x)\) 的常系数线性递推,令
q_i=ie^{(i-1)x}(m^{c_i}V(x)+v_{c_i}e^x)
\]
则
\]
美观多啦,手代一下就能展开成通项:
\]
进一步,代入 \(\text{ans}_p\) 的式子:
\frac{\text{ans}_p}{(n-p)!}&=[x^{n-p}]e^xF_{m-1}(x)\\
&=[x^{n-p}]e^x\sum_{k=1}^{m-1}q_k\prod_{j=k+1}^{m-1}p_j\\
&=[x^{n-p}]\sum_{k=1}^{m-1}\left(ke^{kx}(m^{c_k}V(x)+v_{c_k}e^x)\right)\left(\prod_{j=k+1}^{m-1}m^{c_j}e^{mx}\right)\\
&=[x^{n-p}]\sum_{k=1}^{m-1}k\left(\prod_{j=k+1}^{m-1}m^{c_j}\right)(m^{c_k}e^{(m(m-1-k)+k)x}V(x)+v_{c_k}e^{(m(m-1-k)+k+1)x})\\
\end{aligned}
\]
卡住啦,瓶颈在于求 \(e^{(m(m-1-k)+k)x}V(x)\)。来看看 \(V(x)\) 是什么……
V(x)&=\sum_{i=0}^{+\infty}\frac{m^i-1}{m-1}\cdot\frac{x^i}{i!}\\
&=\frac{1}{m-1}(e^{mx}-e^x)\\
&=\frac{e^x}{m-1}(e^{(m-1)x}-1)
\end{aligned}
\]
大力丢进去,有
e^{(m(m-1-k)+k)x}V(x)&=\frac{1}{m-1}e^{(m(m-1-k)+k+1)x}(e^{(m-1)x}-1)
\end{aligned}
\]
天呐它果然封闭,可以 \(\mathcal O(1)\) 算系数。那么整个算法就是 \(\mathcal O(nm)\) 枚举 \(p\) 套 \(\mathcal O(m)\) 求 \(\text{ans}_p\),即 \(\mathcal O(m^2n)\) 的。
\(\mathcal{Case~3}\)
来冷静并反复刺激一下大脑叭~
研究某个 \(x\) 及其 \(s(x)\),设 \(x\) 中数码出现次数为 \(c_{0..9}\),则
\]
实质上就是 \(\mathcal{Case~1}\) 中 \(11\dots 1\) 的转化。然后类似 \(\mathcal{Case~2}\) 地,枚举 \(x\) 与 \(X\) 的相同前缀及下一位严格小于 \(X\) 的数码。还是记枚举的位置 \(p\),前缀中数码出现次数为 \(c_{0..9}\)。把上式 \(\sum_{j=i}^{m-1}c_j\) 处理为后缀和 \(s_i\),那么 \(\text{ans}_p\) 有
\]
注意其中 \(j\) 枚举的是“大于等于 \(i\) 的数码个数”。瞪一下和式里面,显然可以把形如二项式展开的这一坨拍回去。记 \(l=n-p\),推一推:
\sum_{j=0}^{l}\cdots&=m^{s_i}\sum_{j=0}^l\binom{l}{j}(i-1)^{l-j}(m-i)^jm^j-(m-1)^l\\
&=m^{s_i}(m(m-i)+i-1)^l-(m-1)^l
\end{aligned}
\]
扫前缀的过程中顺带维护一下这个式子,Tiw:可以做到 \(\mathcal O(mn)\)。
由于有些算法没写,所以都不给代码啦 awa~
最新文章
- Linux C 信号 pause、sigsuspend 的相同与区别
- MySQL学习笔记十:日志管理
- [WCF编程]9.性能与限流
- OAuth授权过程
- 简单封装cookie操作
- POJ 3264 区间最大最小值Sparse_Table算法
- 洛谷 P1273 有线电视网
- Spark SQL编程指南(Python)
- [中级] 有效删除URL中的index.php
- angular-fullstack test
- commands - `ls`
- Scrapy 初体验
- ES6中export , export default , import模块系统总结
- SQL性能优化的几点建议
- post请求参数Json字符串包含数组的校验和处理 -工作随记-备查工具
- pypi pack and upload
- go日常问题记录
- JavaScript之ECMA对象的学习
- hashlib
- Java获取后台数据,动态生成多行多列复选框