传送门
对于出题人zxyoizxyoizxyoi先%\%%为敬题目需要龟速乘差评。
题意简述：5e55e55e5组数据，给出n，请你求出所有n位数中有偶数个5的有多少，n≤1e18n\le1e18n≤1e18
思路：一眼数位dpdpdp，哎哟这nnn怎么这么大绝望.jpg
既然是zxyoizxyoizxyoi大毒瘤的题自然要推一推式子了无奈.jpg
考虑对每一位构造生成函数:
- 首位:F(x)=8+xF(x)=8+xF(x)=8+x
- 非首位:F(x)=9+xF(x)=9+xF(x)=9+x
所以答案就是(8+x)(9+x)n−1(8+x)(9+x)^{n-1}(8+x)(9+x)n−1展开之后所有次数为偶数的项的系数之和。
然后来一波变形：
(8+x)(9+x)n−1=(x+9)n−(x+9)n−1(8+x)(9+x)^{n-1}=(x+9)^n-(x+9)^{n-1}(8+x)(9+x)n−1=(x+9)n−(x+9)n−1
<=>(1+9)n−(−1+9)n2−(1+9)n−1−(−1+9)n−12\frac{(1+9)^n-(-1+9)^n}2-\frac{(1+9)^{n-1}-(-1+9)^{n-1}}22(1+9)n−(−1+9)n−2(1+9)n−1−(−1+9)n−1 使用二项式定理进行变形
<=>10n+8n−10n−1−8n−12\frac{10^n+8^n-10^{n-1}-8^{n-1}}2210n+8n−10n−1−8n−1
然后常规快速幂感觉挺慢的就上了一波倍增预处理。
代码