zhongzihao/51nod

1048. 整数分解为2的幂 V2

题目大意：求 \(n\) 分解为若干个 \(2\) 的幂相加（无序）的方案数。

题解：定义 \(dp[i][j]\) 表示用前 \(i\) 个 \(2\) 的幂表示 \(j\) 的方案数。那么显然 \(dp[i][j]=\sum_{k=0,k\le\lfloor\frac{j}{2^{i}}\rfloor}dp[i-1][j-k\cdot2^{i}]\)。容易发现，\(dp[1][k\cdot 2+n\mod{2}]\) 是关于 \(k\) 的一次多项式，那么我们可以归纳证明，\(dp[i][k\cdot2^{i}+n\mod{2^{i}}]\) 是关于 \(k\) 的 \(i\) 次多项式。那么整个问题可以插值解决。

tips：这题一眼看上去很像生成函数题，但是推出来以后并没有办法计算（可能是我太菜了）。所以还是要尝试从不同的角度思考问题。

1132. 覆盖数字的数量 V2

题目大意：求 \([x,y]\) 中能由若干个 \(a\) 和 \(b\) 加起来表示的数量。

题解：不妨设 \(\gcd(a,b)=1\)，那么有 \(xa+yb=1\)，不妨设 \(x>0,y<0\)。那么一个数 \(c\) 能被表示，相当于 \(ax_{1}+bx_{2}=c\) 有非负整数解，而这一方程的通解为 \(x_{1}=xc-tb,x_{2}=yc+ta\)。那么有解的充要条件即为 \(yc+\lfloor\frac{xc}{b}\rfloor a\ge0\)，即 \(\lfloor\frac{xc}{b}\rfloor\ge\frac{-yc}{a}\)。

注意到 \(xa+yb>0,\frac{xc}{b}>\frac{-yc}{a}\)。而 \(\frac{xc}{b}\ge\frac{-yc}{a}+1\) 时显然有解，因此我们只需要统计 \(\frac{-yc}{a}<\frac{xc}{b}<\frac{-yc}{a}+1\)，即 \(c<ab\) 范围内的解即可。容易证明，在这个范围内，有解等价于 \(\lceil\frac{-yc}{a}\rceil-\lfloor\frac{xc}{a}\rfloor=1\)，无解等价于 \(\lceil\frac{-yc}{a}\rceil-\lfloor\frac{xc}{a}\rfloor=0\)。这个个数容易用类欧统计。

1143. Square Country 3

题目大意：构造一个 \(n\times m\) 的矩阵，使得每行、每列、每行的和、每列的和都是完全平方数，且矩阵中元素两两不同。

题解：可以分别构造两个长度为 \(n\) 的 \(m\) 的序列 \(a\) 和 \(b\)，使得序列里的元素及序列的和都是完全平方数，那么 \(A_{i,j}=a_{i}b_{j}\) 即满足要求。对于元素两两不同的条件要小心。

1149. Pi的递推式

题目大意：定义

\[ f(x)=\begin{cases} &1&(x<4)\\ &f(x-1)+f(x-\pi)&(x\ge4) \end{cases} \]

求 \(f(n)\)。

题解：转化为求解格路径的数量，形状大致是一个阶梯型，用组合数计算即可。

1150. Logarithm

题目大意：给出一个长度为 \(n\) 且两两不同的数列 \(a\)，求 \(\sum_{i}\sum_{j\neq i}\log_{10}(a_{i}\oplus a_{j})\)。

题解：trie 入门题。

1171. 两个数的平方和 V2

题目大意：给出 \(N\le10^{18}\)，求出所有的整数 \(0\le i\le j\)，使得 \(N=i^{2}+j^{2}\)。

题解：注意到即便暴力复杂度也只有 \(\mathcal{O}(10^{9})\)，考虑剪枝。我们可以选取若干个质数，求出所有满足 \(i^{2}+j^{2}\equiv N\pmod{p}\) 的 \(i\)。由于模质数意义下只有一半的数是二次剩余，所以每一个质数大约能够筛掉一半的数。

1184. 第N个质数

题目大意：求第 \(n\le10^{9}\) 个质数。

题解：朴素的想法是二分加洲阁筛，时间复杂度是 \(\mathcal{O}((n\log n)^{\frac{3}{4}})\)，会稍微超时一点。但是我们可以从wiki上找到一个质数估计函数，在本题范围下误差不超过 \(\pm3\times10^{6}\)。因此我们可以对 left-1 前用洲阁筛计数，left~right 用区间筛即可。

1221. 矩阵中不重复的元素 V3

题目大意：求 \(x^{y}\) 有多少种不同的取值，其中 \(x\in\mathbb{N}\cap[a,a+n-1],y\in\mathbb{N}\cap[b,b+m-1]\)。

题解：显然我们可以将问题转化为：对于所有非完全乘方数，统计它们的多少次幂被取到。设 \(t\) 为一个非完全乘方数，\(x=t^{u},y=v\)，那么我们有 \(\log_{t}a\le u\le\log_{t}(a+n-1),b\le v\le b+m-1\)。注意到取 \(\log\) 后值很小，可以枚举所有不同的 \(\log_{t}a\) 和 \(\log_{t}(a+n-1)\) 来计算，而满足要求的 \(t\) 的数量可以容斥得到。下面的问题就变成了，对于 \(l\le u\le r,b\le v\le b+m-1\)，有多少不同的 \(uv\) 值。这可以暴力对 \(u\) 容斥得到，但是有些卡常，需要手写 hash。

1224. 阶乘的幂的倍数

题目大意：定义 \(s(i,k)\) 为满足 \((i!)^{k}\mid n!\) 的最小的 \(n\)，求 \(\sum_{i=2}^{n}s(i,k)\)。

题解：定义 \(f(i,p)\) 为 \(i!\) 中 \(p\) 的个数。显然 \(f\) 是一个关于 \(\lfloor\frac{i}{p}\rfloor\) 的函数，因此我们可以枚举所有的质数及它们的倍数，计算 \(f^{k}(i,p)\) 最早在哪个阶乘中出现。注意到在 \(p\) 进制下，每一位对 \(p\) 的贡献相当于该位数乘上一个系数，因此这个答案很容易用数位 \(dp\) 求出。

1245. Binomial Coefficients Revenge

题目大意：求 \({n\choose0},\cdots,{n\choose n}\) 中质因子 \(p\) 的数量分别为 \(0,1,2,\cdots\) 的有多少个。

题解：使用库默尔定理就可以简单地转化成一个数位 \(dp\) 了。

1261. 上升数

题目大意：定义前一位小于等于后一位的正整数为上升数，求 \(n\) 位且能被 \(k\) 整除的上升数的数量。

题解：经过一番转换后，可以等价于下面的问题：\(10^{a_{1}}+\cdots+10^{a_{8}}\equiv9-10^{n}\pmod{9k}\)，且 \(0\le a_{1}\le\cdots\le a_{8}\le n\) 的数列 \(a\) 有多少。显然是个 \(dp\)，朴素的想法只需要对 \(0\sim n\) 中每个数取多少个进行 \(dp\) 即可。但是 \(n\) 太大，还需要注意到 \(\pmod{9k}\) 下只有 \(9k\) 种余数，可以分组背包 \(dp\)。设 \(dp[i][j][k]\) 表示前 \(i\) 组中取 \(j\) 个数，余数为 \(k\) 的方案数，转移时算一下组合数即可。最后答案为 \(dp[9k][8][9-10^{n}\mod{9k}]\)。

1334. 无穷可定义数

题目大意：对于所有满足 \(w\nmid x\) 的正整数 \(x\)，定义 \(f(x)=\frac{x}{x\mod{w}}\)。若对于某个正整数 \(x\)，\(f(x),f(f(x)),\cdots\) 无限嵌套下去都有定义，称 \(x\) 为无穷可定义数。给出 \(w\)，求 \([L,R]\) 中的无穷可定义数。

题解：显然一个无穷可定义数嵌套若干次后模 \(w\) 余 \(1\)，此后就不再变化。我们可以反向思考，从模 \(w\) 余 \(1\) 开始暴搜，每次考虑乘上一个数 \(x\)，判断乘上之后模 \(w\) 的余数是否恰好是 \(x\)。这样我们每次可以得到模 \(kw\) 余 \(k\) 的一个形式，很容易计算。

1355. 斐波那契的最小公倍数

题目大意：定义 \(f_{0}=0,f_{1}=1,f_{i}=f_{i-1}+f_{i-2}\)。给出若干个 \(a_{i}\)，求 \(\text{lcm}(f_{a_{1}},\cdots,f_{a_{n}})\)。

题解：易证 \(\gcd(f_{i},f_{j})=f_{\gcd(i,j)}\)。求 \(\text{lcm}\) 可以通过指数的 \(Min-Max\) 反演化为求 \(\gcd\)，而 \(\gcd\) 容易容斥求出。

1361. 有一种递推

题目大意：设 \(a_{1}=1,a_{n}=6a_{n-1}^{2}+10a_{n-1}+3\)，求 \(a_{n}\mod{p}\)。

题解：可得 \(a_{n}+\frac{5}{6}=6(a_{n-1}+\frac{5}{6})^{2}-\frac{1}{3}\)，可以用待定系数法设 \(a_{1}=6^{u}+6^{-2-u}\)，之后就容易了。

1386. 双马尾机器人

题目大意：求 \(\{1,2,\cdots,n\}-\{k\}\) 的所有子集中极大的两两互质的集合的大小的最小值。

题解：经典 \(dp\)。对于小于等于 \(\sqrt{n}\) 的质数状压 \(dp\)，大于 \(\sqrt{n}\) 的质数分组背包 \(dp\)。

1387. 移数字

题目大意：对一个序列有两种操作：一是把第三位的数字移到最前面，二是把最后一位的数字移到最前面。问 \(1\sim n\) 的所有排列中有多少可以通过这两种操作排成升序。

题解：\(n\) 为奇数时，两种操作都不改变逆序数的奇偶性，因此答案最多为 \(\frac{n!}{2}\)。下面我们证明答案为 \[ \begin{cases} &n!&(2\mid n)\\ &\frac{n!}{2}&(2\nmid n) \end{cases} \] 使用第二种操作可以把整个串循环移位，使用第一种操作可以把前三位循环移位，结合一下就可以把任意三个位置循环移位。这样容易得到以下两种序列之一：\(1,2,\cdots,n-1,n\) 和 \(1,2,\cdots,n,n-1\)。对于奇数我们就已经证明完毕了。对于偶数的第二种情况，我们把 \(n-1\) 移到开头后再重复以上操作即可。

然后用这种黑科技计算答案即可。

1538. 一道难题

题目大意：给出一个数列 \(a\) 及 \(n,m\)，求 \(\displaystyle{\sum_{\prod_{i=1}^{n}a_{i}b_{i}=m}\frac{(\sum_{i=1}^{n}b_{i})!}{\prod_{i=1}^{n}b_{i}!}}\)。

题解：所求式子的组合意义相当于：有 \(n\) 种物品，第 \(i\) 种物品的价值为 \(a_{i}\)，任选一些物品做排列，求使得总价值为 \(m\) 的不同排列的数量。设 \(f(i)\) 表示价值为 \(i\) 的物品的数量，那么所求即为 \([x^{m}]\sum_{i=0}^{+\infty}f^{i}(x)=[x^{m}]\frac{1}{1-f(x)}\)。后面就是一个经典的 \(FFT\) 题了。

1553. 周期串查询

题目大意：给你一个数字字符组成的串，有一些区间修改，询问操作是问 \([l,r]\) 是否以 \(d\) 为周期。

题解：字符串 hash，用线段树维护。

1569. 二项式系数的个数

题目大意：求满足 \(0\le k\le n\le A\) 且 \(p^{\alpha}\mid{n\choose k}\) 的 \((n,k)\) 的个数

题解：使用库默尔定理就变成一道娱乐的数位 \(dp\) 题了。

时间复杂度 \(\mathcal{O}(\log^{2}_{p}A)\)。

1587. 半现串

题目大意：给出两个串 \(s\) 和 \(t(|t|=d)\)，称 \(s\) 在 \(t\) 中半现，当且仅当 \(s\) 有一个长度为 \(\lfloor\frac{d}{2}\rfloor\) 的子串同时也是 \(t\) 的子串。现给定数字串 \(s\)，求 \([x,y]\) 中 \(s\) 半现的数量。

题解：\(AC\) 自动机上数位 \(dp\)。

1728. 不动点

题目大意：设 \(f:\{1,2,\cdots,n\}\to\{1,2,\cdots,n\}\)，且 \(\overbrace{f\circ\cdots\circ f}^{k个}(i)=\overbrace{f\circ\cdots\circ f}^{k-1个}(i)\)，求所有满足要求的 \(f\) 的数量。

题解：设 \(F_{k}\) 为答案的指数型生成函数。那么显然 \(F_{1}=e^{x}\)。注意到答案等价于 \(n\) 个带标号点，高度不超过 \(k\) 的有向森林的数量。设 \(G_{k}\) 为连通的有向森林的指数型生成函数，那么 \(F_{k}=e^{G_{k}}\)。考虑求 \(G_{k}\)，我们可以枚举某一个点作为根，那么显然方案就是 \(nF_{k-1}(n-1)\)，化简计算一下可得 \(G_{k}=xF_{k-1}\)。因此 \(F_{k}=e^{xF_{k-1}}\)。