NOIP rp++！|| solution - AT_abc433_f

· · 题解

OI 生涯最后一场 abc 了。写篇题解留下个纪念吧。

作为一个非常不会数数题的人，罕见的场切了数数题，保佑我 NOIP 也有这样的运气吧。

首先因为每个情况都可以表示为一段 i 拼上一段 i+1 的形式，所以只讨论 i=1 的情况，其它情况都是同理的。

枚举中间的那个 1，考虑这个 1 右边的每个 2。分别统计这个 1 左边 1 的个数、这个 2 右边 2 的个数，可以得到得到这样的序列：

\underbrace{11 \ldots 1} _{x \text{个}} 1 2 \underbrace{22 \ldots 2} _{y \text{个}}

那么考虑最左边的 2（即和 1 相邻的那个 2）可能是哪个，以及选几个数（这样可以保证不重不漏），可以得到式子：

\begin{aligned} & \sum _{i=0} ^y \sum _{j=0} ^{\min(i,x)} \binom x j \binom i j \\ = & \sum _{i=0} ^y \sum _{j=0} ^x \binom x j \binom i j \\ = & \sum _{i=0} ^y \sum _{j=0} ^x \binom x {x-j} \binom i j \\ = & \sum _{i=0} ^y \binom {x+i} x \\ = & \binom {x+y+1} {x+1} \end{aligned}

第一步是因为 j>i 的部分 \binom i j = 0，所以 \min 可以直接丢掉不管；第二步没什么好说的；第三步是范德蒙德恒等式；第四步是【我不知道叫什么】恒等式。

可以参考组合数学常用的基础恒等式。

时间复杂度 O(n|\Sigma|)，其中 |\Sigma| 为字符集大小，在本题中为 10。精细实现可以做到 O(n) 不过我懒。

代码：

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,nxt[N][10],cnt[N][10];
string s;

il void solve(int __Ti)
{
    read(s),n=s.size(),s="$"+s+"###";

    rep(j,0,9) nxt[n+1][j]=n+1;
    rpe(i,n,1) rep(j,0,9) nxt[i][j]=s[i+1]-'0'==j?i+1:nxt[i+1][j],cnt[i][j]=cnt[i+1][j]+(s[i]-'0'==j);

    int ans=0,x,y;
    rep(i,1,n) if(s[i]<'9')
    {
        x=cnt[1][s[i]-'0']-cnt[i][s[i]-'0'];
        y=cnt[nxt[i][s[i]-'0'+1]][s[i]-'0'+1]-1;
        if(y<0) continue;
        add(ans,C(x+y+1,x+1));
    }

    write(ans);
}

华风夏韵，洛水天依！

NOIP rp++！