算法笔记--数学之自然数幂和

r囧r小猫 2022-01-12 11:59 184阅读 0赞

**1.递推求法**

![1130834-20190226155006118-2122154575.png][]

![1130834-20190226155015346-1185806388.png][]

![1130834-20190226155030765-680530824.png][]

记

![1130834-20190226155102052-1443844885.png][]

得到递归式：

![1130834-20190226155120228-987129437.png][]

这个可以用记忆化搜索求出S(n, k)， 复杂度：O(k \* k)

例题：

[ZOJ 2865][]

代码：

import java.util.*;
    import java.math.*;
    
    public class Main {
    
        /**
         * @param args
         */
        public static final int N = 100 + 10;
        public static final BigInteger f = BigInteger.ZERO.subtract(BigInteger.ONE);
        public static BigInteger C [][] = new BigInteger[N][N];
        public static BigInteger P [] = new BigInteger[N];
        public static BigInteger dp[] = new BigInteger[N];
        public static BigInteger n;
        public static int k;
        public static void init() {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j)
                        C[i][j] = BigInteger.ZERO;
            }
            C[0][0] = BigInteger.ONE;
            for (int i = 1; i < N; ++i) {
                C[i][0] = BigInteger.ONE;
                for (int j = 1; j <= i; ++j) {
                    C[i][j] = C[i-1][j-1].add(C[i-1][j]);
                }
            }
        }
        public static BigInteger DFS(int k) {
            if(dp[k].compareTo(f) != 0) return dp[k];
            if(k == 0) return dp[k] = n;
            if(k == 1) return dp[k] = n.multiply(n.add(BigInteger.ONE)).divide(BigInteger.valueOf(2));
            BigInteger res = P[k+1];
            for (int i = 2; i <= k; ++i) {
                res = res.subtract(C[k+1][i].multiply(DFS(k+1-i)));
            }
            res = res.subtract(n);
            res = res.subtract(BigInteger.ONE);
            res = res.divide(BigInteger.valueOf(k+1));
            return dp[k] = res; 
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            init();
            P[0] = BigInteger.ONE;
            while(in.hasNext()) {
                n = in.nextBigInteger();
                k = in.nextInt();
                for (int i = 1; i <= k+1; ++i) P[i] = P[i-1].multiply(n.add(BigInteger.ONE));
                for (int i = 0; i <= k+1; ++i) dp[i] = f;
                System.out.println(DFS(k));
            }
        }
    
    }

**2.伯努利数**

伯努利数定义：

[https://www.bernoulli.org/][https_www.bernoulli.org]

伯努利数和自然数幂和之间的关系：

![1130834-20190226155501003-1712095016.png][]

伯努利数的递推求法：

![1130834-20190226155700302-469275924.png][]

![1130834-20190226155706373-1612061400.png][]

观察式子我们可以发现，可以通过O(k\*k) 预处理出伯努利数，然后每次O(k)求自然数幂和

例题1：

[51nod 1228][]

代码：

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<cstdio>
    #include<iostream>
    #include<cmath>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 2e3 + 5;
    const int MOD = 1e9 + 7;
    LL C[N][N];
    LL B[N], inv[N];
    void init() {
        C[0][0] = 1;
        for (int i = 1; i < N; ++i) {
            C[i][0] = 1;
            for (int j = 1; j <= i; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;
        }
        inv[1] = 1;
        for (int i = 2; i < N; ++i) inv[i] = (MOD - MOD/i) * inv[MOD%i] % MOD;
        B[0] = 1;
        for (int i = 1; i < N-1; ++i) {
            LL t = 0;
            for (int j = 0; j < i; ++j) {
                t = (t + C[i+1][j]*B[j]%MOD) % MOD;
            }
            t = (-t * inv[i+1]) % MOD;
            t = (t + MOD) % MOD;
            B[i] = t;
        }
    }
    int main() {
        init();
        int T, k;
        LL n;
        scanf("%d", &T);
        while(T--) {
            scanf("%lld %d", &n, &k);
            LL p = 1, res = 0;
            for (int i = 1; i <= k+1; ++i) {
                p = (p * ((n+1)%MOD)) % MOD;
                res = (res + (C[k+1][i]*B[k+1-i]%MOD*p)%MOD) % MOD;
            }
            res = (res * inv[k+1]) % MOD;
            printf("%lld\n", res);
        }
        return 0;
    }

例题2：

[51nod 1258][]

这道题k很大以至于不能O(k\*k)预处理出伯努利数

于是

![1130834-20190226160153383-5753313.png][]

这种方法可以O(k\*log(k))预处理伯努利数

可是不会NTT。。。未完待续

参考：

[https://blog.csdn.net/ACdreamers/article/details/38929067][https_blog.csdn.net_ACdreamers_article_details_38929067]

[http://picks.logdown.com/posts/189620-the-inverse-element-of-polynomial][http_picks.logdown.com_posts_189620-the-inverse-element-of-polynomial]

转载于:https://www.cnblogs.com/widsom/p/10437987.html

[1130834-20190226155006118-2122154575.png]: /images/20220109/c2f81c5ff89e448f8b902140ba3d3422.png
[1130834-20190226155015346-1185806388.png]: /images/20220109/9f81e65861c940f9a0013ad18474d23f.png
[1130834-20190226155030765-680530824.png]: /images/20220109/fc05a1e30bee421a87d377be78f03ddd.png
[1130834-20190226155102052-1443844885.png]: /images/20220109/26701049a7a04cb08228f038f32b58ae.png
[1130834-20190226155120228-987129437.png]: /images/20220109/52ab9fc0cc5744909baba1d2f637ff66.png
[ZOJ 2865]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1864
[https_www.bernoulli.org]: https://www.bernoulli.org/
[1130834-20190226155501003-1712095016.png]: /images/20220109/33015a23beb1477fb4676c97fb2f7cef.png
[1130834-20190226155700302-469275924.png]: /images/20220109/3fa69e6ef45c4d92bc993fb0bacecda5.png
[1130834-20190226155706373-1612061400.png]: /images/20220109/23deb9fd78694266be3347ff3eee6f6d.png
[51nod 1228]: http://www.51nod.com/Challenge/Problem.html#!%23problemId=1228
[51nod 1258]: http://www.51nod.com/Challenge/Problem.html#!%23problemId=1258
[1130834-20190226160153383-5753313.png]: /images/20220109/6b91cdeea00f48debd4b23f5fbe21cdf.png
[https_blog.csdn.net_ACdreamers_article_details_38929067]: https://blog.csdn.net/ACdreamers/article/details/38929067
[http_picks.logdown.com_posts_189620-the-inverse-element-of-polynomial]: http://picks.logdown.com/posts/189620-the-inverse-element-of-polynomial