2020杭电多校赛 Multi-University Training Contest

第一场多校 出题人 朝鲜MUTC KUT Round

1005_6755 Fibonacci Sum: 二次剩余_Fib的k次幂和

链接
传送门: here
题意
$1\le n,c\le 1e18,1\le k\le 1e5$
$Fib1=1,Fib1=1,Fi{b}_n=Fi{b}_{n-1}+Fi{b}_{n-2}$
求$Fi{b}_0^k+Fi{b}_c^k+Fi{b}_{2c}^k+...+Fi{b}_{nc}^k,mod=1e9+9$

前请提要
有关取模、同余、逆元的一些东西：
$fib[n]=\frac{\sqrt{5}}{5}\times [(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n]$
$p=1e9+9$
二次剩余：
$383008016^2\equiv 5(modp)$
$383008016\equiv \sqrt{5}(modp)$
$\frac{1}{\sqrt{5}}\equiv 276601605(modp)$
$383008016的逆元=276601605$
$(1+\sqrt{5})/2\equiv 691504013(modp)$
$383008017\times 2的逆元=691504013$
$(1-\sqrt{5})/2\equiv 308495997(modp)$
$(p-383008016+1)\times 2的逆元=308495997$

$fib[n]=276601605\times [(691504013{)}^n-(308495997{)}^n](modp)$
$fib$前$n$项和等比数列求和：$sum=\frac{a}{a-1}\times (a^n-1)(modp)=a^2(a^n-1)(modp)=a^{n+2}-a^2(modp)$
当$p=1e9+9,a=691504013或308495997时成立$。
思路
通过上面我们知道，在模$p=1e9+9$意义下有:
$fib[n]=276601605\times [(691504013{)}^n-(308495997{)}^n](modp)=d\times (a^n-b^n)$
$fi{b}_{nc}=d\times (a^{cn}-b^{cn})=d\times (A^n-B^n)=Fib{C}_n，A=a^c,B=b^c$
$(\frac{1}{d}fi{b}_{nc}{)}^k$二项式展开有：
$$C_k^0(A^n{)}^k+(-1{)}^1{C}_k^1(A^n{)}^{k-1}(B^n)+(-1{)}^2{C}_k^2(A^n{)}^{k-2}(B^n{)}^2+...+(-1{)}^r{C}_k^r(A^n{)}^{k-r}(B^n{)}^r+...+(-1{)}^{k-1}{C}_k^{k-1}(A^n)(B^n{)}^{k-1}+(-1{)}^k{C}_k^k(B^n{)}^k$$
$$C_k^0(A^k{)}^n+(-1{)}^1{C}_k^1(A^{k-1}{)}^n(B{)}^n+(-1{)}^2{C}_k^2(A^{k-2}{)}^n(B^2{)}^n+...+(-1{)}^r{C}_k^r(A^{k-r}{)}^n(B^r{)}^n+...+(-1{)}^{k-1}{C}_k^{k-1}(A{)}^n(B^{k-1}{)}^n+(-1{)}^k{C}_k^k(B^k{)}^n$$
现在我们要求$FibC$的前$n$项和，我们$O(k)$枚举$C_k^r$，逐项求出前$n$项和再累加即可。
对于$(-1{)}^r{C}_k^r$而言，令$a=A^{k-r}{B}^r$，前$n$项和为$(-1{)}^r{C}_k^r\times \frac{a\times (a^n-1)}{a-1}$
可以加的几个优化：

• 欧拉降幂，$n,c\le 1e18,p=1e9+9$，$a^n(modp)=a^{n\%\varphi (p)}(modp)$ ^_^
• $a=A^{k-r}{B}^r$没有必要预处理，我们可以在线求，令$a=A^k$，然后$a=a\ast b\ast inv(a)$即可
• 同理$a^n$也可以在线求，然后就过了。

备注
参考：ACDreamers
AC_CODE
here

1006_6756 Finding a MEX: 分块_线段树_树状数组

链接
传送门: here
题意
$n,m,q\le 1e5$无向图, $S_u=\{A_v|(u,v)\in E\}$,$F_u=mex(S_u)$
$type1:1ux,change{A}_u=x$
$type2:2u,query{F}_u$
思路
度数大于$\sqrt{m}$的超级点不超多$\sqrt{m}$个。
小点暴力算，超级点用分块或者bit，线段树
分块复杂度$O(n\ast \sqrt{n})$, 1170ms
线段树复杂度$O(n\ast \sqrt{n}\ast log(n))$, 1560MS
树状数组+二分求mex复杂度$O(n\ast \sqrt{n}\ast log(n)\ast log(n))$, 1092MS
树状数组求mex复杂度$O(n\ast \sqrt{n}\ast log(n)\ast log(n))$, 1762MS
动态开点线段树TLE
分块维护每个块内数字第一次出现的次数，$O(\sqrt{n})$修改，$O(\sqrt{n})$查询
线段树维护mex其实就是维护最小值
备注

AC_CODE
分块，线段树，树状数组求mex，树状数组+二分求mex

1009_6759 Leading Robots: 优先队列贪心

链接
传送门: here
题意
有$n(1e5)$辆车在数轴正半轴，每个车在初始位置在$p_i$、初速度$0$，加速度$a_i$，可能有车信息完全相同，问有多少辆车存在某一个时刻它走在当之无愧的第一名，也就是没有并列。
思路
1.把所有车子$unique$一下，相同车子记录他的个数(当然如果它个数大于$1$，我是不会算它的贡献滴)
2.用单调栈预处理一下，去掉永远不可能在第一位的车子。
3.用$rs[]$记录每个车子下一个要超过的车子的编号
4.优先队列保存每个车子$i$超过车子$rs[i]$的时间，优先队列每次取出时间最短的那个车子
6.判断他是否超车到了第一位，若是就记录，并且若这是最初排在最后一位的车子就break结束
5.然后去掉$rs[i]$这个车子，因为他还没到第一就已经被车子$i$超车了
6.复杂度$O(n\ast log(n))$
备注
去年多校也有一个车子过红绿灯贪心题HDU Vacation
AC_CODE
here

第二场多校 出题人 Claris

1007 In Search of Gold: 二分+树dp

链接
传送门: here
题意
$n(2e4),k(20)$，$n$个节点的树，每条边有两种长度属性$(a,b)$，已知恰好有$k$条边长度
属性为$a$，其他边均为$b$，问这种树的直径最小可能时多少。
思路
二分答案+树形DP
初始化$dp[u][0]=0,dp[u][1-k]=INF$
$dp[u][i]$表示u的子树内有$i$条边选择树形值$a$的情况下的最长叶子路径
状态转移时确保直径小于等于$mid$即可。
若$dp[1][k]\le mid$表示有解。
备注
AC_CODE
here

第三场多校 出题人 Tokitsukaze and Her Friends

1006_6796 X Number: 数位dp

链接
传送门: here
题意
$f(x)$等于$x$中出现次数最多的那一个数字。
问$l,r$中有几个数字$f(x)=d,0\le d\le 9$.
思路
$数位dp$同时要记录前面各位选的数字的次数，可用大小为$10$的$array$存起来
为了保证能正确的记忆化，这个$array$应该占$dp$的一维状态，所以只能用$map$表示$dp$状态
$map<array<int,10>,int64>dp[d][pos][leadZero]$
表示只考虑$d$类数，$pos$前的位数，是否有前导$0$，数字使用情况为$array$的合法方案数。
仅当$!limit$时才记忆化。

当数字使用情况为$array$所记录，且还能使用$pos$位任意$0-9$数字时，想要让众数为d的方案数
可以使用$母函数DP$写出来，复杂度$O(n^4)$。

算法时间复杂度我猜为 $O(进制数\ast 位数+进制数\ast 新增状态数\ast 18^4)$
备注

AC_CODE
here

第四场多校 出题人 Hangzhou Xuejun Contest

第五场多校 出题人 福州大学

1007 Tree: 优先队列贪心维护换根dp

链接
传送门: here
题意
$n(2e5)$个点的带边权的树，选出一个连通子图，保证至多只有一个点的度数可以大
于$k(0\le k<n)$，问这种子图的最大边权和。
思路
换根$dp$+优先队列贪心
$dp[u][0]$表示至多选出$u$的$k-1$个子树的最大边权和
$dp[u][1]$表示至多选出$u$的$k$个子树的最大边权和
$dp[u][1]={\sum }_{maxkv}(dp[v][0]+w_{uv})$
选出最大的$k$个$dp[v][0]+w_{uv}$转移即可，优先队列贪心维护最大的$k$个。
$k\_son\_val[u]$表示$u$的第$k$大的子树权值和：$dp[v][0]+w_{uv}$
$max\_k1\_son[v]$表示$v$是否属于其父亲子树中权值和最大的$k-1$个子树
备注

AC_CODE
here

第六场多校 出题人 USETC

1001 Road To The 3rd Building: 期望线性性

链接
传送门: here
题意
$n(2e5)$的序列，求每个区间平均值的期望。
思路
算每个数字的期望加起来即可。
备注
AC_CODE
here

1005 Fragrant numbers: 区间DP

链接
传送门: here
题意
求114514191911451419191145141919一个最短前缀，添加任意(,),+,*后数值为$n(5000)$.
思路
$O(13^3\ast n^2)$区间dp即可。
备注

1007 A Very Easy Math Problem: 莫比乌斯反演

链接
传送门: here
题意
$T\le 1e4,n\le 2e5,k,x\le 1e9$
求：
$$\sum _{a_1=1}^n...\sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)\times f(gcd(a_1,...,a_x))\times gcd(a_1,...,a_x)$$
思路
$$\sum _{a_1=1}^n...\sum _{a_x=1}^n(\prod _{j=1}^x{a}_j^k)=(\sum _{i=1}^n{i}^k{)}^x$$
容易推导出：
$$\Downarrow$$
$$\sum _{d=1}^{n}f(d)d^{xk}\sum _{p=1}^{\frac{n}{d}}\mu (p)\times p^{xk}\times S(\frac{n}{pd})$$
比赛时的测评机全部预处理$O(n\times \sqrt{n}+T\sqrt{n})$即可通过，比赛后的测评机记忆化处理也能过。
还可以进一步优化。
$$\Downarrow$$
$$T=pd,\sum _{T=1}^{n}S(\frac{n}{T})\times T^{xk}\sum _{p|T}\mu (p)f(\frac{T}{p})$$
备注
由于出题人不卡时限，所以$O(n\times log(n)+T\sqrt{n})$或者$O(n+T\sqrt{n})$均可以通过。
AC_CODE
here
线性筛代码：

const int mod = 1e9 + 7;
int fpow (int a, int b) { int ret = 1; while (b) { if (b & 1) ret = 1ll * ret * a % mod; a = 1ll * a * a % mod; b >>= 1; } return ret; }
int add (int a, int b) { return (a += b) >= mod ? a - mod : a; }
int sub (int a, int b) { return (a -= b) >= 0 ? a : a + mod; }
int mul (long long a, int b) { return a * b % mod; }
int inv (int a) { return fpow(a, mod - 2); }
int p[N], pc;
bool ptag[N];
int f[N], low[N];
void sieve (int n = N - 1) {
	f[1] = low[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!ptag[i]) {
			p[++ pc] = i;
			f[i] = sub(i, 1);
			low[i] = i;
		}
		for (int j = 1, k; j <= pc && i * p[j] <= n; j++) {
			ptag[k = i * p[j]] = 1;
			if (i % p[j]) {
				low[k] = p[j];
				f[k] = mul(f[i], f[p[j]]);
			} else {
				low[k] = low[i] * p[j];
				if (low[i] == i) {
					if (low[i] == p[j])
						f[k] = sub(mod, p[j]);
					else 
						f[k] = 0;
				} else
					f[k] = mul(f[i / low[i]], f[low[i] * p[j]]);
				break;
			}
		}
	}
}

1008 Yukikaze and Smooth numbers: min25筛

待补

CCPC网络赛 出题人：北大出题组

Xor: 数位dp

题意
$T:2e3$, $abcd:1e9$
问有多少对$(x,y)$满足$|x-y|\le c$且$x⨁y\le d,0\le x\le a,0\le y\le b$。
链接：点我点我
思路
两个限制条件：

• $xor$
  ip1 = 1 means equal to c, ip1 = 0 means less than c
• $abs$
  $|x-y|\le m⟹x-y\le m\&\&x-y\ge -m$
  $⟹m-x+y>=0\&\&m+x-y>=0$.
  $m,x,y$ 可取 0 或 1, 上述式子取值可以是 $-1,0,1,2$.
  若$[高位]\ge 1$ , 后面数位就算全取-1最后结果还满足条件，$x,y$取值不受限制。此位就算大于1也可以按1考虑；
  若$[高位]<-1$ ,后面就算全取2也一定不行 ，所以直接返回0就行；
  又因为只有两个值同时大于等于1的时候才可以返回1。
  所以只需考虑上述式子取值为1或0或-1的情况。
  为避免负数下标，令-1为0，0为1，1为2

AC_CODE
here