先膜一发，大佬的博客上多项式相关的非常全

题目大意

求

\[\sum\limits_{i=1}^{n}i^mm^i\]

题解

设一个函数\(f(i)=\sum\limits_{j=1}^{n}j^im^j\)

然后貌似用一个叫扰动法（感觉就是错位相消法）的东西，算一下

\[(m-1)f(i)=\sum\limits_{j=1}^{n+1}(j-1)^im^j-\sum\limits_{i=1}^{n}j^im^j=n^im^{n+1}-\sum\limits_{j=1}^{n}m^j[(j-1)^i-j^i]\]

其中，\((j-1)^i-j^i\)可以用一波二项式展开化为\(\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}j^k\)，回带可得

\[(m-1)f(i)=n^im^{n+1}-\sum\limits_{j=1}^{n}m^j\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}j^k\]\[=n^im^{n+1}-\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}\sum\limits_{j=1}^{n}j^km^j\]\[=n^im^{n+1}-\sum\limits_{k=0}^{i-1}\binom{i}{k}(-1)^{i-k}f(k)\]

然后就有了一个\(O(m^2)\)的递推做法，还有一个\(O(m)\)的，但看起来挺麻烦的，咕了

以下是代码，注意初值\(f(0)\)的设置还有\(m=1\)时的特判

#include 
    
     #include  
     
      #include   
      
       #include   
       
        #include    
        
         #include    
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include