ABC240G Teleporting Takahashi

Description

求在三维空间内走步抵达的方案数。每步只能沿一个维度的一个方向走单位长度。

。

Sol

容易发现可以直接取绝对值而不影响答案。

时方案数即为多重集排列数。

时显然无解。

考虑时我们如何消耗掉多出的步数，显然是任选一个方向走一步再退回来。

形式化地，设，那么每一维都需要枚举它要向反方向走多少步，则得到 ~~真是吓人呢~~

拆一下后面部分拆成阶乘：提出与无关的项然后开始重组：观察后面的部分，可以发现就是一个下指标卷积，最终得到直接计算即可。时间复杂度线性。

Code

#include<bits/stdc++.h>
using std::vector;
#define int long long
typedef vector<int> vi;
typedef long long ll;
const int Mod=998244353;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

signed main(){
    int n=read(),x=abs(read()),y=abs(read()),z=abs(read());
    if(n<x+y+z||(n-x-y-z)%2!=0)return puts("0"),0;
    int w=(n-x-y-z)/2;
    auto ksm=[](int x,int y){
        int ans=1;
        for(;y;y>>=1,x=x*x%Mod)if(y&1)ans=ans*x%Mod;
        return ans;
    };
    vi fac(n+1),inv(n+1);
    fac[0]=fac[1]=1;
    for(int i=2;i<=n;++i)fac[i]=fac[i-1]*i%Mod;
    inv[n]=ksm(fac[n],Mod-2);
    for(int i=n-1;~i;--i)inv[i]=inv[i+1]*(i+1)%Mod;
    auto C=[fac,inv](int x,int y){return x>=0&&y>=0&&x>=y?fac[x]*inv[y]%Mod*inv[x-y]%Mod:0;};
    int ans=0;
    for(int i=0;i<=w;++i){
        int W=fac[n-x-2*i]*inv[z+w-i]%Mod*inv[w-i+y]%Mod*C(2*w-2*i+y+z,w-i)%Mod;
        (ans+=W*C(n,x+2*i)%Mod*C(x+2*i,i)%Mod)%=Mod;
    }
    printf("%lld\n",ans);
    return 0;
}