【算法与数据结构】——自然幂数求和公式

傷城~ 2022-09-04 14:45 168阅读 0赞

# 自然幂数求和 #

自然幂数求和指的是 ∑ i = 0 n i p \\sum\_\{i=0\}^ni^p ∑i=0nip p是常数。  
关于各种求解自然幂数和的方法，可以参考博客[自然数幂和小结][Link 1]，我就不详细整理了，主要还是没有全部学会，我在这里只记录一种较为简单的差分法的求解代码作为模板。时间复杂度 O ( k 2 ) O(k^2) O(k2)

#include <bits/stdc++.h>
    using namespace std;
    const int K = 1005;//k的最大值
    int fnv[K];
    int d[K];
    
    const int P = 1e9 + 7;
    int pw(int a, int m) { 
        int res = 1;
        while (m)
        { 
            if(m&1)
            { 
                res = 1ll * res * a % P;
            }
            a = 1ll * a * a % P;
            m >>= 1;
        }
        return res;
    }
    
    void work(int k, int *d) {  // prepare for 0^k + 1^k + 2^k + ...
        for(int i = 0;i <= k+1;i++)
        { 
            d[i] = pw(i, k);
        }
        for(int i = 1;i <= k+1;i++)
        { 
            for(int j = k + 1;k >= i + 1;k--)
            { 
                d[j] = (d[j] - d[j - 1] + P) % P;
            }
        }
        fnv[0] = 1;
        for(int i = 1;i <= k + 1;i++)
        { 
            fnv[i] = 1ll * fnv[i - 1] * pw(i, P - 2) % P;
        }
    }
    
    int calc(int n, int k, int *d) {  // 0^k + ... + n^k
        int res = 0, coef = 1;
        for(int i = 0;i <= k+1;i++)
        { 
            res = (res + 1ll * coef * fnv[i] % P * d[i]) % P;
            coef = 1ll * coef * (n - i) % P;
        }
        return res;
    }
    
    int main() { 
        int n, k;
        scanf("%d%d", &n, &k);
        work(k, d);
        printf("%d\n", calc(n, k, d));
        return 0;
    }

[Link 1]: https://notes.sshwy.name/Math/Faulhaber/