light oj 1132 Summing up Powers

点击打开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;
}
时间: 2024-10-25 18:26:33

light oj 1132 Summing up Powers的相关文章

矩阵快速幂专题【完结】

第一题 hdu 1757 A Simple Math Problem 点击打开链接 思路:矩阵快速幂 分析: 1 最简单的矩阵快速幂的题目,直接利用矩阵求解即可 点击打开查看代码 第二题 hdu 1575 Tr A 点击打开hdu 1575 思路: 矩阵快速幂 分析: 1 题目给定一个n*n的矩阵要求矩阵的k次幂之后的矩阵的对角线的和 2 矩阵快速幂的裸题 点击打开查看代码 第三题 hdu 2604 Queuing 点击打开hdu 2604 思路: 递推+矩阵快速幂 分析; 1 根据题目的意思,

c语言-OJ的输入输出 C语言的输入输出多组测试数据

问题描述 OJ的输入输出 C语言的输入输出多组测试数据 请问OJ测试代码时是如何输入输出的?C语言如何实现多组数据的输出?比如这道题 "水仙花数"是指一个三位数,它的各位数字的立方和等于其本身,比如:153=1^3+5^3+3^3. 现在要求输出所有在m和n范围内的水仙花数. Input 输入数据有多组,每组占一行,包括两个整数m和n(100<=m<=n<=999). Output 对于每个测试实例,要求输出所有在给定范围内的水仙花数,就是说,输出的水仙花数必须大于等

字母大小写转换 算法-OJ上一道字母大小写转换的题

问题描述 OJ上一道字母大小写转换的题 OJ上的一道题,题目是:cAPS lOCK我写的代码链接:http://codepad.org/JrJrOGxQ 自己在编译器上编译时 没发现有什么错,但是在OJ上提交时出现:wrong answer on test 6不知道哪里错了 解决方案 大小写字母转换字母大小写转换字母大小写转换 解决方案二: 估计是不是你没有考虑对数字和其它字符的判断,导致没有通过测试用例. 我运行了你的程序,的确,对于如下情况,你的程序都没有问题:只有一个小写字母,比如z全部大

CSS 滤镜——Mask,Light滤镜

css|滤镜 Mask 滤镜语法 {filter:mask(color=color)} 使用"MASK"属性可以为对象建立一个覆盖于表面的膜,其效果就象戴着有色眼镜看物体一样 . 原表格拷屏   CSS 滤镜效果实现欢迎光临天极设计在线 效果拷屏 Light 滤镜 Light 滤镜语法 {filter:light} 这个属性模拟光源的投射效果.一旦为对象定义了"LIGHT"滤镜属性,那么就可以调用它的"方法(Method)"来设置或者改变属性.&

Light Room处理图片教程:处理灰蒙蒙照片

导言:这套教程可能相对老一点,不过对图片后期感兴趣,或者想使用Light Room来处理图片的专业人士来说,都会有一定的启示,希望你们能在教程中学到知识! 我这里说的只有LR的处理噢-,我先提一下:Camera Raw+Ps也可以做出同样的效果觉得自己Ps+Br就能做的跟LR一样快一样好或者像一些坚决排斥认识新软件,认为自己做得已经很好的同学可以看其他的东西-- 这里是对比图 请注意,这只是一张样图 原图很灰很数码 请注意,这只是一张样图 此图相对有比较好的对比和比较油润一些的颜色.可能样图比较

UVa 11332 Summing Digits (water ver.)

11332 - Summing Digits Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2307 For a positive integer n, let f(n) denote the sum of the digits of n when repr

UVa 112 Tree Summing (scanf()去空格&amp;amp;递归&amp;amp;二叉树遍历)

112 - Tree Summing Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=48 Background LISP was one of the earliest high-level programming languages and, with FORTRAN, is one o

UVa 10110 Light, more light:数论

10110 - Light, more light Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=100&page=show_problem&problem=1051 The Problem There is man named "mabu" for switching on-off light

UVa 11752 The Super Powers (数学)

11752 - The Super Powers Time limit: 1.000 seconds http://uva.onlinejudge.org/index.php? option=com_onlinejudge&Itemid=8&category=467&page=show_problem&problem=28 52 We all know the Super Powers of this world and how they manage to get adv