Brief description :

计算1^k+2^k+..+n^k。
(1<=n<=10^41, 3<=k<=100)

Analyse :

这是一个重要问题，我目前痛并TLE着。

/*
    Author: xiaodao
    Prog: POJ 2515. Birthday Cake
    Status: Time Limited Error
    Last modifiy: GMT +8 Aug. 29th 17:51
*/
#include 
#include "bignum.h"
using namespace std;
const int M = 1001;
bignum D[M][M];
bignum n; int m;


// c(n, k)
bignum c(int k){
    bignum res = 1, nn = n;
    for (int i=1;i<=k;i++){
        res = res * nn; nn-=1;
        res = res / i;
    }
    return res;
}


// s(n, m)
bignum s(){
    bignum res = 0;
    for (int i=0;i<=m;i++)
        res += D[i][0] * c(i+1);
    return res;
}

void init(){
    cin >> n >> m;
    for (int i=0;i<=m;i++)
        D[0][i] = pow(i+1, m);

    for (int i=1;i<=m;i++)
        for (int j=0;j<=m-i;j++)
            D[i][j] = D[i-1][j+1] - D[i-1][j];
}

void patch(){
    for (int i=0;i<=m;i++){
        for (int j=0;j<=m-i;j++)
            cout << D[i][j] << " ";
        cout << endl;
    }
}


int main(){
    int T; cin >> T;
    while (T--){
        init(); //patch();
        cout << s() << endl;
    }
}

External link :

POJ 2515. Birthday Cake

Posted by xiaodao
Category: 日常