Atcoder arc111

發表於 更新於 分類於 ， Disqus： 文章字數： 2.1k 所需閱讀時間 ≈ 7 分鐘
F(生成函数)

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)$

似乎就过了?

代码

https://atcoder.jp/contests/arc111/submissions/50503511

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
#include <atcoder/modint>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
typedef long long ll;
ll read(){ll r;scanf("%lld",&r);return r;}
// sum x^0+x^1+...+x^{pwr-1}
mint g(mint x,int pwr){ return (x==1)?pwr:((x.pow(pwr)-1)/(x-1)); }
int main(){
  ll N=read();
  ll M=read();
  ll Q=read();
  mint ans=0;
  mint A=mint(N*(N+1)/2)*(2*M+1);
  mint AQ1 = A.pow(Q-1); // A^{Q-1}
  for(ll i=1;i<=N;i++) {
    mint c = i*(N+1-i);
    mint d = mint(N*(N+1)/2)*(2*M+1)-c*M;
    assert(d != A);
    ans += c*c/(d-A)*AQ1*(M*(M-1)/2)*(g(d/A,Q)-Q);
  }
  printf("%d\n",ans.val());
  return 0;
}

Ref

https://atcoder.jp/contests/arc111/editorial

总结

E: 稍微转化一下表达式，一个明显的floor_sum形式

F: 看评分是个红3119分的题，但自己虽然搞了很久，但自己搞出来了，

不过加了个assert 发现测试数据中没有 di=A的时候，emmmm

如果要相等 就是 $\frac{n(n+1)}{2}(2M+1) - Mi(n+1-i) \equiv \frac{n(n+1)}{2}(M+M+1) \pmod{998244353}$

$Mi(n+1-i) \equiv 0 \pmod{998244353}$, 哦，显然不会等，那我还瞎推了半天。。。

那这样，上面的过程能减少很多很多