【题解】7月11日比赛题解备份

【题解】7月11日比赛题解备份

Wed Jul 12 2023
7 分钟

一.重复字符串(powerstr):#

30分做法:枚举

长度范围只有 1000 时,我们可以枚举 k, 取字符串第 1 个到第 k 个字符作为子串 T,然后去验证剩下的字符串是否都是 T 重复得来

时间复杂度 O(n^2)

100分做法:KMPNext数组

假设字符串为 S,长度为 N,子串 T 重复 K 次后得到串 S,那么 T 的长度一定为 L = N/K(要整除),则T=S[1...L]T = S[1...L],将 S 拆分成 K 份,每份长度为 L,则有

S[1...L]=S[L+1...2L]=S[2L+1...3L]=...=S[(K1)L+1...KL]S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]

由于要保证 K 最大,势必 L 要取最小,所以根据 Next 函数的定义,有Next[KL]=(K1)L;Next[KL] = (K-1)L;

Next[N]=NLNext[N] = N - L,所以L=NNext[N];L = N - Next[N];

但是得出的长度 L 还要保证能被 N 整除,所以如果不能整除说明 L = N,即 K = 1;而如果能整除,那么K=N/(NNext[N]);K = N / (N - Next[N]);

因而我们只要对字符串 S 做一趟 KMP,对其求 Next 数组,剩下的就是上述结论

时间复杂度O(n)O(n)

二.Fibonacci 进制(fib):#

100分做法:DP

N 很大,先尝试几个小数据。可以发现,每个 Fibonacci 表示的长度,和 Fibonacci 数大小有关(1,2,3,5,8,13,21……),这些值最高位上是 1,后面全是 0,即第一个 Fibonacci 表示长度为 i 的数是fib[i]fib[i]。因此按照长度对 Fibonacci 表示进行分类,长度为 i 的数有fib[i1]fib[i-1]个,看做是第 i 组。那么第 i 组的总长度len[i]=fib[i1]ilen[i] = fib[i-1]*i

接下来,看 1 出现的次数。长度为 i 的数的表示中,第 i-1 位肯定是 0。

Sum[i]Sum[i]表示前 i 组的 1 的个数。可以得到如下式子:Sum[i]=sum[i1]+fib[i1]+sum[i2]Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]。第 i 组首位 1 的个数为fib[i1]fib[i-1]i1i-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]sum[5],i<=100000 中 1 的个数即为sum[5]+1sum[5]+1

  2. 对于 100000<i<=100100,最高位都是 1,共有fib[3]fib[3]个,后三位 1 的个数为sum[2]+1sum[2]+1

  3. 1 的总个数为sum[5]+1+fib[3]+sum[2]+1sum[5]+1+fib[3]+sum[2]+1

最后细节比较多,要实现的仔细一些。

三.发奖金(reword):#

100*分做法:组合+质因数分解+逆元+中国剩余定理

题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m,那么就等价于求方程x1+x2+...+xn=mx_{1} + x_{2} + ... + x_{n} = m的解的个数,利用插板法可得到公式:C(n+m1,m)C(n + m - 1, m) 现在要求不大于 m 的,相当于对i=0...mi = 0 ... mC(n+i1,i)C(n + i - 1, i)求和,根据 pascal 递推式可以得到答案为C(n+m,m)C(n + m, m) 现在就需要求C(n+m,m)modPC(n + m, m) \mod P

这里我们主要要解决如何快速计算n!modPn! \mod P

以及当分母有m!modPm! \mod P的情况

1.      当 n,m 都比较小的时候,同时 P 为比较大的素数时,可以直接利用逆元求解,当 n,m 比较大的时候,见下面两种情况(以下参考魏铭 2011 年国家集训队作业)

2.      当 P 为素数的情况:

我们发现n!modPn! \mod P的计算过程是以 P 为周期的,举例如下:

n=10,P=3n = 10, P = 3 n!=12345678910n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 =12457810369= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9 =(12)333(123)= (1 * 2)^3 * 3^3 * (1 * 2 * 3)

最后一步中的1231 * 2 *3可递归处理。

因为 P 的倍数与 P 不互质,所以 P 的倍数不能直接乘入答案,应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。

我们提前预处理出fac[i]=123(i1)imodPfac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P,函数 calcfac(n)返回n!modPn! \mod P的值,power(a, b, c)返回abmodca^b \mod c的值,可用快速幂在O(logb)O(logb)的时间内完成。

CPP
1
2
3
4
5
6
7
8
9
10
11
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!modpn! \mod p的计算可在O(logn)O(logn)的时间内解决。

对于分母中的 n!,方法是相似的。若 a 为正整数,aa=1(modP)a * a’ = 1(\mod P),那么我们称 a’为 a 的逆元,记作 a-1,并有b/a(modP)=ba1(modP)b / a(\mod P) = b * a-1(\mod P)。这样我们只需要把预处理fac[i]=123(i1)imodPfac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P更换为inv[i]=112131(i1)1i1modPinv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P,其计算方法与分子中的 n!计算相差无几,具体可参考我的代码。求逆元可以使用扩展欧几里得算法。

3.      当 p 为合数时

对于某些测试点,我们发现 P 分解后只有 2 个因子,并且不相同,所以我们可以对这两个因子分别运行算法 2,最后用中国剩余定理合并即可。

对于剩下的数据,可以对 P 进行质因数分解,得到P=p1c1p2c2ptctP = p1^{c1} * p2^{c2} * … * pt^{ct}

对于每个1it1≤i≤t,以picipi^{ci}为模运行算法 2,最后用中国剩余定理合并。这里picipi^{ci}不一定为质数,不过只需对原算法稍加修改即可。令P=piciP = pi^{ci}fac[i]=除去pi的倍数外i的阶乘fac[i] = 除去pi的倍数外i的阶乘。例如pi=3,ci=2pi = 3,ci = 2,那么fac[10]=12457810fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10,除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的,calcfac(n)与算法 2 主体相同,只是统计因子个数时,应使用ret+=n/piret += n / pi而不是ret+=n/Pret += n / P,递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。

时间复杂度O(tn)O(t * n)