【题解】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组的所有情况。

整体算法也就明了了：

求出N位所在的Fibonacci表示的数的长度t
求1~t中Fibonacci表示中1出现的个数。
继续求解剩余字符的1。
最后一个暴力扫描

例如求解得到最后对应Fibonacci表示为x=100100

对于长度为1~5的Fibonacci表示中1的个数为 $sum[5]$ ，i<=100000中1的个数即为 $sum[5]+1$ 。
对于100000<i<=100100,最高位都是1，共有 $fib[3]$ 个，后三位1的个数为 $sum[2]+1$ 。
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)$