light oj 1132 Summing up Powers-阿里云开发者社区

开发者社区> 人工智能> 正文

light oj 1132 Summing up Powers

简介: 点击打开light oj 1132 思路: 构造矩阵+矩阵快速幂 分析: 1 题目给定n和k要求(1K + 2K + 3K+ ... + NK) % 232 2 具体的思路见下图    3 对于求组合数,我们可以利用公式C(n , ...

点击打开light oj 1132

思路: 构造矩阵+矩阵快速幂

分析:

1 题目给定n和k要求(1K + 2K + 3K+ ... + NK) % 232

2 具体的思路见下图

  

3 对于求组合数,我们可以利用公式C(n , k+1) = C(n , k)*(n-k)/(k+1) ,那么我们可以先打表求出50之内的所有的组合数


代码:

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-29                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ************************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int64 MOD = (int64)1<<32;
const int N = 55;

int64 n , k;
int64 c[N][N];
struct Matrix{
    int64 mat[N][N]; 
    Matrix operator*(const Matrix &m)const{
        Matrix tmp;
        for(int i = 0 ; i < (k+2) ; i++){
            for(int j = 0 ; j < (k+2) ; j++){
                tmp.mat[i][j] = 0;
                for(int t = 0 ; t < (k+2) ; t++)
                    tmp.mat[i][j] += mat[i][t]*m.mat[t][j]%MOD;
                tmp.mat[i][j] %= MOD;
            }
        }
        return tmp;
    } 
};

int64 getVal(){
    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][j-1]*(i-j+1)/(j);
    }
}

void init(Matrix &m){
    memset(m.mat , 0 , sizeof(m.mat));
    for(int i = 0 ; i <= k ; i++){
        int x = 0;
        for(int j = i ; j <= k ; j++ , x++)
            m.mat[i][j] = c[k-i][x];
    }
    for(int i = 0 ; i <= k ; i++)
        m.mat[k+1][i] = m.mat[0][i];
    m.mat[k+1][k+1] = 1;
}

int64 Pow(Matrix &m){
    Matrix ans;
    memset(ans.mat , 0 , sizeof(ans));
    for(int i = 0 ; i <= k+1 ; i++)
        ans.mat[i][i] = 1;
    n--;
    while(n){
        if(n%2)    
            ans = ans*m;
        n /= 2;
        m = m*m;
    }
    int64 sum = 0;
    for(int i = 0 ; i < k+2 ; i++){
        sum += ans.mat[k+1][i]%MOD;
        sum %= MOD;
    }
    return sum;
}

int main(){
    int cas = 1;
    int Case;
    Matrix m;
    getVal();
    scanf("%d" , &Case);
    while(Case--){
        scanf("%llu%llu" , &n , &k);
        init(m);
        printf("Case %d: " , cas++); 
        printf("%llu\n" , Pow(m));
    }
    return 0;
}




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章