在新Blog上食用 重更Blog写道毒瘤题题解 CH5702 Count The Repetitions 题面  首先明确一个道理，即：conn(conn(s2,n2),m)=conn(s2,n2*m)[长得很像乘方运算] 所以可以求出一个最大的M，使得conn(s2,M)可以被conn(s1,n1)生成然后⌊M/n2⌋即为答案  我们考虑将M拆分为：M=2^k1+2^k2+2^k3+...+2^kn于是效率就有了大幅的提升  再考虑使用DP。定义状态f[i][j]表示从s1[i]开始用多少个字符可以凑成conn(s2,2^j)然后就是状态转移方程： f[i][j]=f[i][j-1]+f[(...

根据欧拉函数的定义，令 是 的第 个因数，且满足。 则这样的x有 个， 两边同乘以 ， 即可推出 。（显然）  以内与 的最大公约数为 的数有个。  与所有小于 的数的最大公约数之和为  for(i=1;i<=n;i++) //枚举n的约数 if(n%i==0) f[n]+=phi[n/i]*i; 外层还要枚举每个数字，故时间复杂度为 可惜要T。 那么就可以优化一下，枚举那个公因数，累加答案。 见代码： #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib&g...

TO BE CONTINUED 注：最近较忙，只贴代码，详解请等待 正解：二分+DP 因为数据太水 咳咳... 某些玄学DP也能过 但是最近我加强了一波数据，所以玄学DP过不了第11个点 所以是这样的： #include<iostream> #include<cstdio> using namespace std; int n,a[20001],mx[20001],mn[20001],ans; int check(int x) { mn[1]=mx[1]=a[1]; for(int i=2;i<=n;i++) mx[i]=min(a[i],a[1]-mn[i-1]...