【题解】P7481 Real D

Owen_codeisking

2021-04-07 14:10:41

Solution

昨天某佬过来问我此题,想了一想,想出来了一个麻烦的做法。 定义三元函数 $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$。