BZOJ3157: 國王奇遇記 & 3516: 國王奇遇記加強版

令

Si=∑k=1nkimk

我們有

(m?1)Si======mSi?Si∑k=1nkimk+1?∑k=1nkimk∑k=2n+1(k?1)imk?∑k=1nkimknimn+1+∑k=1nmk((k?1)i?ki)nimn+1+∑k=1n(∑j=1i?1(?1)i?j(ij)kjmk)nimn+1+∑j=0i?1(?1)i?j(ij)Sj

直接按照這條式子O(n2)

遞推即可。