【题解】7月11日比赛题解备份
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
typedef long long LL;
LL calcfac(LL n)
{
if (n <P) return fac[n];
LL seg = n / P, rem = n % P;
LL ret = power(fac[P - 1], seg, P); //fac[P - 1]重复出现了seg次
ret = ret * fac[rem] % P; //除去seg次fac[P – 1]外，剩下的零头
cnt += n / P; //提出n / P个因子P
ret = ret * calcfac(n / P) % P; //递归处理
return ret;
}
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
