T1
Statement
任意相邻两个数字之差至少为 \(2\) 的正整数被称为 windy 数。给出 \(A,B(A\le B \le2\times10^9)\),求 \([A..B]\) 中有多少个 windy 数。
Solution
我们使用记忆化搜索实现。
\(f(i,x,a,b)\) 表示还有 \(i\) 位需要确定,上一位数字为 \(x\),是否达到上限,是否不含前导 0 的方案数。
转移:
int mx = a ? num[i] : 9, ans = 0;
for (int k = 0; k <= mx; k++)
if (abs(x - k) >= 2 || !b)
ans += dfs(i - 1, k, a&(k==mx), b|(k!=0));
f[i][x][a][b] = ans;
初值:-1
边界:i = 0
时返回 \(1\)
答案:dfs(n, 0, 1, 0)
最后用两个前缀相减得到答案。
T2
Statement
给定正整数 \(A\)(\(\le 10^{1000}\))和 \(S\)(\(\le 5000\)),需要在 \(A\) 的数码之间添加若干个加号,使得得到的式子与 \(S\) 相等。问最少添加多少个加号。
Solution
- \(num(i,j)\) 表示 \(A\) 中第 \(i\) 个数字到第 \(j\) 个数字组成的数.
- \(n\) 表示 \(A\) 的长度,\(m\) 表示 \(S\) 的长度.
\(f(i,j)\) 表示后 \(i\) 位数字加起来等于 \(j\) 的最少加号数.
\(f(i,j)=\min_{k=i+1}^{\min(n,i+2m-1)}\{f(k,j-num(i,k-1))+1\}\)
这里我们让新增的数的位数不超过 \(S\),保证了复杂度;同时注意 \(j-num(i,k-1)\) 需要大于 0.
注意到前导零的存在(如 1 + 0001 + 1
),所以我们最多保留 \(m-1\) 个连续的 0
,并让 \(k\) 循环到 \(i+2m-1\)
因为如果有多于 \(m-1\) 个连续的 0
,那么多出的 0
就不能与前面的数组合,就没用了;此时 \(k\) 最多需要循环到 \(i+2m-1\)
初始 \(f(n,0)=0\),其余设为 inf
时间复杂度 \(\mathcal O(nmS)\).
T3
Statement
找一个数作为“支点”,两边的“力矩”相等的数称为“平衡数”。给出正整数 \(x,y\)(\(x\le y\le10^{18}\)),问 \([x..y]\) 中有多少个“平衡数”。
Solution
由于两边力矩相等,令一边为正、一边为负,那么相加就是 0.
然后发现力矩最大为 \(18\times9+17\times9+..+1\times9=1539\),很小
无限制:
\(f(x,i,1/0)\) 表示 \(i\) 个数使得力矩为 \(x\) 的方案数,每个数 \(\in[0,9]\),其中第一个数能否为 0.
\(f(x,i,0)=\sum_{j=0}^9f(x-ij,i-1,0)\),其中要求 \(x-ij\ge0\)
\(f(x,i,1)=\sum_{j=1}^9f(x-ij,i-1,0)\)
设这个数有 \(i\) 位,则方案数 \(=\sum_{k=0}^{1539}\sum_{j=2}^{i-1}10\times f(k,j-1,1)\times f(k,i-j,0)\)
\(i=1\) 时方案数 \(=10\)
有限制:
设有 \(i\) 位待确定,这个数一共 \(n\) 位,每位数字分别为 \(a_k\)
枚举支点 \(x\) 和力矩 \(y\)
方案数 \(=\sum_{x=2}^{n-1}\sum_{y=p}^{p+9\times\max(0,(x-n+i)\cdot(x-n+i+1)/2)}f(y-p,x-n+i,0)\cdot f(y,n-x,0)\)
其中 \(p\) 表示已知的数字在支点 \(x\) 下产生的力矩大小,即
\(p=\sum_{j=1}^{n-i+1}a_j\cdot|x-j|\)
若 \(x-n+i\le0\),令 \(f(y-p,x-n+i,0)=1\)
=======
答案加起来就行了
时间复杂度 \(\mathcal O(18\times1539+18\times1539\times18+18\times18\times1539)=\mathcal O(1,024,974)\)
T4
Statement
\(\mathrm{cnt1}(i)\) 表示二进制整数 \(i\) 中包含的数字 1
的个数。给定 \(N\)(\(\le 10^{15}\)),求 \(\prod_{i=1}^{N}{\mathrm{cnt1}(i)}\bmod Q\)。
Solution
不卡到上限:
设有 \(i\) 位,选出 \(j\) 个 1,则 \(\mathrm{cnt1}=j\),有 \(\binom ij\) 种选法,故乘 \(\binom ij\) 次
所以 \(Ans=\prod_{j=1}^ij^{\binom ij}\bmod Q\)
卡到上限:
设共 \(L\) 位,还有 \(i\) 位未确定(不包括当前),\(cnt(k)\) 表示前 \(k\) 位的 1 的数量
若当前已经卡到了上限,则继续向下一位计算(若选 1 则一定会卡到上限);
若当前选 0,则相似地,\(Ans=\prod_{j=1}^i(cnt(L-i-1)+j)^{\binom ij}\bmod Q\)
========
所有的 \(Ans\) 乘起来再 mod Q 即可,因为只有 15 位,直接暴力算都绰绰有余
我们发现一个问题:\(\binom ij\) 可能会超过 long long 范围,此时将他 \(\bmod\ \varphi(Q)\) 即可
T5
Statement
一个数各相邻数位的下降、相等和上升用 \-/
三个字符表示,然后将连续相同的字符缩写成一个,形成一个长度为 \(n\)(\(\le100\))的给定字符串,问 \([A..B]\) 中有多少个数的波动关系缩写以后等于它。\(0\le A\le B\le10^{100}\),有 \(100\) 组数据。
Solution
数的长度限制为 \(m\),\(cmp(x,y)\) 表示数 \(x,y\) 之间的波动关系,\(c_k\) 表示字符串从右往左第 \(k\) 位的波动关系,\(a_k\) 表示该数从左往右第 \(k\) 个数码
\(f(i,x,j)\) 表示有 \(i\) 位,最高位为 \(x\),对应给出字符串从右往左 \(j\) 个字符,的方案数
\(f(i,x,j)=\sum_{y=0}^9t\),其中 \(j\not=0\)
当 \(cmp(x,y)=c_j\) 且 \(i>j+1\) 时,\(t=f(i-1,y,j-1)+f(i-1,y,j)\)
当 \(cmp(x,y)=c_j\) 且 \(i=j+1\) 时,\(t=f(i-1,y,j-1)\)
\(f(1,x,0)=1,i\in[1,9]\),其余初始为 \(0\)
无限制:\(Ans=\sum_{i=1}^{m-1}\sum_{j=1}^9f(i,j,n)\)
有限制:
\(g(i)\) 表示确定的前 \(i\) 位满足字符串从左往右的字符数,\(c\) 变成从左往右数.
\(i=0\) 时 \(Ans=\sum_{j=1}^{a_{i+1}-1}f(m,j,n)\)
\(i=1\) 时 \(Ans=\sum_{j=0\ 且\ cmp(a_i,j)=c_1}^{a_{i+1}-1}f(m-i,j,n-1)+f(m-i,j,n)\)
\(i>1\) 且 \(g(i)>0\) 时,其中 \(j\in[0..a_{i+1}-1]\)
-
\(cmp(j,a_i)=c_{g(i)}\) 时:\(Ans=\sum f(m-i,j,n-c_{g(i)}+1)+f(m-i,j,n-c_{g(i)})\)
-
\(cmp(j,a_i)=c_{g(i)+1}\) 时:\(Ans=\sum f(m-i,j,n-c_{g(i)}-1)+f(m-i,j,n-c_{g(i)})\)
最后答案就是加起来. 然后前缀和相减.
复杂度 \(\mathcal O(TnmB^2)\),其中 \(B=10\).
T6
Statement
一个数是“漂亮的”,当且仅当它能够被它的每个非零位整除。问 \([L..R]\) 中有多少个数是“漂亮的”。\(1\le L\le R\le9\times10^{18}\)。
Solution
每个数位 \(\in[0,9]\),观察到 \(\text{lcm}(1,2,..,9)=2520\) 极小,故枚举 \(\text{lcm}\).
那么若一个数被 \(\text{lcm}\) 整除,则这个数是“漂亮的”.
\(f(i,j,k)\) 表示这个数有 \(i\) 位(含前导零),这个数 \(\bmod\ 2520=j\),这个数的各数位 \(\text{lcm}=k\),的个数
假设当前 \(f(i,j,k)\) 已知,规定 \(\text{lcm}(x,0)=x\),我们用它向外更新:
\(f(i+1,(j+p)\bmod2520,\text{lcm}(k,p))\) += \(f(i,j,k)\),其中 \(p\in[0..9]\)
\(f(1,p,p)=1\)(\(p\in[0..9]\)),其余初始化为 0.
无限制:设 \(n\) 位,一起算:\(Ans=\sum_{k=1}^{2520}\sum_{l=1}^{\lfloor\frac{2520}k\rfloor}f(n,l\cdot k,k)\)
有限制:
设共 \(n\) 位,有 \(i\) 位已知,\(s(k)\) 表示前 \(k\) 位已知数码组成的数,\(l(k)\) 表示前 \(k\) 位已知数码的 \(\text{lcm}\).
分开算:\(Ans=\sum_{j=0}^{2519}\sum_{k=1}^{2520}f(n-i,j,k)\),且 \(j,k\) 满足 \(\text{lcm}[l(i),k]\) 整除 \([s(i)\times10^{n-i}+j]\bmod2520\).
总的答案就把所有 \(Ans\) 加起来,然后用前缀和相减得到.
时间复杂度 \(\mathcal O(nm^2+m\log m+nm^2)=\mathcal O(nm^2)\),其中 \(n\) 是数字长度,\(m=2520\).
标签:le,..,text,sum,ij,Ans,dp,数位 From: https://www.cnblogs.com/laijinyi/p/18148220/Num-dps1