`

HDU 3306 Another kind of Fibonacci

阅读更多
/*
*  [题意]
*   已知:
*       F(0)=1, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)
*       A(0)=1, A(1)=1, A(n)=X*A(n-1)+Y*A(n-2) (n>=2)
*   求:S(n), S(n) = (A(0)^2)+(A(1)^2)+...+(A(n)^2)
*  [解题方法]
*   (A(n)^2) = (X*A(n-1) + Y*A(n-2))^2
*            = X*X*(A(n-1)^2) + Y*Y*(A(n-2)^2) + 2*X*Y*(A(n-1)*A(n-2))
*   A(n)*A(n-1) = (X*A(n-1) + Y*A(n-2)) * A(n-1)
*               = X*(A(n-1)^2) + Y*(A(n-1)*A(n-2))
*   S(n) = S(n-1) + A(n)^2
*   所以可以构造矩阵:
*   |1  1   0   0       |       |   S(n-1)      |       |   S(n)    |
*   |0  X*X Y*Y 2*X*Y   |   *   |   (A(n-1)^2)  |   =   |(A(n)^2)   |
*   |0  1   0   0       |       |   (A(n-2)^2)  |       |(A(n-1)^2) |
*   |0  X   0   Y       |       | A(n-1)*A(n-2) |       |A(n)*A(n-1)|
*/
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define FF(i, n) for(int i = 0; i < n; i++)
#define M 4

int ans[M], mod = 10007;
int ret[M][M];
int init[M][M];
int ss[M][M] = {1, 1, 0, 0,
                0, 0, 0, 0,
                0, 1, 0, 0,
                0, 0, 0, 0};

void ini(int n)
{
    FF(i, n) FF(j, n) init[i][j] = ss[i][j];
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void matmul(int a[], int b[][M], int n)
{
    int tp[M] = {0};
    FF(j, n) if(a[j]) FF(i, n) if(b[i][j])
        tp[i] = (tp[i] + b[i][j]*a[j]) % mod;
    FF(i, n) a[i] = tp[i];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for ( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int main()
{
    int n, x, y;
    while (cin >> n >> x >> y)
    {
        FF(i, M) ans[i] = 1;
        ini(M);
        init[1][1] = (x%mod)*(x%mod) % mod;
        init[1][2] = (y%mod)*(y%mod) % mod;
        init[1][3] = (x%mod)*(y%mod) % mod * 2 % mod;
        init[3][1] = x % mod;
        init[3][3] = y % mod;
        qmod(M, n);
        matmul(ans, ret, M);
        cout << ans[0] << endl;
    }
    return 0;
}

 

1
0
分享到:
评论

相关推荐

    HDU_2010.rar_hdu 2010_hdu 20_hdu acm20

    【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...

    hdu.rar_hdu

    HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...

    HDU题目java实现

    【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...

    hdu1250高精度加法

    ### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...

    HDU DP动态规划

    例如,一个简单的动态规划问题可以是“斐波那契数列”,其中状态通常定义为第n个斐波那契数,状态转移方程为F(n) = F(n-1) + F(n-2),初始条件为F(0) = 0,F(1) = 1。 在HDU的DP题目中,可能会有各种复杂度的题目,...

    HDU图论题目分类

    HDU图论题目分类 HDU图论题目分类是指在杭州电子科技大学(Hangzhou Dianzi University)的判题平台HDU OJ(Online Judge)上收录的一系列图论题目的分类。本分类涵盖了图论领域的多种类型的题目,涉及到图论的基本...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

    HDU1059的代码

    HDU1059的代码

    hdu1001解题报告

    hdu1001解题报告

    hdu 1574 passed sorce

    hdu 1574 passed sorce

    hdu2101解决方案

    hdu2101AC代码

    ACM HDU

    【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu 5007 Post Robot

    hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。

    Hdu1000—2169部分代码

    HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...

    HDU acm-PPT课件

    【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...

    hdu acm1166线段树

    hdu 1166线段树代码

    HDU1019(2028)解题报告

    The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...

    HDU最全ac代码

    HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...

Global site tag (gtag.js) - Google Analytics