三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

题解:AT_abc458_e [ABC458E] Count 123

题解:AT_abc458_e [ABC458E] Count 123

题目传送门

AtCoder

题目大意

用 \(X_1\) 个 \(1\),\(X_2\) 个 \(2\) 和 \(X_3\) 个 \(3\) 组成一个序列,要求相邻两个数 \(a_i\) 和 \(a_{i+1}\) 的绝对值之差 \(|a_{i+1}-a_i| \leq 1\)。

思路

分析条件

注意到 \(|a_{i+1}-a_i| \leq 1\) 意味着:

  • \(1\) 和 \(2\) 可以相邻(因为 \(|1-2|=1\))
  • \(2\) 和 \(3\) 可以相邻(因为 \(|2-3|=1\))
  • \(1\) 和 \(3\) 不能相邻(因为 \(|1-3|=2\))

因此,构造出的序列中相邻的 \(1\) 和 \(3\) 之间必须用 \(2\) 隔开。


所以,我们可以把 \(2\) 当作隔板,把 \(X_2\) 个 \(2\) 排成一排如下:

\(\_,2,\_,2,\_,\dots,\_2,\_,2,\_\)

这 \(X_2\) 个 \(2\) 总共形成了 \(X_2+1\) 个空隙,每个空隙都可以放若干个 \(1\) 或若干个 \(3\),但是 \(1\) 和 \(3\) 不能出现在同一个空隙中。

组合计数

考虑组合计数。

设 \(s=X_2+1\),表示空隙总数。

枚举 \(i\) 满足 \(1 \leq i \leq \min(X_1,s)\),\(j\) 满足 \(1 \leq j \leq \min(X_3,s-i)\)。

接下来可以分四步计算。

1.选空隙

从 \(s\) 个空隙中选择 \(i\) 个放 \(1\),剩余 \(s-i\) 个中选 \(j\) 个放 \(3\):

\[\binom{s}{i} \cdot \binom{s-i}{j} \]

2.分配 \(1\)

隔板法。

把 \(X_1\) 个 \(1\) 放入 \(i\) 个非空盒子:

\[\binom{X_1-1}{i-1} \]

3.分配 \(3\)

把 \(X_3\) 个 \(3\) 放入 \(j\) 个非空盒子:

\[\binom{X_3-1}{j-1} \]

4.求总方案数

总方案数即:

\[\sum_{i=1}^{\min(X_1,s)} \sum_{j=1}^{\min(X_3,s-i)} \binom{s}{i} \binom{s-i}{j} \binom{X_1-1}{i-1} \binom{X_3-1}{j-1} \]

优化

上述公式显然超时,考虑优化掉内层循环。

定义:

\[g[r] = \sum_{j=1}^{\min(X_3,\, r)} \binom{r}{j} \cdot \binom{X_3 - 1}{j - 1} \]

其中 \(r\) 为可用的空隙数量(\(r=X_2+1-i=s-i\))

含义:有 \(r\) 个空隙,把 \(X_3\) 个 \(3\) 放入其中(可不放一些空隙)的方案数。

则:

\[\sum_{i=1}^{\min(X_1,s)} \sum_{j=1}^{\min(X_3,s-i)} \binom{s}{i} \binom{s-i}{j} \binom{X_1-1}{i-1} \binom{X_3-1}{j-1}=\sum_{i=1}^{\min(X_1,s)} \sum_{j=1}^{\min(X_3,s-i)} \binom{s}{i} \binom{X_1-1}{i-1} \cdot g[r] \]

令 \(t=j-1\):

\[g[r]=\sum_{t=0}^{\min(X_3-1, r-1)} \binom{r}{t+1} \binom{X_3-1}{t} \]

由于 \(\binom{r}{t+1} = \binom{r}{r-1-t}\),所以:

\[g[r]=\sum_{t} \binom{r}{r-1-t} \binom{X_3-1}{t} \]

考虑使用范德蒙德卷积:

\[\sum_{i=0}^k \binom{n}{i} \binom{m}{k-i}=\binom{n+m}{k} \]

此处:

  • \(n=r\)
  • \(m=X_3-1\)
  • \(k=r-1\)

所以:

\[g[r]=\binom{r+X_3-1}{r-1} \]

总方案数:

\[\sum_{i=1}^{\min(X_1,s)} \binom{s}{i} \binom{X_1-1}{i-1} \binom{r+X_3-1}{r-1} \]

所以,在线性时间复杂度内就可求出答案。


特殊情况

  • 若 \(X_3=0\),则内层的贡献必然始终为 \(1\)。每次加上 \(\sum_{i=1}^{\min(X_1,s)} \binom{s}{i} \binom{X_1-1}{i-1}\) 即可。
  • 若 \(X_1=0\),与 \(X_3=0\) 同理。
  • 若 \(r=0\)(即 \(i=s\))
    • 若 \(X_3=0\),则 \(g[0]=1\)。
    • 若 \(X_3 \neq 0\),则 \(g[0]=0\)。

代码

AC Code
#include <iostream>
#define int long long
using namespace std;
const int p=998244353;
int ksm(int a,int b,int MOD)
{int res=1;while(b){if(b&1){res=(res*a)%MOD;}a=(a*a)%MOD;b>>=1;}return res;
}
int f[2000005],fn[2000005],x1,x2,x3,ans,x,g,s;
int c(int n,int m)
{if(m<0||m>n){return 0;}return f[n]*fn[m]%p*fn[n-m]%p;
}
signed main()
{f[0]=1;for(int i=1;i<=2000000;i++){f[i]=f[i-1]*i%p;}fn[2000000]=ksm(f[2000000],p-2,p);for(int i=1999999;i>=0;i--){fn[i]=fn[i+1]*(i+1)%p;}cin >> x1 >> x2 >> x3;s=x2+1;for(int i=1;i<=min(x1,s);i++){x=s-i;if(x<0)break;x=c(s,i)*c(x1-1,i-1)%p;if(x3==0){ans=(ans+x)%p;}else{if(s-i==0){g=(x3==0?1:0);}else{g=c(s-i+x3-1,s-i-1);}ans=(ans+x*g)%p;}}cout << ans;return 0;
}
← 返回列表