[SDOI2015]约数个数和题目描述设\(d(x)\)为\(x\)的约数个数，给定\(n,m\)，求\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]输入格式输入文件包含多组测试数据。第一行，一个整数\(T\)，表示测试数据的组数。接下来的\(T\)行，每行两个整数\(n,m\)。输出格式\(T\)行，每行一个整数，表

题意给定一个\(2\timesN\)的网格，网格上的点和上下左右连边。要求支持以下几种操作：修改某条边的边权。求满足\(y\in[l,r]\)的点构成的点集的最小生成树。分析这道题的想法和P4246[SHOI2008]堵塞的交通很相似。注意到\(N,M\leq6\times10^4\)，并且查询的是

假如将所有激光武器放在一边，所有机器人放在一边，激光武器向它可以伤害的机器人连边，再加超级源/汇点，这就是一个网络流问题。考虑激光武器向机器人连的边容量无限，而机器人向超级汇点连的边容量为机器人的装甲值，而超级源点连向激光武器的边则是用时\(\times\)激光武器伤害。发现假

题意求：\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]其中\(d(n)\)代表\(n\)的约数个数。Sol考虑拆开\(d(ij)\)，平凡的想法是考虑\(i\)和\(j\)分别对\(d(ij)\)提供因子。注意到若\(i\)能提供完因子\(p\)，那么直接从\(i\)里取即可。否则需要在\(j\)里取因子

[SDOI2015]寻宝游戏题目大意给你一棵树，边有边权，现在每个村庄可能会突然有宝藏，又可能会突然没宝藏。若可以随意选择起点，问每次修改后从起点遍历完所有宝藏再回到起点的最短路径长度。难度：七星（满分十星）题解注：\(dis(x,y)\)为\(x\)到\(y\)的距离。若目前有的点按照\(df

题目分析虽然数据范围只有\(n\le60000\)，但是完全可以直接用线段树做。首先考虑那种状态的图在左边和右边加入节点和边之后可以连通。容易发现，这种图有这两个性质：至少有一条路径，经过最左端和最右端中的点。所有点至少和最左端和最右端的点连通。于是可以划分成以下几种状态

其实就是动态维护包含所有关键点的极小联通子树边权和。暴力做法只要子树内有关键点就去遍历，所以按照DFS序顺序去遍历这些关键点肯定是没问题的。用set维护即可。在\(x\)和\(z\)之间加入\(y\)，答案加上\(dis(x,y)+dis(y,z)-dis(x,y)\)，删除就反过来。

题目链接description给定一个质数\(m\)，以及\(n,x\)和集合\(S\)。从集合\(S\)中任意选数构成长度为\(n\)的数列（一个数可以选多次），求数列元素乘积模\(m\)等于\(x\)的数列的数量。模\(1004535809\)。\(3\leqm\leq8000\)\(1\leqn\leq10^9\)\(|S|\leqm,0\leqx<m

洛谷传送门感觉挺综合的一道题。考虑朴素dp，\(\forallx\inS,f_{i+1,jx\bmodm}\getsf_{i,j}\)。复杂度\(O(nm^2)\)。显然可以矩乘优化至\(O(m^3\logn)\)，但是不能通过。如果转移式中是加法而不是乘法，那很容易卷积优化。接下来是一个很重要的套路：化乘为加。实数

[SDOI2015]约数个数和https://www.luogu.com.cn/problem/P3327\(d(x)\)为\(x\)的约数个数,有\(T\)组询问,每次询问\[\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\]的值.\(1\le

简要题意\(T\)组数据，每组数据给出\(n,m\)，计算：\[\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d\midij}{1}\]\(1\leqT,n,m\leq5\times10^4\)思路又是推式子好题，不过这