https://atcoder.jp/contests/arc111
F - Do you like query problems?
一个查询问题
整数序列,a[n],初始全0,
ans = 0
q个询问，其中$v_i\in[0,M-1]$
- 1类: $\mathrm{for} j = l_i\cdots r_i, a_j=\min(a_j,v_i)$, 区间change min
- 2类: $\mathrm{for} j = l_i\cdots r_i, a_j=\max(a_j,v_i)$, 区间change max
- 3类:
ans+=(\sum a[l_i..r_i])
最后输出ans
Maroon 觉得这个 问题太简单了
对于 给定$N,M,Q$,那么 有 $(\frac{N(N+1)}{2}(M+M+1))^Q$种合法的输入，求所有输出的值的和 mod 998244353
输入 $N,M,Q \in[1,200000]$
4s
1024mb
我的思路
啊？？？？
题意上的 合法输入，左边就是选$[l,r]$, 右边就是min的选v,max的选v,输出的1
这个 询问的问题真的可做吗？感觉上 统计所有方案可以从概率频次的角度去计算，但是原来的单独问题真的能做吗？
比如 改成了
1
2
3
4
5
6
7
| 大小大小大小大小大小大小大小大
然后对 区间 做多次 min
[ ]
[ ]
[ ]
但是过程保持 大于这里面的小，又可以下降大，这样的话是非常离散的多点状态更新啊
|
感觉做不了一点
回到本题，感觉就每个点单独考虑贡献就好了
对于 a[i] 表示$[x^v]f_{i,t}(x)$表示下标$i$经过$t$轮后值为$v$的操作方案数,初始状态有$[x^v]f_{i,0}(x) = [v=0]$
那么 就可以变成 当前状态+=上个状态 * 区间选择 * (操作类型=1)* 值选择
令$c_i=i(n+1-i)$表示一次选区间时$i$被选中的方案数，那么不被选中的为$\frac{n(n+1)}{2} - c_i$
$\mathrm{ans}=\sum_{i=1}^{N}c_i\sum_{v=0}^{M-1}v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$, 表示$t+1$次的时候覆盖了位置$i$调用输出$v$了，而注意后续任何操作该次贡献都翻倍，所以有后面的$A^{Q-(t+1)}$
这是一个 明显超时的方案，接下来就看能不能做效率优化了
令$A=\frac{N(N+1)}{2}(M+M+1) \neq 0$表示单次所有操作方案数
考虑$[x^v]f_{i,t}(x)$的来源
$[x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2}\cdot 1)$ 表示一个位置不被操作的方案数
$[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (M-v)$ 表示 使用$\min(v_1),v_1 \ge v$的方案数，也就是min操作后不影响
$\sum_{v_1 > v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$ 表示 使用$\min(v),v_1 > v$的方案数，min操作后改变
$[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (v+1)$ 表示 使用$\max(v_1),v_1 \le v$的方案数，也就是操作后不影响
$\sum_{v_1 < v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$ 表示 使用$\max(v),v_1 < v$的方案数，操作后改变
合并一下
$[x^v]f_{i,t}(x) = [x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2}\cdot 1)+[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (M+1) + \sum_{v_1 \neq v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$
$= [x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2} +(c_i) \cdot (M)) + \sum_{v_1 = 0}^{M-1} [x^{v_1}]f_{i,t-1}(x) \cdot (c_i)$ , 从第二部分提取1个到第三部分
而右侧 是和v无关的，只和$t$相关，因为它是位置$i$的所有可能值的方案数，所以和$i$也是无关的，但$c_i$是有关$i$的
而左侧也和$v$无关，表现的是不同$v$之间没有直接的影响
$= [x^v]f_{i,t-1}(x) \cdot (\frac{n(n+1)}{2}(2M+1) - c_iM) + A^{t-1} \cdot c_i$
令$d_i=\frac{n(n+1)}{2}(2M+1) - c_iM$
$[x^v]f_{i,t}(x)= [x^v]f_{i,t-1}(x) \cdot d_i+ A^{t-1} \cdot c_i$
讨论$d_i = 0,A,$和其它（这里我的思考过程是3步骤，不过回过头看只用看是否是$A$
若$d_i=0$, $[x^v]f_{i,t}(x)= A^{t-1} \cdot c_i$
否则$d_i\neq 0$
$\displaystyle \frac{[x^v]f_{i,t}(x)}{d_i^t}= \frac{[x^v]f_{i,t-1}(x)}{(d_i)^{t-1}} + \frac{c_i}{d_i}(\frac{A}{d_i})^{t-1}$
$\displaystyle \frac{[x^v]f_{i,t}(x)}{d_i^t}= \frac{[x^v]f_{i,0}(x)}{(d_i)^{0}} + \frac{c_i}{d_i}\sum_{j=0}^{t-1} (\frac{A}{d_i})^{j}$
令$\displaystyle g(x,p)=\sum_{i=0}^{p-1} x^i$,有$x=1$时$g(x,p)=p$,当$x\neq 1$时$\displaystyle g(x,p)=\frac{x^p-1}{x-1}$
$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([x^v]f_{i,0}(x) + \frac{c_i}{d_i} g(\frac{A}{d_i},t)\right)$
$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([v=0] + \frac{c_i}{d_i} g(\frac{A}{d_i},t)\right)$,未操作时都是0
如果$d_i = A$则$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([v=0] + \frac{c_i}{d_i} g(1,t)\right)= d_i^t\left([v=0] + \frac{c_i}{d_i} t\right)$,未操作时都是0
否则$d_i\neq 0,d_i\neq A$, 待定系数法
$[x^v]f_{i,t}(x) + k_iA^t = d_i([x^v]f_{i,t-1}(x) + k_iA^{t-1})$
$d_ik_iA^{t-1}-k_iA^t=A^{t-1}c_i$
$d_ik_i-k_iA=c_i$, 因为$A\neq 0$
$\displaystyle k_i=\frac{c_i}{d_i-A}$ 这里分母非0
$[x^v]f_{i,t}(x) + k_iA^t = (d_i)^t([x^v]f_{i,0}(x) + k_iA^0)$
$[x^v]f_{i,t}(x) = (d_i)^t([x^v]f_{i,0}(x) + k_i)- k_iA^t$
$= (d_i)^t([v=0] + k_i)- k_iA^t$，未操作时都是0, 而这种情况对于$d_i=0$ 也成立，一定$0\neq A$,
所以 $[x^v]f_{i,t}(x) = \frac{c_i}{d_i-A} ((d_i)^t-A^t), v\neq 0$
$\displaystyle \mathrm{ans}=\sum_{i=1}^{N}c_i\sum_{v=0}^{M-1}v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$,带入 上面时分类讨论$d_i$与$A$是否相等
令$\mathrm{ans}i=c_i\sum{v=0}^{M-1} v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x)) A^{Q-(t+1)}= c_i\sum_{v=1}^{M-1} v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$ 注意到$v=0$时不会贡献
则 $\displaystyle \mathrm{ans}=\sum_{i=1}^{N} ans_i$
对于 $d_i=A$
$\displaystyle \mathrm{ans}i=c_i\sum{v=1}^{M-1}v\sum_{t=0}^{Q-1} d_i^t\left([v=0] + \frac{c_i}{d_i} t \right)A^{Q-(t+1)}$
$\displaystyle =c_i\sum_{v=1}^{M-1}v\sum_{t=0}^{Q-1} A^t\left(\frac{c_i}{A} t\right)A^{Q-(t+1)}$
$\displaystyle =c_i^2A^{Q-2}\frac{M(M-1)}{2} \sum_{t=1}^{Q-1} t$
$\displaystyle =c_i^2A^{Q-2}\frac{M(M-1)}{2} \frac{Q(Q-1)}{2}$
若$d_i\neq A$
$\displaystyle \mathrm{ans}i=c_i\sum{v=0}^{M-1}v\sum_{t=0}^{Q-1} \left(\frac{c_i}{d_i-A} ((d_i)^t-A^t)\right)A^{Q-(t+1)}$
$\displaystyle =\frac{c_i^2}{d_i-A} A^{Q-1} \frac{M(M-1)}{2} \left(\sum_{t=0}^{Q-1} \left(\frac{d_i}{A}\right)^t-\sum_{t=0}^{Q-1} 1\right)$
$\displaystyle = \frac{c_i^2}{d_i-A} A^{Q-1}\frac{M(M-1)}{2} \left(g(\frac{d_i}{A},Q)-Q\right)$
整理一下,$N,M,Q$输入
$A=\frac{N(N+1)}{2}(M+M+1)\neq 0$
令$\displaystyle g(x,p)=\sum_{i=0}^{p-1} x^i$,有$x=1$时$g(x,p)=p$,当$x\neq 1$时$\displaystyle g(x,p)=\frac{x^p-1}{x-1}$
$c_i=i(n+1-i)$
$d_i=\frac{n(n+1)}{2}(2M+1) - c_iM$
$\displaystyle \mathrm{ans}=\sum_{i=1}^{N} ans_i$
若$d_i = A$, 则 $\displaystyle \mathrm{ans}_i=c_i^2A^{Q-2}\frac{M(M-1)}{2} \frac{Q(Q-1)}{2}$
若$d_i \neq A$,则$\displaystyle \mathrm{ans}_i = \frac{c_i^2}{d_i-A} A^{Q-1}\frac{M(M-1)}{2} \left(g(\frac{d_i}{A},Q)-Q\right)$
似乎就过了?