hdu 6050 Funny Function 矩阵快速幂

就算告诉我是矩阵快速幂我也推不出递推式呀!!!

官方题解:

对于任意i>=1,当j>=3时,有通过归纳法可以得到

进而推导出

我构造的矩阵是(2X2) * (2X1)的

所以和官方题解的矩阵位置相反

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const ll Mod=1e9+7;
const int msize=2;
const int N=4;

struct Mat
{
    ll mat[N][N];
};

Mat operator *(Mat a, Mat b)
{
    Mat c;
    memset(c.mat, 0, sizeof(c.mat));
    for(int k = 0; k < msize; ++k)
        for(int i = 0; i < msize; ++i)
            if(a.mat[i][k])
                for(int j = 0; j < msize; ++j)
                    if(b.mat[k][j])
                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;
    return c;
}

Mat operator ^(Mat a, ll k)
{
    Mat c;
    memset(c.mat,0,sizeof(c.mat));
    for(int i = 0; i < msize; ++i)
        c.mat[i][i]=1;
    for(; k; k >>= 1)
    {
        if(k&1) c = c*a;
        a = a*a;
    }
    return c;
}

Mat operator -(Mat a,Mat b)
{
    for(int i=0; i<msize; i++)
        for(int j=0; j<msize; j++)
            a.mat[i][j]=(a.mat[i][j]-b.mat[i][j])%Mod;
    return a;
}

int main()
{
//    freopen("in.txt","r",stdin);
    int t;
    ll n,m;
    Mat A,B1,B2;
    A.mat[0][0]=1,A.mat[0][1]=2;
    A.mat[1][0]=1,A.mat[1][1]=0;
    B1.mat[0][0]=B1.mat[1][1]=1;
    B1.mat[0][1]=B1.mat[1][0]=0;
    B2.mat[0][0]=0,B2.mat[0][1]=2;
    B2.mat[1][0]=1,B2.mat[1][1]=-1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64d%I64d",&n,&m);
        Mat ans;
        if(n%2==0) ans=((A^n)-B1)^(m-1);
        else ans=((A^n)-B2)^(m-1);
        printf("%I64d\n",(ans.mat[1][0]+ans.mat[1][1])%Mod);
    }
    return 0;
}
时间: 07-28

hdu 6050 Funny Function 矩阵快速幂的相关文章

HDU 2604 Queuing (矩阵快速幂)

HDU 2604 Queuing (矩阵快速幂) ACM 题目地址:HDU 2604 Queuing 题意: n个人排队,f表示女,m表示男,包含子串'fmf'和'fff'的序列为O队列,否则为E队列,有多少个序列为E队列. 分析: 矩阵快速幂入门题. 下面引用巨巨解释: 用f(n)表示n个人满足条件的结果,那么如果最后一个人是m的话,那么前n-1个满足条件即可,就是f(n-1): 如果最后一个是f那么这个还无法推出结果,那么往前再考虑一位:那么后三位可能是:mmf, fmf, mff, fff

HDU 5950 Recursive sequence 矩阵快速幂

http://acm.hdu.edu.cn/showproblem.php?pid=5950 一开始以为i^4不能矩阵快速幂,但是结论是可以得,那么要怎么递推呢? 矩阵快速幂的思路都是一样的,matrix_a * matrix_b ^ n 其中,想要维护什么,就在matrix_a写,比如现在是F[n - 1], F[n - 2],我想要递推到下一项,那么就 会变成F[n], F[n - 1],这个时候,你就要寻找一下F[n]和F[n - 1]有什么关系. i^4也一样,想要从i^4 递推到 (i

HDU 2842 Chinese Rings(矩阵快速幂+递推)

题目地址:HDU 2842 这个游戏是一个九连环的游戏. 假设当前要卸下前n个环.由于要满足前n-2个都卸下,所以要先把前n-2个卸下,需要f(n-2)次.然后把第n个卸下需要1次,然后这时候要卸下第n-1个,然后此时前n-2个都已经被卸下了.这时候把前n-2个都卸下与都装上所需的次数是一样的,因为卸下与装上的规则是一样的.所以又需要f(n-2)次,这时候前n-1个都在上面,卸下前n-1个需要f(n-1)次. 所以,总共需要2*f(n-2)+f(n-1)+1次. 然后构造如下矩阵. 1,2,1

hdu 2604 Queuing(矩阵快速幂乘法)

Problem Description Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time. Now we define that ‘f’ is short for female and

HDU 3117 Fibonacci Numbers(矩阵快速幂+公式)

题目地址:HDU 3117 对于后四位可以用矩阵快速幂快速求出来,但前四位就没办法了.要知道斐波那契数列是有通项公式的,所以只能通过通项公式来求前四位,但公式不能求后四位,因为公式使用浮点数求的,精度显然不够,求前四位要用到对数. 通项公式为: f(n)=1/sqrt(5)(((1+sqrt(5))/2)^n+((1-sqrt(5))/2)^n) 假设F[n]可以表示成 t * 10^k(t是一个小数),那么对于F[n]取对数log10,答案就为log10 t + K,此时很明显log10 t<

codeforces 678D Iterated Linear Function 矩阵快速幂

矩阵快速幂的题要多做 由题可得 g[n]=A*g[n-1]+B 所以构造矩阵  { g[n] }    =  {A   B}  * { g[n-1]} {   1   }         {0   1}     {    1    } 然后矩阵快速幂就好 矩阵快速幂的题要多做,多构造矩阵 注:其实这个题可以直接等比数列求求和,单数矩阵快速幂对于这类题更具有普遍性 #include <cstdio> #include <iostream> #include <ctime>

hdu 5667 Sequence【矩阵快速幂】

Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 285    Accepted Submission(s): 92 Problem Description Holion August will eat every thing he has found. Now there are many foods,but he d

2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6155 Subsequence Count 矩阵快速幂

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6155 题意: 题解来自:http://www.cnblogs.com/iRedBean/p/7398272.html 先考虑dp求01串的不同子序列的个数. dp[i][j]表示用前i个字符组成的以j为结尾的01串个数. 如果第i个字符为0,则dp[i][0] = dp[i-1][1] + dp[i-1][0] + 1,dp[i][1] = dp[i-1][1] 如果第i个字符为1,则dp[i][1

HDU 4565 So Easy! 矩阵快速幂 + 共轭数

题意:中文题 So Easy 解题思路: 这题应该是 HDU 2256的原题 , 根据类似的结论可以推出 中间矩阵 ta  1 tb ta 原矩阵 1 1 解题代码: 1 // File Name: temp.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月17日 星期三 11时35分45秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #inc

hdu 5015 233 Matrix (矩阵快速幂)

题意: 有一种矩阵,它的第一行是这样一些数:a  0,0 = 0, a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333... 除此之外,在这个矩阵里, 我们有 a i,j = a i-1,j +a i,j-1( i,j ≠ 0).现在给你 a 1,0,a 2,0,...,a n,0, 你能告诉我a n,m 是多少吗? n,m(n ≤ 10,m ≤ 10 9)输出 a n,m mod 10000007. 思路:首先我们观察n和m的取值范围,会发现n非常小而m却非常大,如果