在题解中看到一个式子,题解说是二项式反演,但我推不出来/kk
f(i,j)=∑x=in∑y=jn(xi)(yj)(−1)(x−i)+(y−j)g(x,y)⇔g(x,y)=∑x=in∑y=jn(xi)(yj)f(x,y)f(i,j)=\sum_{x=i}^n\sum_{y=j}^n{x\choose i}{y\choose j}(-1)^{(x-i)+(y-j)}g(x,y)\Leftrightarrow g(x,y)=\sum_{x=i}^n\sum_{y=j}^n{x\choose i}{y\choose j}f(x,y)f(i,j)=∑x=in∑y=jn(ix)(jy)(−1)(x−i)+(y−j)g(x,y)⇔g(x,y)=∑x=in∑y=jn(ix)(jy)f(x,y)
注,二项式反演:f(n)=∑i=0n(ni)g(i)⇔g(n)=∑i=0n(ni)(−1)n−if(i) f(n)=\sum_{i=0}^n{n\choose i}g(i)\Leftrightarrow g(n)=\sum_{i=0}^n{n\choose i}(-1)^{n-i}f(i)f(n)=∑i=0n(in)g(i)⇔g(n)=∑i=0n(in)(−1)n−if(i)