[ABC240G] Teleporting Takahashi
前言
心血来潮闲的蛋疼VP了一场ABC，秒到这道题秒不动之后就去看论文了。
题目
AtCoder
讲解
当时脑抽了，想着想着就突然认为要最后一定要化出一个只有组合数，没有累加的式子。
好吧，我们先看二维情况，令 \(f(k)\) 表示多 \(2k\) 步乱走的方案数。
\[\begin{aligned} f(k)&=\sum_{i=0}^k C_{x+y+2k}^{x+i,i,y+k-i,k-i}\\ &=\sum_{i=0}^k \frac{(x+y+2k)!}{(x+i)!i!(y+k-i)!(k-i)!}化成这样就已经lose了\\ &=\sum_{i=0}^k C_{x+y+2k}^{x+k}\times C_{x+k}^{x+i}\times C_{y+k}^{i}\\ &=C_{x+y+2k}^{x+k}\times \sum_{i=0}^k C_{x+k}^{x+i}\times C_{y+k}^{i}化成这样又lose了\\ &=C_{x+y+2k}^{x+k}\times \sum_{i=0}^k C_{x+k}^{x+i}\times C_{y+k}^{y+k-i}\\ &=C_{x+y+2k}^{x+k}\times C_{x+y+2k}^{x+y+k}\\ \end{aligned} \]然后其实就做完了，因为第三维可以直接插进去，时间复杂度 \(O(n)\)。
刚刚在U群里面看到有大佬说最后两行是范德蒙德卷积，其可以用组合意义轻松证明！然而我看题解的时候直接意会的
代码
实现简单。
//12252024832524
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 10000005;
const int MOD = 998244353;
int n,X,Y,Z,ans;
int fac[MAXN],ifac[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int qpow(int x,int y){
int ret = 1;
while(y){
if(y & 1) ret = 1ll * ret * x % MOD;
x = 1ll * x * x % MOD;
y >>= 1;
}
return ret;
}
void init(int x)
{
fac[0] = ifac[0] = 1;
for(int i = 1;i <= x;++ i) fac[i] = 1ll * fac[i-1] * i % MOD;
ifac[x] = qpow(fac[x],MOD-2);
for(int i = x-1;i >= 1;-- i) ifac[i] = ifac[i+1] * (i+1ll) % MOD;
}
LL C(int x,int y){
if(x < y || y < 0) return 0;
return 1ll * fac[x] * ifac[y] % MOD * ifac[x-y] % MOD;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n = Read(); X = Abs(Read()); Y = Abs(Read()); Z = Abs(Read());
if(X+Y+Z > n) {Put(0,'\n');return 0;}
if((n-(X+Y+Z)) & 1) {Put(0,'\n');return 0;}
init(n);
for(int k = 0;X+Y+(k<<1)+Z <= n;++ k){
LL tmp = C(X+Y+(k<<1),X+k) * C(X+Y+(k<<1),X+Y+k) % MOD,nd = n-X-Y-(k<<1);
LL t1 = ((nd-Z) >> 1) + Z,t2 = nd - t1;
tmp = tmp * C(X+Y+(k<<1)+t1,t1) % MOD;
tmp = tmp * C(X+Y+(k<<1)+t1+t2,t2) % MOD;
ans = (ans + tmp) % MOD;
}
Put(ans,'\n');
return 0;
}
后记
听说jiangly哥哥vp的时候也没过。