[ABC310F] Make 10 Again
分母是 \(\prod a_i\)，只需求分子。
首先要发现投出了 \(10\) 以上的点数是无用的，所以只需考虑 \(10\) 以内的。
思考如何计数，发现转移依赖于前面的点数和的方案数，而且 \(10\) 很小，考虑状压 DP，设 \(f_{i,s}\) 表示前 \(i\) 个骰子，状态为 \(s\) 的方案数，转移不表。
\(s\leq M=2^{11}\)，所以时间复杂度 \(\mathcal{O}(nM10^2)\)。
[ARC174E] Existence Counting
怎么就没想到呢？？一直想着直接计数，比较困难，正难则反，转化为：排列数 \(-\) 没出现 \(x\) 的排列数 \(-\) 字典序大于 \(P\) 的方案数 \(+\) 既没出现 \(x\) 字典序还大于 \(P\) 的方案数。转化后就比较基础了。
[ARC173C] Not Median
感觉还是不够。
直觉告诉我们，答案大多数都很小。
注意到答案很大的地方周围应该长这样 -+-+-+0-+-+-+，这告诉我们只需找到两个相邻的值又同时在 \(p_i\) 一侧的就好了。
每个点都往左右扫，复杂度看似 \(\mathcal{O}(n^2)\)，但是其实在 \(i\) 和 \(x_1,x_2\) 之间的所有数答案一定是 \(3\)，这意味着每个数只会被扫一遍。所以时间复杂度 \(\mathcal{O}(n)\)。
[ABC281G] Farthest City
将所有点按最短路分层，每层的节点只能和相邻层还有层内的节点连边。设 \(f_{i,j}\) 表示用了 \(i\) 个点，最后一层有 \(j\) 个点的方案。转移：
\[f_{i,j}=\sum\limits_{k=1}^{i-j}f_{{i-j},k}\times \dbinom{n-1-(i-j)}{j}\times 2^{\frac{j(j-1)}{2}}\times (2^k-1)^j \]CF1476F Lanterns
典题，覆盖问题可以将状态设计成 \(f_i\) 表示前 \(i\) 盏灯能覆盖的最长前缀。
转移分三类：
- 前面不能覆盖到 \(i\)，直接不管 \(i\)，\(f_i=f_{i-1}\)。
- 前面能覆盖到 \(i\)，\(f_i=\max(f_{i-1},i+p_i)\)。
- 将 \(i\) 向左，找到一个 \(f_j\ge i-p_i\) 最小的 \(j\)，然后 \(j+1\sim i-1\) 全部向右，\(f_i=\max\{k+p_k\}\)。
不知道为什么想这么久，明明这么简单。
[ARC154C] Roller
有 ARC182B 作为基础这题很容易想到做法，将相同的合并成一块，只需判断是否存在一个断点使得 \(a\) 是 \(b\) 的子序列。
但是还需要空余的位置，可以是 \(a\) 中 \(b\) 没出现的，可以是 \(b\) 中相邻的，也可以是 \(a\) 中相邻的。若没有空余位置则必须 \(a,b\) 完全相等。
细节一直写挂，数组还开小了。
P3214 [HNOI2011] 卡农
想不出来。
设 \(f_i\) 表示选了 \(i\) 个子集且满足条件的方案。考虑容斥，为了满足和前面的 \(i-1\) 个子集加在一起全是偶数，前面每种选法都唯一确定一种子集，方案数为 \(A_{2^n-1}^{i-1}\)。
再减去 \(i\) 为空的情况，方案数为 \(f_{i-1}\)（去掉 \(i\) 之后能满足条件）。
再减去 \(i\) 和前面相同的方案。去掉 \(i\) 和 \(j\) 后也能满足条件，\(j\) 有 \(i-1\) 种取值，子集 \(i\) 有 \(2^n-1-(i-2)\) 种取法，方案数为 \(f_{i-2}\times (i-1)\times (2^n+1-i)\)。
最后输出 \(\dfrac{f_m}{m!}\)。
P3577 [POI2014] TUR-Tourism
在无向图搜索树上 DP，没见过。
由题得树的深度不超过 \(10\)，这启发我们用树上状压 DP（还是没见过）。
一个重要的性质：无向图 DFS 树上的非树边一定是回边，不存在横叉边。所以我们可以状压父亲的状态。
DP 过程较为复杂，不写。
P6381 『MdOI R2』Odyssey
通过质因数分解我们很容易判断是否能构成完美数对，但是信息在边上我们很难直接 DP。
但我们发现如果用哈希去表示每一条边，那么能与它配对的边的哈希值也是确定的。这启发我们设 \(f_{i,h_i}\) 表示以 \(i\) 为终点，最后一条边哈希值是 \(h_i\) 的答案，时间复杂度 \(\mathcal{O}(n\log n\times 11)\)。
P8860 动态图连通性
很牛逼。
首先肯定要离线，然后多次询问的边只有第一次有用。
记边被询问的时间为 \(d_i\)，没询问的视作 \(d_i=Q+1\)。将 \(d_i\) 作为边的边权，那么就是要找一条路径，使得将路径上的边的权值从大到小排序，字典序最小。
类似 「The classic problem」一样用主席树维护最短路。
CF464D World of Darkraft
需要注意到 \(k\) 种装备地位相同，所以只需计算一种装备最后乘 \(k\)。设 \(f_{i,j}\) 表示还剩 \(i\) 个怪兽，装备等级为 \(j\) 的期望。转移不表。
[ABC370F] Cake Division
不会倍增的菜鸟了属于是。
二分答案，记 \(f_i\) 为从 \(i\) 开始的一个连续段的结尾 \(+1\)（即下一个连续段的开头），那么就是从 \(i\) 开始跳 \(k\) 次 \(f\) 看终点是否满足条件。这显然倍增。
P7603 [THUPC2021] 鬼街
减半警报器。
一次灵异事件的发生可以暴力给所有质因子 \(+y\)，因为质因子个数很少。问题是什么时候统计答案。
对于一个 \((x,y)\) 的监控，记加入时其质因子已经发生了 \(s\) 次灵异事件，响警报的条件是 \(\sum\limits _{p}cnt_p\ge y+s\)。转化成 \(\sum \Delta cnt_p\ge y\)。那肯定至少有一个 \(p\) 满足 \(\Delta cnt_p\ge \lceil\frac{y}{d_x} \rceil\)，我们将其设为阈值，当一个房间里有监控达到阈值时我们就拿出来 check 一下，这可以用优先队列实现。
如果 check 失败，我们让阈值变成 \(\lceil\frac{y-\sum\Delta cnt_p}{d_x} \rceil\)，然后重新加入优先队列。不难发现， 每次阈值至少减少 \(\dfrac{1}{d_x}\)，所以时间复杂度 \(\mathcal{O}(m\times d_V\log V\log n)\)。
[ARC171C] Swap on Tree
每棵子树最多 \(siz+1\) 种取值，且新的数是什么不重要。设 \(f_{x,t,0/1}\) 表示以 \(x\) 为根的子树，与 \(x\) 相连的边断了几条边，和父亲的边是否断了的方案数。
\(f'_{x,t,0}\leftarrow f_{x,t-1,0}\times f_{y,s,1}\times t+f_{x,t,0}\times f_{y,s,0}\)
\(f'_{x,t,1}\leftarrow f_{x,t-1,1}\times f_{y,s,1}\times t+f_{x,t,1}\times f_{y,s,0}\)
初始化 \(f_{x,0,0}=1\)，\(f_{x,1,1}=[x\ne 1]\)。
P6383 『MdOI R2』Resurrection
其实就是联通块的根之间连边。
容易想到设 \(f_{x,i}\) 表示 \(x\) 上面还有 \(i\) 个点可供选择的方案数，但是不会做转移。
因为 \(x\) 的选择会使得 \(i\) 的限制发生变化，而且 \(x\) 与儿子的谁先与父亲切断对转移也有影响。平常的树形 DP 依赖于儿子的状态，而这里对父亲也提出要求。
考虑分析图的性质，然后就发现儿子连的边一定不会与父亲连的边交叉，要不连父亲，要不连父亲连的点的上面。分析出这点，然后就可以枚举父亲连的点进行转移了。
P6009 [USACO20JAN] Non-Decreasing Subsequences P
静态区间查询，考虑猫树分治。
如何合并两个前后缀信息，记 \(g_{i,j}\) 表示 \([i,mid]\) 里以 \(j\) 结尾的不下降子序列数量。将值域放到状态里即可合并。
P9716 [EC Final 2022] Coloring
先把环找出来，然后对于环上的每个点，以它为根对子树进行 DP。
显然每次覆盖不会完全覆盖上一次，那么最后的覆盖次数肯定是从子树的上到下减小的，所以设 \(f_{x,i}\) 表示 \(x\) 覆盖了 \(i\) 次的答案，转移不表。
若 \(s\) 不在环上，则答案为 \(\max(f_{s,1},f_{s,2})\)。
否则，我们对这个环进行考虑，手玩一下发现，最后以 \(s\) 为开头按照边的方向形成的节点序列的操作次数单调不升，且极差 \(\leq 2\)，所以枚举最小值然后 DP。
有一些细节。
GJOI 9.11 T2
对于 \(01\) 串 \(x\)，一次操作指将其一个子串反转（\(0\rightarrow 1\)，\(1\rightarrow 0\)），定义 \(x\) 的权值为使得 \(x\) 满足任意一对相邻字符均不相同。
\(q\) 个询问，每次询问子串 \(s[l:r]\) 的所有非空子序列之和。
\(n,q\leq 5\times 10^6\)。
记 \(w=\sum\limits_{i=1}^{n-1}[s_i\ne s_{i+1}]\)，则 \(s\) 的权值为 \(\left\lceil\dfrac{w}{2}\right\rceil\)。这样可以设计出 \(\mathcal{O}(n^2q)\) 的DP。使用猫树优化可以做到 \(\mathcal{O}(n\log n+q)\)。
但是题目要求线性，上述的 DP 没有优化前途。
考虑将 \(\lceil\frac{w}{2}\rceil\) 拆成 \(\frac{1}{2}(w+[2\not\mid w])\)，只需计算所有子序列 \(w\) 的和还有 \(w\) 为奇数的子序列个数。
-
先计算前者，对于 \(l\le i<j\le r\) 且 \(s_i=s_j\) 的字符，只有当它们同时出现在某个子序列且相邻才有贡献，则总贡献为
\[\sum\limits_{l\le i<j\le r,s_i=s_j}2^{r-l+i-j}\\=2^{r-l}\left(\sum\limits_{1\le i<j\leq r,s_i=s_j}2^{i-j}-\sum\limits_{1\le i<l,l\le j\le r,s_i=s_j}2^{i-j}-\sum\limits_{1\le i<j<l,s_i=s_j}{2^{i-j}} \right) \] -
再计算后者，有结论一个子序列 \(w\) 的奇偶性与等于子序列长度和 \([s_{st}=s_{ed}]\) 之和的奇偶性。
对于 \(st\ge ed-1\)，特判。
对于 \(st< ed-1\)，若 \(st,ed\) 固定，则长度为奇数的子序列和偶数相等，为 \(2^{ed-st-2}\)。
则总贡献为
\(\sum\limits_{l\le i<r}[s_i=s_{i+1}]+\sum\limits_{l\le i<j-1\le r}2^{j-i-2}\\=\sum\limits_{l\le i<r}[s_i=s_{i+1}]+\sum\limits_{2\le i\le r-l}2^{i-2}(r-l-i+1)\)
时间复杂度 \(\mathcal{O}(n+q)\)。
GJOI 9.10 T2
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=5e6+10,MOD=1e9+7;
int n,Q,opt,al,bl,ar,br,l,r;
LL res;
int pw[N],ipw[N],pre[N],s1[N],s2[N];
int A[N][2][2],B[N];
char s[N];
void addm(int &x,int y){(x+=y)%=MOD;if(x<0)x+=MOD;}
int ksm(int x,int y)
{
int res=1;
while(y)
{
if(y&1) res=1LL*res*x%MOD;
x=1LL*x*x%MOD;
y>>=1;
}
return res;
}
void init()
{
pw[0]=ipw[0]=1;
for(int i=1; i<=n; i++)
pw[i]=1LL*pw[i-1]*2%MOD;
ipw[n]=ksm(pw[n],MOD-2);
for(int i=n-1; i>=1; i--)
ipw[i]=1LL*ipw[i+1]*2%MOD;
for(int i=1; i<=n; i++)
{
if(i>1) pre[i]=pre[i-1]+(s[i-1]==s[i]);
s1[i]=(s1[i-1]+pw[i-1])%MOD;
s2[i]=(s2[i-1]+1LL*pw[i-1]*(n-i)%MOD)%MOD;
bool cur=(s[i]=='1');
B[i]=B[i-1];
addm(B[i],1LL*ipw[i]*A[i-1][cur][0]%MOD);
A[i][0][0]=A[i-1][0][0];
A[i][0][1]=A[i-1][0][1];
A[i][1][0]=A[i-1][1][0];
A[i][1][1]=A[i-1][1][1];
addm(A[i][cur][0],pw[i]);
addm(A[i][cur][1],ipw[i]);
}
}
int main()
{
freopen("alternate.in","r",stdin);
freopen("alternate.out","w",stdout);
scanf("%d%d%d%s",&n,&Q,&opt,s+1);
if(opt) scanf("%d%d%d%d%d%d",&al,&bl,&ar,&br,&l,&r);
init();
for(int i=1; i<=Q; i++)
{
if(opt)
{
int tf=(1LL*al*l%n+bl)%n+1,tg=(1LL*ar*r%n+br)%n+1;
if(tf>tg) swap(tf,tg);
l=tf; r=tg;
}
else scanf("%d%d",&l,&r);
int ans=0;
addm(ans,B[r]); addm(ans,-B[l-1]);
addm(ans,-1LL*(A[r][0][1]-A[l-1][0][1]+MOD)%MOD*A[l-1][0][0]%MOD);
addm(ans,-1LL*(A[r][1][1]-A[l-1][1][1]+MOD)%MOD*A[l-1][1][0]%MOD);
ans=1LL*ans*pw[r-l]%MOD;
addm(ans,pre[r]-pre[l]);
addm(ans,s2[r-l-1]); addm(ans,-1LL*s1[r-l-1]*(n-r+l)%MOD);
ans=1LL*ans*ipw[1]%MOD;
if(opt) res^=(LL)(ans+i*23);
else printf("%d\n",ans);
}
if(opt) printf("%lld\n",res);
return 0;
}