[SDOI2015] 约数个数和
第一步可参考第一篇题解。
∑i≤n∑j≤md(ij)\sum_{i \le n}\sum_{j \le m}d(ij)
i≤n∑j≤m∑d(ij)
=∑i≤n∑j≤m∑k∣i∑l∣j[(k,l)=1]=\sum_{i \le n}\sum_{j \le m}\sum_{k \mid i}\sum_{l \mid j}[(k,l)=1]
=i≤n∑j≤m∑k∣i∑l∣j∑[(k,l)=1]
=∑i≤n∑k∣i∑j≤m∑l∣j[(k,l)=1]=\sum_{i \le n}\sum_{ k \mid i}\sum_{j \le m}\sum_{l\mid j}[(k,l)=1]
=i≤n∑k∣i∑j≤m∑l∣j∑[(k,l)=1]
由于枚举 i≤ni \le ni≤n ，再枚举 iii 的因数，等价于先枚举 i≤ni \le ni≤n ，再枚举 iii 的倍数， jjj 同理。而 iii 的倍数有 ⌊ni⌋\lfloor \frac{n}{i} \rfloor⌊in⌋ 个， jjj 同理，所于原式等价于：
∑i≤n⌊ni⌋∑j≤m⌊ ...
[ICPC 2018 Xuzhou R] Rikka with Minimum Spanning Trees
简单题。
题目链接： [ICPC 2018 Xuzhou R] Rikka with Minimum Spanning Trees 。
题目描述：
给一个 nnn 点 mmm 边的图，求最小生成树的边权和乘最小生成树个数的结果，对 109+710^9+7109+7 取模。
给定随机的输入方式。 n,m≤105n,m\le 10^5n,m≤105 。
123456789101112131415161718192021unsigned long long k1, k2;unsigned long long xorShift128Plus() { unsigned long long k3 = k1, k4 = k2; k1 = k4; k3 ^= k3 << 23; k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26); return k2 + k4;}int n, m, u[10000 ...
Day 0
还记的上次试机是因为换系统了……
这次试机本以为只是试机，结果题目上面居然不是 A+B\large A+BA+B ，而是大大的 FILL\large FILLFILL 。我推了 1 个小时连 n=2n=2n=2 都不会写，最后跟我说要用那个引理……
还好省选不会再考这个我学都没学的东西了……
Day 1
一看 T1 居然是一个期望题目，耗费了 1 个小时推样例没有退出来，换下一题。
T2 还是很良心的，给了 151515 分暴力，剩下的推了一会儿性质 A ，写完后就有了 303030 分啦！
看到 T3 ，没想到省选还会有 SpecailJudge 。甚至输出 Yes 和 No 都有 50%50\%50% 的分数，或许今天就有 100 分了？
哼唧哼唧推了 1 小时，结果发现自己连 Yes 和 No 都不会，这题还是太难了，只能打完暴力走了。
T2T3 太难了！
最后一个多小时回看 T1 ，发现求轻边数量的期望和求某条边是重儿子的概率是等价的，十分兴奋的以为自己 Day1 就要切题目了，结果最后发现自己不会算概率，最后黯然离场……
估计 8+30+12=50 。
D ...
ABC474
比赛链接： ABC474 。
A. Not X
题目描述：
给一个 X∈{1,2,3}X\in\{1,2,3\}X∈{1,2,3} 。
输出一个 {1,2,3}\{1,2,3\}{1,2,3} 内与 XXX 不同的整数。
未识别到题目。
B. Exit Order
题目描述：
给一个排列 ppp ，将排列 101010 个一分组之后，判断是否每一组都满足他们是对应下标的排列。
未识别到题目。
C. Remove and Append
题目描述：
给一个排列 ppp ， QQQ 次操作，每次将一个元素 xxx 移到最后。求最终排列。
记录每一个元素最后一次出现的位置即可。
D. Outweigh
题目描述：
构造一个序列 www ，满足 ∑i=1naiwi>∑i=1nbiwi\sum\limits_{i=1}^n a_iw_i>\sum\limits_{i=1}^n b_iw_ii=1∑naiwi>i=1∑nbiwi 。
或输出无解。
wi∈[1,1018]w_i\in[1,10^{18}]wi∈[1,1018] 。
...
[NOIP2022] 喵了个喵
zhennanxie
题目链接： [NOIP2022] 喵了个喵 。
题目描述：
有 nnn 个栈，长度为 mmm 的序列 aaa ，满足 ai∈[1,k]a_i\in[1,k]ai∈[1,k] 。
有两种操作：
1 x 。取出序列第一个元素并置于栈 xxx 的栈顶。若栈 xxx 的栈顶拥有两个相同元素，则删去他们。
2 x y 。若栈 xxx 和 yyy 的栈底元素一样，则删去他们。
请合理构造使得最终序列和所有栈均为空。
数据保证有解。
数据范围（多测）：
1≤n≤3001\le n \le 3001≤n≤300 。
k∈{2n−2,2n−1}k\in\{2n-2,2n-1\}k∈{2n−2,2n−1} 。
∑m≤2×106\sum m \le 2\times10^6∑m≤2×106 。
Case #1: k=2n−2k=2n-2k=2n−2
置空一个栈，其余栈最多每个有 222 个元素。
容易发现极限情况是所有可使用的栈全部被沾满，此时由于我空出了一个栈，所以所有元素都可以被消去。
简单模拟就行。
Case #2: n=2n=2 ...
[CSP-S 2025] 员工招聘
切掉了 /cy
题目链接： [CSP-S 2025] 员工招聘 。
题目描述：
有 nnn 个数，第 iii 个数为 cic_ici 。还有一个长度为 nnn 的 010101 串 sss 。
一个长度为 nnn 的排列 ppp 合法当且仅当：
依次考虑 i=1,2,⋯ ,ni=1,2,\cdots,ni=1,2,⋯,n 并初始化计数器 C=0C=0C=0。
若 cpi≤Cc_{p_i}\le Ccpi≤C 或 si=0s_i=0si=0 ，则 C+1→CC+1\to CC+1→C 。
若最终 C≤n−mC\le n-mC≤n−m ，则排列 ppp 合法。
求有多少种合法的排列 ppp ，对 998244353998244353998244353 取模。
n≤500n\le 500n≤500 。
定义 fi,j,kf_{i,j,k}fi,j,k 为考虑 sss 的前 iii 个字符，有 jjj 个数使得 C+1→CC+1\to CC+1→C ，有 kkk 个数满足他们的 ccc 比 jjj 大且不考虑这些数具体是什么的合法排列数。 ...
[湖北省队互测2014] 一个人的数论
我必须承认我现在一点注意力都没有
题目链接： [湖北省队互测2014] 一个人的数论 。
题目描述：
给定 nnn 的质因数分解方式 ∏i=1wpiai\prod\limits_{i=1}^w p_i^{a_i}i=1∏wpiai ，求：
(∑i=1nik[i⊥n]) mod (109+7)(\sum_{i=1}^n i^k[i\perp n])\bmod (10^9+7)
(i=1∑nik[i⊥n])mod(109+7)
保证 1≤w≤1031\le w \le 10^31≤w≤103 ， 2≤pi,ai≤1092 \le p_i,a_i \le 10^92≤pi,ai≤109 ， 1≤k≤1001\le k \le 1001≤k≤100 。
设 F(n)=∑i=1nikF(n)=\sum\limits_{i=1}^n i^kF(n)=i=1∑nik ， G(n)=∑i=1nik[i⊥n]G(n)=\sum\limits_{i=1}^n i^k[i\perp n]G(n)=i=1∑nik[i⊥n] ，则注意到：
F(n)= ...
[ABC226H] Random Kth Max
Random Kth Max is the same.
题目链接： [ABC226H] Random Kth Max 。
题目描述：
nnn 个随机变量，第 iii 个随机变量 XiX_iXi 服从在 [Li,Ri][L_i,R_i][Li,Ri] 上连续均匀分布。
求第 kkk 大的数的期望。
n≤50n\le 50n≤50 ， 0≤Li<Ri≤1000\le L_i<R_i\le 1000≤Li<Ri≤100 。
考虑 min-max 容斥，则：
E[maxk{X1,X2,⋯ ,Xn}]=∑T⊆{1,2,⋯ ,n}(−1)∣T∣+k(∣T∣−1k−1)E[mini∈T{Xi}]=∑T⊆{1,2,⋯ ,n}(−1)∣T∣+k(∣T∣−1k−1)∫ab∏i∈TPr[Xi≥v]dv\begin{aligned}
E[\max_k\{X_1,X_2,\cdots,X_n\}]&=\sum_{T\subseteq\{1,2,\cdots,n\}}(-1)^{|T|+k}\binom{|T|-1}{ ...
[ICPC 2016 NAIPC] Jewel Thief
逆天背包。
题目链接： [ICPC 2016 NAIPC] Jewel Thief 。
题目描述：
给 nnn 个物品，每个物品有价值 viv_ivi 和重量 wiw_iwi ，你需要对于每一个 1≤i≤k1\le i \le k1≤i≤k ，求出大小为 iii 的背包的最大价值。
1≤n≤1061\le n\le 10^61≤n≤106 。
1≤k≤1051\le k \le 10^51≤k≤105 。
1≤vi≤1091\le v_i\le 10^91≤vi≤109 。
1≤wi≤3001\le w_i\le 3001≤wi≤300 。
一个普通的背包 DP ，但是直接背包复杂度 O(nk)\mathcal{O}(nk)O(nk) ，过不了。
考虑从 wi≤300w_i\le 300wi≤300 入手。不妨把所有的相同重量的物品经行分组，同组内的按权值从大到小排序后累加的前缀和数组为 ai,ja_{i,j}ai,j ，共有 szisz_iszi 物品。
那么写出 DP 式子（不妨设这一轮 DP 结果 ...
[APIO 2026 中国赛区] 蛋糕
简单题，但是考场看错题了 be like 。
题目链接： [APIO 2026 中国赛区] 蛋糕 。
题目描述：
你可以选择一个长度不超过 NNN ，值域在 [1,W+200][1,W+200][1,W+200] 的序列 aaa 。并实现函数 vector<int> bake_cakes(int N,int W,int K) 返回你选择的序列。
有多次独立的询问，每次询问交互库会往你的序列 aaa 中加入一个值域 [1,W][1,W][1,W] 的数字 www ，并将你的序列排序。
设排序后的数组为 bbb ，长度为 m+1m+1m+1 。则你需要实现函数 int find_tastiness(int m,int W,int K) 返回交互库往你的数组中加入的数字 www 。
你可以在你的函数中调用函数 int compare_tastiness(vector<int>S1,vector<int>S2) 。该函数调用时需要满足 S1∩S2=∅S_1\cap S_2=\varnothingS1∩S2=∅ ...
