自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:40:08，当前版本为作者最后更新于2022-10-03 17:11:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

可以先考虑计算从 $(A,B,C)$ 走到 $(0,0,0)$ 而不撞墙的概率，有递推关系：

$$f_{A,B,C}=\frac 13 (f_{A-1,B,C}+f_{A,B-1,C}+f_{A,B,C-1}) $$

建立生成函数，设 $f_{A,B,C}=[x^Ay^Bz^C]F$，则有

$$F= \frac 13(x+y+z)F+1$$

多出来的这个 +1 就是因为要补上 $f_{0,0,0}=1$ 这一项。

$$F = \frac{1}{1-(x+y+z)/3}=\sum_{i=0}^\infty \frac{1}{3^i}(x+y+z)^i $$

提取系数即得

$$f_{A,B,C}= \frac{1}{3^{A+B+C}}\binom{A+B+C}{A,B,C} $$

那么计算从 $(A,B,C)$ 走到 $(i,j,k)$ 而不撞墙概率就容易计算了。其递推式与 $f$ 很像，再稍加分析就可以发现所求是 $f_{A-i,B-j,C-k}$。

现在只需要枚举墙边的位置，根据走到那撞到墙的概率，就可以将答案表示为：

$$g(A,B,C)+g(A,C,B)+g(B,C,A)$$ $$g(d_1,d_2,d_3)=\frac 13\sum_{i=0}^{d_1}\sum_{j=0}^{d_2} \binom{i+j+d_3}{i,j,d_3}\frac{(d_1+d_2-i-j)^k}{3^{i+j+d_3}} $$

你会发现有些位置可能被重复计算了，但没关系。被计了两次的位置，都是有两个方向面对墙的位置。

这里就说 $g(A,B,C)$ 的计算方法，剩下的两部分也是一样的。可以发现 $i+j$ 在和式中频繁出现，考虑换元枚举 $t=i+j$：

$$3g(A,B,C)=\frac{1}{3^C}\sum_{t=0}^{A+B} \frac{(A+B-t)^k}{3^t}\sum_{j=t-A}^B \binom{t+C}{t-j,j,C} $$

后面那个和式可以单独计算，先化简为

$$\binom{t+C}{C} \sum_{j=t-A}^B \binom{t}{j}$$

这种超几何式显然可以整式递推计算，利用二项式系数的递推公式：

$$D_n=\sum_{i=n-A}^B \binom ni = \sum_{i=n-A}^B \binom{n-1}{i}+\binom{n-1}{i-1} $$$$D_n=2D_{n-1} -\binom{n-1}{A}- \binom{n-1}{B}$$

可以在线性时间内递推计算，最后用线性筛来求 $t^k$ 即可。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 10000003
#define ll long long
#define p 998244353
using namespace std;

inline int power(int a,int t){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

const int inv3 = 332748118;
int fac[N],ifac[N],pw[N],pr[N>>3],inv[N];
int cnt;

void init(int n,int k){
    inv[1] = pw[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for(int i=2;i<=n;++i) fac[i] = (ll)fac[i-1]*i%p;
    ifac[n] = power(fac[n],p-2);
    for(int i=n-1;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
    for(int i=2;i<=n;++i){
        inv[i] = (ll)fac[i-1]*ifac[i]%p;
        if(!pw[i]){
            pr[++cnt] = i;
            pw[i] = power(i,k);
        }
        for(int j=1;j<=cnt&&i*pr[j]<=n;++j){
            pw[i*pr[j]] = (ll)pw[i]*pw[pr[j]]%p;
            if(i%pr[j]==0) break;
        }
    }
}

int g(int A,int B,int C,int k){
    if(A>B) swap(A,B);
    ll res = 0;
    int bc = 1,f = 1,ifa = ifac[A],ifb = ifac[B],ipw3 = 1;
    for(int i=0;i<=A+B;++i){
        res += (ll)pw[A+B-i]*f%p*ipw3%p*bc%p;
        ipw3 = ipw3*332748118ll%p;
        bc = (ll)bc*(i+C+1)%p*inv[i+1]%p;
        if(i<A) f = (f<<1)>=p?(f<<1)-p:f<<1;
        else if(i<B) f = ((f<<1)-(ll)fac[i]*ifa%p*ifac[i-A])%p;
        else f = ((f<<1)-((ll)ifa*ifac[i-A]+(ll)ifb*ifac[i-B])%p*fac[i])%p;
    }
    return res%p*power(3,p-C-1)%p;
}

int A,B,C,k;

int main(){
    scanf("%d%d%d%d",&A,&B,&C,&k);
    init(A+B+C-min(min(A,B),C),k);
    int ans = (ll)((g(A,B,C,k)+g(A,C,B,k))%p+g(B,C,A,k))*inv3%p;
    printf("%d",(ans+p)%p);
    return 0;  
}