【题解】P7481 Real D
Owen_codeisking
2021-04-07 14:10:41
昨天某佬过来问我此题,想了一想,想出来了一个麻烦的做法。
定义三元函数 $f(n,a,b)=\sum {b\choose i}{n-i\choose a}$
现在来研究她的递推式:
$$f(n,a,b)=\sum {b\choose i}{n-i\choose a}$$
$$={n\choose a}+\sum_{i\ge 1} ({b-1\choose i}+{b-1\choose i-1}){n-i\choose a}$$
$$={n\choose a}+\sum_{i\ge 1} {b-1\choose i}{n-i\choose a}+\sum_{i\ge 1}{b-1\choose i-1}{n-i\choose a}$$
$$=f(n,a,b-1)+f(n-1,a,b-1)$$
接着我们发现对于 ${n-i\choose a}$ 也进行类似的变形,可以得到:
$$f(n,a,b)=f(n-1,a,b)+f(n-1,a-1,b)$$
将这个递推式代到上面,可以得到:
$$f(n,a,b)=f(n-1,a-1,b-1)+2\times f(n-1,a,b-1)$$
可以发现这个递推式 $n$ 和 $b$ 同时 $-1$,只有 $a$ 有时不变有时 $-1$。
根据某套路,将这个递推式视为一个三维平面的游走模型,以 $n,b,a$ 为 $x,y,z$ 轴。那么我们每次就是对角线走一步,或者对角线走完后走到上面的平面。而且,$f(n,a,b)$ 只和 $f(n-b,i,0)$ 有关。
$f(n-b,i,0)={n-b\choose i}$。而从 $(n-b,i,0)$ 走到 $(n,a,b)$ 时,共走了 $b$ 步,有 $a-i$ 次选择向上走,每次方案数为 $1$;有 $b-a+i$ 次选择不往上走,每次方案数为 $2$。
那么函数就可化为:
$$f(n,a,b)=\sum 2^{b-a+i}{n-b\choose i}{b\choose a-i}$$
将 $2^{b-a}$ 提出来:
$$f(n,a,b)=2^{b-a}\sum 2^i{n-b\choose i}{b\choose a-i}$$
$$=2^{b-a}(1+2x)^{n-b}(1+x)^b[x^a]$$
以上解决的是 $b\ge a$ 的问题,但实际上 $b<a$ 类似,可以推出相同的结论。
接着可以先预处理出 $(1+2x)^n$ 的前 $m$ 项多项式,每次乘上 $(1+x)$ 后除掉 $(1+2x)$。因为每次操作乘或除的都是一次式,所以单次 $\mathcal{O}(m)$,总时间 $\mathcal{O}(m^2)$。
突然想了一下,这个做法是不是可以拓展?比如给出 $n,b$ 求一行 $a$,$n,b\le 10^9,a\le 10^5$。