前言
疑似是有点不会数学了，照着题解推式子都推了小半个下午，还看不出来减法公式，唉。
题解
考虑把这些 \(f(a,b)\) 异或起来再模一个数不会有很好的性质，所以要把每一个 \(f(a,b)\) 都算出来。
由加法公式得
\[f(a,b)=\sum \ \tbinom{b}{i}\tbinom{n-i}{a} \]\[= \sum \tbinom{b-1}{i}\tbinom{n-i}{a}+\sum \tbinom{b-1}{i-1}\tbinom{n-i}{a} \]\[=f(a,b-1)+\sum\tbinom{b-1}{i}\tbinom{n-i-1}{a} \]再想办法把加号后面的式子用 \(f\) 表示。
由减法公式得
原式=
\[f(a,b-1)+\sum \tbinom{b-1}{i}\tbinom{n-i}{a}-\sum \tbinom{b-1}{i}\tbinom{n-i-1}{a-1} \]\[2 \times f(a,b-1)-\sum \tbinom{b-1}{i}\tbinom{n-i-1}{a-1} \]接着表示减号后面的
原式=
\[2 \times f(a,b-1)-(\sum \tbinom{b}{i+1}\tbinom{n-i-1}{a-1}-\sum\tbinom{b-1}{i+1}\tbinom{n-i-1}{a-1}) \]\[=\sum \tbinom{b}{i}\tbinom{n-i}{a-1}-\sum\tbinom{b-1}{i}\tbinom{n-i}{a-1} \]\[=f(a-1,b)-f(a-1,b-1) \](后面省略了减号之前的部分)
整理得
\(f(a,b)=2 \times f(a,b-1)-f(a-1,b)+f(a-1,b-1)\)
然后就递推算每一个 \(f(a,b)\) 就行了。
这里要注意一下边界。
然后复杂度是 \(O(m^2)\) 的。
标签：数论,题解,sum,times,算法,tbinom,公式,减号 From： https://www.cnblogs.com/infinite2021/p/18119431