binom を多項式として見るテク

TODO: 書く

0≤x$0\le x$ に対して、 (xr)=x(x−1)…(x−r+1)r!$(\genfrac{}{}{0ex}{}{x}{r})=\frac{x(x-1)\dots (x-r+1)}{r!}$ であるので、これは x$x$ の r$r$ 次多項式としてみなせる

例題1 ラグランジュ補間

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2951
解説 https://jag-icpc.org/?plugin=attach&refer=2019%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=H.pdf

定義域に注意すること。
x<0$x<0$ においては、 (xr)=0$(\genfrac{}{}{0ex}{}{x}{r})=0$ とすることが多く、 x(x−1)…(x−r+1)r!$\frac{x(x-1)\dots (x-r+1)}{r!}$ で計算すると値がおかしくなってしまう。

例題2 陽に多項式を求める

www.codechef.com

x(x−1)…(x−r+1)$x(x-1)\dots (x-r+1)$ は第1種スターリング数と呼ばれる数列に関係している。
第1種スターリング数はダブリングを用いて O(NlogN)$O(N\log N)$ で陽に求めることができる

追記

例題3 なんですかこれ（HIRさんに教えてもらいました　ありがとうございます）

問題 community.topcoder.com
解説 codeforces.com

えーすごいね　包除しようとしたら破滅した　なんだこれ
m-nが小さいからエスパーできるのかな