[NOI 2026] 布丁
建议删除此题，我毫无逻辑的搞都过了，明显不是题，纯看谁运气好。
题目链接： [NOI 2026] 布丁 。
题目描述：
有多次询问，每次询问交互库会生成一个数 www ，你需要实现函数 int find_tastiness(int c,int m) 猜测并返回这个 www 。
你可以调用函数 int query_tastiness(vector<int>S) ，该函数会将 www 加入 SSS 后排序并输出相邻两项的 gcd\gcdgcd 之和。
对于单组测试，你最多调用不超过 444 次该函数，传入的 SSS 最多不超过 353535 。如果你超过了限制，你会获得相应的部分分。
w∈[1,m],m=3000w\in[1,m],m=3000w∈[1,m],m=3000 。
时间限制 12s12s12s 。
交互库不是自适应的。
很明显 gcd\gcdgcd 的和不具备任何实际意义。你只能通过 query_tastiness 的结果和原来的 SSS 的相邻两项 gcd\gcdgcd 做差才能得到有效信息。不妨设 query(S) 的结果 ...
[NOI2024] 百万富翁
神仙题目。
写完后看题解发现没有一个用试图优化 DP 的，全都是注意力惊人。
题目链接： [NOI2024] 百万富翁 。
题目描述：
小 W 有一个长度为 nnn 的序列 www 。你可以经行多组询问。每一组询问里包含若干个普通询问。每一个普通询问为形如 (i,j)(i,j)(i,j) 的二元组，小 W 会对于每一组询问，一次性告诉你这一组里每一个普通询问 (i,j)(i,j)(i,j) 中 wiw_iwi 和 wjw_jwj 谁要更大。
你需要在不超过 TTT 组询问，一共不超过 SSS 个普通询问内找出数组的最大值。
有两个子任务：
子任务编号
TTT
SSS
nnn
111
111
499500499500499500
100010001000
222
888
109994410999441099944
100000010000001000000
交互库是自适应的。
子任务一直接两两枚举即可。
交互库自适应这一点可以告诉我们，对于一组点，如果我只能询问一组的话，一定需要两两枚举询问。因为如果我们哪怕少询问了一个点， ...
HDU20260820B 大户爱的硬币
第一道写出的计数题！！！！
题目描述：
一次抛硬币抛到正面的概率是 ppp 。
求 Var[Xk]Var[X^k]Var[Xk] ，其中 Var[X]Var[X]Var[X] 表示随机变量的方差（即 E[(X−E[X])2]E[(X-E[X])^2]E[(X−E[X])2] ）， XXX 表示第一次抛硬币抛到正面的次数。结果对 998244353998244353998244353 取模。
0<p<998244352,k≤2×1050<p<998244352,k\le2\times10^50<p<998244352,k≤2×105 。
看起来非常原题，且非常可以爆标。
首先， Var[X]=E[X2]−E[X]2Var[X]=E[X^2]-E[X]^2Var[X]=E[X2]−E[X]2 ，所以题目求的东西实际上是 E[X2k]−E[Xk]2E[X^{2k}]-E[X^k]^2E[X2k]−E[Xk]2 ，本质上是求 E[Xk]E[X^k]E[Xk] 。
考虑斯特林反演，则由期望的线性性得原式为 ∑i=0 ...
HDU20260820I 大改革
拿下首杀！！！！！！！！！
题目描述：
有 nnn 个变量，第 iii 个变量为 tit_iti ，有权重 ai,bia_i,b_iai,bi 。有三个变量 S1,S2,AS_1,S_2,AS1,S2,A ，初始为 000 。
你可以以任意顺序，对于每一个满足 ti≠0t_i\ne 0ti=0 的 iii 依次执行以下两个操作：
若 ai=tia_i=t_iai=ti ，则令 A←A+[S1≥c]+[S1≥−c]A\leftarrow A+[S_1\ge c]+[S_1\ge -c]A←A+[S1≥c]+[S1≥−c] ，然后令 S1←S1+1S_1\leftarrow S_1+1S1←S1+1 。否则令 A←A−[S1≤c]−[S1≤−c]A\leftarrow A-[S_1\le c]-[S_1\le -c]A←A−[S1≤c]−[S1≤−c] ，然后令 S1←S1−1S_1\leftarrow S_1-1S1←S1−1 。
若 bi=tib_i=t_ibi=ti ，则令 A←A+[S2≥c]+[S2≥− ...
[NOI 2026] 中位数
我声称摩卡串是简单好写好想题。
题目链接： [NOI 2026] 中位数 。
题目描述：
把长度为 nnn 的序列切成 kkk 段，要求每段中位数构成的序列的中位数最大。
5≤n≤106,2≤k≤n5\le n \le 10^6,2\le k \le n5≤n≤106,2≤k≤n 。
中位数的定义：长度为 mmm 的序列的中位数为第 ⌈m2⌉\lceil\frac{m}{2}\rceil⌈2m⌉ 大的数。
警示后人：
性质 A\text{A}A ， k mod 2≡0k\bmod 2\equiv 0kmod2≡0 和 k>5k>5k>5 是诈骗性质。
这个题目就是让你冲正解的，几乎没有部分分。
经典二分转 1,−11,-11,−1 序列 bbb 。
那么一个序列的中位数 ≥x\ge x≥x 的充要条件为序列的和 ≥0\ge 0≥0 。
现在问题变成了：判定一个 −1,1-1,1−1,1 的序列 bbb 是否能切成 kkk 份使得至少有 ⌈k2⌉\lceil\frac{k}{2}\rceil⌈2k⌉ 个子区间的和 ≥0\ge ...
哈集幂
哈集幂是啥？能吃吗？
位运算卷积
对于长度为 2n2^n2n 的序列 a,ba,ba,b ，定义 aaa 和 bbb 的卷积结果为 ccc 当且仅当：
∀i∈[0,2n−1], ci=∑j⊕kajbk\forall i\in[0,2^n-1],\ c_i=\sum_{j\oplus k}a_jb_k∀i∈[0,2n−1], ci=∑j⊕kajbk 。
对于 ⊕\oplus⊕ 分别为与运算，或运算和异或运算时，我们可以使用 FWT 求解 ccc 。
这个东西长得很像 FFT 的加法卷积形式，所以我们也考虑对序列 aaa 和 bbb 分别变换为 AAA 和 BBB 后点乘，之后再逆变换回来。
然后就是极具注意力的东西了。
或运算卷积
注意到 j∣k=i → (j∣k)∣i=ij|k=i \ \to \ (j|k)|i=ij∣k=i → (j∣k)∣i=i 且 j∣i=i,k∣i=i → (j∣k)∣i=ij|i=i,k|i=i \ \to \ (j|k)|i=ij∣i=i,k∣i=i&nb ...
另一个视角下的 FWT
一般的 FWT 的解释是直接利用分治和一些注意力注意到了一个变换方法。但是这个方法怎么来的，或者将题目变换以下，一般的解释就无能为力了。
此处提供另一种解释。
不妨假设我们要变换的数组为 fff ，变换的结果为 FFF 。
设 Fi=∑j=0n−1c(i,j)fjF_i=\sum_{j=0}^{n-1} c(i,j)f_jFi=∑j=0n−1c(i,j)fj 。
那么，容易发现，如果说卷积运算符为 ⊕\oplus⊕ ，那么只要满足 c(i,j)c(i,k)=c(i,j⊕k)c(i,j)c(i,k)=c(i,j\oplus k)c(i,j)c(i,k)=c(i,j⊕k) ，那么卷积就一定可以表示为这种变换后的结果的点乘。
那么问题就是如何作这种变换。
以二进制位运算卷积举例，我们可以发现一些性质：
Fi=∑j=0n−1c(i,j)fj=∑j=0n2−1c(i,j)fj+∑j=n2n−1c(i,j)fjF_i=\sum_{j=0}^{n-1} c(i,j)f_j=\sum_{j=0}^{\frac{n}{2}-1}c(i,j)f_j+\sum_{j=\fra ...
[NOI 2026] 传送 实现细节
上篇题解是口胡的，写完代码后感觉有点细节。
代码结构：
12345678910111213141516171819using ll=long long;using pli=pair<ll,int>;using V=vector<int>;ll gcd(ll a,ll b); // 最大公约数struct Q{}; // 有理数结构体namespace DFT{ // 点分树 int Min(int x,int y); // dfn-lca 比较函数 void dfs(int x,int fa); // dfn-lca 预处理函数 int lca(int x,int y); // dfn-lca 实现函数 int dist(int x,int y); // 距离函数 void getrt(int x,int fa); // 找重心 void dfs2(int x,int fa,int aim,int c[],ll res[],int &mx); // 对于每个分治重心，预处理距离 ...
[NOI 2026] 传送
NOI2026D1T1 线段：做干净的奥赛。
题目链接： [NOI 2026] 传送 。
题目描述：
一颗 nnn 个点的树。有 mmm 个询问，每次询问从 xxx 到 yyy 游走期望耗时有限且最短的时间为多少。对于一个节点 iii ，一次游走耗时一秒。每一次游走你可以选择移动到相邻节点或选择绝对随机的传送到一个点。
n≤5×105,m≤106n\le5\times10^5,m\le10^6n≤5×105,m≤106 。
简单题。
容易发现对于某一次询问 x→yx\to yx→y ，总有一个 kkk 使得距离 yyy 不超过 kkk 的所有点都会选择向 yyy 前进，其余点选择随机传送。并且这个 kkk 具有单调性，可以二分求出。对于树上 kkk 邻域数点，可以使用点分树在 O(logn)O(\log n)O(logn) 求解。总复杂度 O(nlog2n+q)O(n\log^2n+q)O(nlog2n+q) 。
代码不放了。
更优的 RMQ 问题解法
问题：给定长度为 nnn 的序列 aaa ，和 mmm 次询问。每次询问 [l,r][l,r][l,r] 内的最大值。
朴素解法
使用 ST 表可以做到 O(nlogn)∼O(1)O(n\log n)\sim O(1)O(nlogn)∼O(1) 。
设 fi,jf_{i,j}fi,j 表示 maxj≤k<j+2i{ak}\max\limits_{j\le k<j+2^i}\{a_k\}j≤k<j+2imax{ak} 。
那么就有 f0,i=aif_{0,i}=a_if0,i=ai ， fi,j=max{fi−1,j,fi−1,j+2i−1}f_{i,j}=\max\{f_{i-1,j},f_{i-1,j+2^{i-1}}\}fi,j=max{fi−1,j,fi−1,j+2i−1} 。
查询时设 k=⌊logn⌋k=\lfloor\log n\rfloork=⌊logn⌋ 。
那么答案为 max{fk,l,fk,r−2k+1}\max\{f_{k,l},f_{k,r-2^k+1}\}max{fk,l,fk,r−2 ...
