麻中麻。

比赛过程

开幕还是巨大多读题，读了 K 感觉不是简单题，看了看 J 感觉会做，开写！然后写完了忘记了一个 corner case，总计在一个题上耗了近一个半点……期间 bzy 过了 A，冯佬高强度写 G。

然后我看到 bzy 说 C 是个数轴游走题，就去想。非常生草的事是我一开始理解是错的（我以为它要求的是整个过程中的最大值期望，其实题目只要求最终状态最大值期望），推了半天反射法……最后意识到这个问题，整出来一个二维平面游走，但看着尼玛也不像能做的样子啊（最终可以走进去的那个区域形状很诡异）。

bzy 写 D 莫名其妙 WA，冯佬写 G 莫名其妙 T。最后 bzy 弃坑，冯佬随后发现 G 理解有问题，改改就过了。接下来冯佬尝试去调 bzy 的程序，发现有三个诡异的 corner cases，不知道怎么改……我当时实在想不动了，就在 bzy 的代码基础上加了特判这三个情况，结果竟然过了……

补题：C

题意

数轴上有三个人，初始座标分别为\(x_1,x_2,x_3\)。

现在开始进行\(k\)秒随机游走，每秒钟从三个人中均匀随机的选择一个，然后这个人的座标会有\(p\)的概率加一，有\(1-p\)的概率减一。

请问，最终这三个人座标最大者减去最小者的期望是多少？答案对\(998244353\)取模后输出。

\(-10^5\le x_1,x_2,x_3\le 10^5,1\le k\le 2\times 10^5\)

解析

绝绝子，真的绝绝子。

只需要注意到： \[ \max(a,b,c)-\min(a,b,c)=\frac 1 2(|a-b|+|a-c|+|b-c|) \] （这个式子不难证明，因为最大到最小的段上的每一块都被覆盖了恰好两次）

然后我们考虑单独挑出来一个\(a-b\)，考虑它每秒钟会怎么变化：

  • 不变：这种情况就是选择了\(c\)来变化，概率为\(\frac 1 3\)。
  • 加一：\(a\)被选择且加一，或者是\(b\)被选择且减一，概率为\(\frac{p}{3}+\frac{1-p}{3}=\frac 1 3\)。
  • 减一：\(a\)被选择且减一，或者是\(b\)被选择且加一，概率为\(\frac{1-p}{3}+\frac p 3=\frac 1 3\)。

这三种情况发生的概率都恰好是\(\frac 1 3\)，所以\(p\)其实屁用没有。要去描述这个\(a-b\)的变化的话，我们考虑构造多项式\(F(x)=\frac 1 3(1+x+x^2)\)，然后\(F^k(x)\)就能描述\(k\)秒中的变化。至于怎么求这个，拿出多项式全家桶里的多项式幂就行了。

代码

直接用了冯佬的多项式全家桶，，，

#include <bits/stdc++.h>
namespace Poly{
using namespace std;
#define For(i,a,b) for(int i=a;i<b;i++)
#define clr(x) memset(x,0,sizeof x)
#define per(i,a,b) for(int i=b,i##_end=a;i>=i##_end;--i)
  const int N=1e6+11,mo=998244353,G=3;
  int Pow(int a,int b){
    int r=1;
    for(;b;b>>=1,a=1ll*a*a%mo)
      if(b&1)r=1ll*r*a%mo;
    return r;
  }
  void dft(int *a,int n){
    int i,j,l;
    for(i=j=0;i<n;++i){
      if(i>j)swap(a[i],a[j]);
      for(l=n>>1;(j^=l)<l;l>>=1);
    }
    for(l=1;l<n;l<<=1){
      int wn=Pow(G,(mo-1)/l/2);
      for(i=0;i<n;i+=l<<1){
        int w=1;
        for(j=0;j<l;++j,w=1ll*w*wn%mo){
          int x=a[i+j],y=1ll*w*a[i+j+l]%mo;
          a[i+j]=(x+y)>=mo?x+y-mo:x+y;;
          a[i+j+l]=x-y<0?x-y+mo:x-y;;
        }
      }
    }
  }
  void idft(int *a,int n){
    dft(a,n);
    reverse(a+1,a+n);
    int m=Pow(n,mo-2);
    For(i,0,n)a[i]=1ll*a[i]*m%mo;
  }
  void mul(int *a,int A,int *b,int B,int *c){
    int m=1;
    while(m<A+B)m<<=1;
    int x[m],y[m];
    clr(x),clr(y);
    For(i,0,A)x[i]=a[i];
    For(i,0,B)y[i]=b[i];
    dft(x,m),dft(y,m);
    For(i,0,m)c[i]=1ll*x[i]*y[i]%mo;
    idft(c,m);
  }
  void inv(int *a,int *b,int n){
    if(n==1){
      b[0]=Pow(a[0],mo-2);
      return;
    }
    int m=n+1>>1;
    inv(a,b,m);
    For(i,m,n)b[i]=0;
    int c[4*n];clr(c);
    mul(b,m,b,m,c);
    mul(a,n,c,n,c);
    For(i,0,n)b[i]=(2ll*b[i]-c[i]+mo)%mo;
  }
  void ln(int *a,int *b,int n){
    int c[n*4],d[n*4];clr(c),clr(d);
    For(i,1,n)c[i-1]=1ll*i*a[i]%mo;
    inv(a,d,n);
    mul(c,n,d,n,b);
    int inv[n];
    inv[1]=1;
    For(i,2,n)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
    per(i,0,n-1)b[i+1]=1ll*b[i]*inv[i+1]%mo;
    b[0]=0;
    For(i,n,2*n)b[i]=0;
  }
  void exp(int *a,int *b,int n){
    if(n==1){
      assert(a[0]==0);
      b[0]=1;
      return;
    }
    int m=n+1>>1;
    exp(a,b,m);
    For(i,m,n)b[i]=0;
    int c[n*6],d[n*6];clr(c),clr(d);
    ln(b,d,n);
    For(i,0,n)c[i]=(a[i]-d[i]+mo)%mo;
    mul(c,n,b,m,c);
    For(i,0,n)b[i]=(b[i]+c[i])%mo;
  }
  void fpow(int *a,int *b,int n,int t){
    int c[n*4],d[n*4];clr(c),clr(d);
    ln(a,c,n);
    For(i,0,n)c[i]=1ll*c[i]*t%mo;
    exp(c,b,n);
  }
}

using Poly::N;
using Poly::mo;
using Poly::Pow;

int B[N], BB[N];
int x[3];
int main() {
  int k;
  std::cin >> x[0] >> x[1] >> x[2] >> k;
  B[0] = B[1] = B[2] = 1;
  Poly::fpow(B, BB, k << 1 | 1, k); 
  const int inv_3k = Pow(Pow(3, mo - 2), k);
  for(int i = 0; i <= 2 * k; i ++) {
    BB[i] = 1LL * BB[i] * inv_3k % mo;
  }
  int ans = 0;
  for(int a = 0; a < 3; a ++) {
    for(int b = a + 1; b < 3; b ++) {
      const int diff = x[a] - x[b];
      for(int d = -k; d <= k; d ++) {
        const int th = std::abs(d + diff);
        ans = (1ll * th * BB[d + k] + ans) % mo;
      }
    }
  }
  ans = 1ll * ans * Pow(2, mo - 2) % mo;
  std::cout << ans << "\n";
  return 0;
}