題意：走$N$步從$(0,0,0)$走到$(X,Y,Z)$的不同路徑條數(shù)（每一步不能不走且步長(zhǎng)為1）
不失一般性的我們可以設(shè)$(X,Y,Z>0)$
首先考慮走$(X+Y+2k)$步從$(0,0)$走到$(X,Y)$
枚舉$X$正方向的步數(shù)$(X+i)$，總的走法就是
$$C_{x+y+2k}^k\sum _{i=0}^k{C}_k^i\times C_{x+y+k}^{x+i}=C_{x+y+2k}^k\sum _{i=0}^k{C}_k^{k?i}\times C_{x+y+k}^{x+i}=C_{x+y+2k}^k\times C_{x+y+2k}^{y+k}$$
其中$C_{x+y+2k}^k$枚舉了多走的$k$步的位置，$C_k^i\times C_{x+y+k}^{x+i}$分別枚舉了$X$方向回退的$i$步的位置和$X$方向走的$(X+i)$步位置
其中等式${\sum }_{i=0}^k{C}_k^{k?i}\times C_{x+y+k}^{x+i}=C_{x+y+2k}^{y+k}$是著名的范德蒙恒等式
一般形式為${\sum }_{i=0}^k{C}_m^{k?i}\times C_n^i=C_{m+n}^k$
推導(dǎo)過程如下：

考慮在一堆和為$(m+n)$數(shù)量的物品中選$k$個(gè)的方案數(shù)，考慮前$n$個(gè)中選了$i$個(gè)，后$m$個(gè)中選了$(k?i)$個(gè)的方案，枚舉所有$i$求和就得到了答案。

接下來考慮$Z$方向上的情況，剩余未考慮的步數(shù)為$N?(X+Y+2k)$，這些步數(shù)中朝$Z$負(fù)方向的有$(N?(X+Y+Z+2k))/2$步，其余為正方向
則對(duì)于某個(gè)$k$，方案為
$$C_{x+y+2k}^k\times C_{x+y+2k}^{y+k}\times C_N^{N?(x+y+2k)}\times C_{N?(X+Y+2k)}^{(N?(X+Y+Z+2k))/2}$$
枚舉所有$k$就得到了答案，復(fù)雜度$O(N)$

#include<bits/stdc++.h> #define ll long long using namespace std; const int mod=998244353; ll poww(ll a,ll b) {ll t=1;while(b){if(b&1)t=a*t%mod;a=a*a%mod;b>>=1;}return t; } ll inv(ll x) {return poww(x,mod-2); } ll P1[10000005],P2[10000005]; void init() {P1[0]=1;for(int i=1;i<=10000000;i++)P1[i]=1LL*P1[i-1]*i%mod;P2[10000000]=inv(P1[10000000]);for(int i=9999999;i>=0;i--)P2[i]=1LL*P2[i+1]*(i+1)%mod; } ll C(ll n,ll m) {return 1LL*P1[n]*P2[m]%mod*P2[n-m]%mod; } int main() {init();ll N,X,Y,Z;scanf("%lld%lld%lld%lld",&N,&X,&Y,&Z);X=abs(X);Y=abs(Y);Z=abs(Z);ll left=N-X-Y-Z;if(left<0||(left%2!=0))printf("0");else{ll ans=0;for(int k=0;k<=left/2;k++){ans=(ans+1LL*C(X+Y+2*k,k)*C(X+Y+2*k,Y+k)%mod*C(N,N-(X+Y+2*k))%mod*C(N-(X+Y+2*k),(N-(X+Y+2*k+Z))/2)%mod)%mod;}printf("%lld\n",ans);} return 0; }

總結(jié)

以上是生活随笔為你收集整理的ABC240G Teleporting Takahashi[组合数学]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。