频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
BZOJ 2326 HNOI 2011 数学作业 矩阵乘法
2015-03-03 14:57:53         来源:(╯°口°)╯(┴—┴  
收藏   我要投稿

题目大意

求一个这样的数:“12345678910111213……”对m取模的值。

思路

观察这个数字的特点,每次向后面添加一个数。也就是原来的数乘10^k之后在加上一个数。而且处理每个数量级的时候是相似的。所以就可以用矩阵乘法来加速。我构造的矩阵是这样的。
[当前数字累加数字1]×???数量级10011001???=[新的数字累加数字+11]

CODE

#include 
#include 
#include 
#include 
#define MO p
using namespace std;

long long k,p;

struct Matrix{
    long long num[5][5];
    int w,h;

    Matrix(int _,int __):w(_),h(__) {
        memset(num,0,sizeof(num));
    }
    Matrix() {
        memset(num,0,sizeof(num));
    }
    Matrix operator *(const Matrix &a)const {
        Matrix re(w,a.h);
        for(int i = 1; i <= w; ++i)
            for(int j = 1; j <= a.h; ++j)
                for(int k = 1; k <= h; ++k)
                    re.num[i][j] = (re.num[i][j] + num[i][k] * a.num[k][j] % MO) % MO;
        return re;
    }
};

inline Matrix QuickPower(Matrix a,long long k)
{
    Matrix re(3,3);
    re.num[1][1] = re.num[2][2] = re.num[3][3] = 1;
    while(k) {
        if(k&1) re = re * a;
        a = a * a;
        k >>= 1;
    }
    return re;
}

int main()
{
    cin >> k >> p;
    long long now = 10,ans_num = 0;
    while(k >= now - now / 10 && now < 1e18) {
        k -= now - now / 10;
        Matrix right(3,3);
        right.num[1][1] = now % MO;
        right.num[2][1] = right.num[2][2] = right.num[3][2] = right.num[3][3] = 1;
        right = QuickPower(right,now - now / 10);
        Matrix left(1,3);
        left.num[1][1] = ans_num;
        left.num[1][2] = (now / 10) % MO;
        left.num[1][3] = 1;
        ans_num = (left * right).num[1][1];
        now *= 10;
    }
    Matrix right(3,3);
    right.num[1][1] = now % MO;
    right.num[2][1] = right.num[2][2] = right.num[3][2] = right.num[3][3] = 1;
    right = QuickPower(right,k);
    Matrix left(1,3);
    left.num[1][1] = ans_num;
    left.num[1][2] = (now / 10) % MO;
    left.num[1][3] = 1;
    cout << (left * right).num[1][1] << endl;
    return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 乘法 矩阵 数学
上一篇:[Leetcode]Single Number
下一篇:CodeForces 520C DNA Alignment
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站