B
你可以进行以下的操作:选择一个点染白色;此后每次染有白色点相邻的,且 \(a_i\) 最小的点。
\(q\) 次询问每次给出 \(p,k\),问有多少种选择点的方案,使得 \(p\) 是第 \(k\) 个选到的。
\(a_i\) 是排列。\(n,q\le 1e5\)。
设 \(l=p-k+1,r=p+k-1\),若 \([l,p-1]\) 能取到且 \(a_p<a_{l-1}\),那么算上 \([l,p-1]\) 的答案。
若 \([p+1,r]\) 能取到且 \(a_p<a_{r+1}\),算上 \([p+1,r]\) 的答案。
考虑一个区间能否取到,考虑取出最大值的位置 \(x\)。
若 \(a_x<a_{l-1}\) 那么 \(x\) 左边的位置都可以作为开头,\(a_x<a_{r+1}\) 那么右边的也都能取到。
现在计算 \(x\) 能否取到,取左边右边分别的最大值,
那么最后的形式一定是左右边一个顶到最大值处,另一边到边界,只需要判断是否出边界即可。
C
我们称两个字符串 \(s\) 和 \(t\) 是等价的,如果对于任意长度为 \(2\) 的字符串在 \(s,t\) 中出现次数相同。
询问一个字符串其有多少个字符串与其等价。字符集大小为 \(3\)。
这是一个欧拉路径计数。
由于 best 定理是计算欧拉回路的,若算的是 \(s\to t\) 的欧拉路径,那么加一条 \(t\to s\) 的边。
由于最后算的是循环同构的回路方案数,考虑旋转使得加的那条边在最后,删掉即可。
即本质不同的欧拉回路个数与欧拉路径的个数是一一对应的关系。
如果算的是欧拉回路个数,要乘上 \(n-1\),因为从环路的任意位置开始都可以。
最后考虑所有边是等价的情况,那么乘上 \(\prod_{i,j}\frac{1}{E_{i,j}!}\)。