FZU 1692 Key problem

点击打开FZU 1692

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

分析:

1 题目的意思是有n个人构成一个圈,每个人初始的有ai个苹果,现在做m次的游戏,每一次游戏过后第i个人能够增加R*A(i+n-1)%n+L*A(i+1)%n 个苹果(题目有错),问m轮游戏过后每个人的苹果数

2 根据题目的意思我们能够列出一轮过后每个人的苹果数

   a0 = a0+R*an-1+L*a1

   a1 = a1+R*a0+L*a2

   .............................

   an-1 = an-1+R*an-2+L*a0

3 根据第二条思路我们可以构造出如下的矩阵

   1 L 0 ...... R        a0         a0'

   R 1 L .........  *     a1         a1'

   ...................       ....      = ......

   ...........R 1 L      an-2       an-2'

   L ...........R 1      an-1       an-1'

4 那么根据3我们可以利用矩阵快速幂求出最后的答案,但是题目的n最大为100,m最大为10^9,那么每个case的时间复杂度为O(Logm*n^3),当n最大为100的时候是会TLE的

5 我们发现初始的矩阵里面,矩阵是一个循环同构的,就是说矩阵的每一行度能够从上一行推出,那么我们只要利用O(n^2)的时间求出第一行,然后我们在利用递推求出剩下的n-1行,那么总的时间复杂度为O(Logm*n^2)

代码:

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

typedef __int64 int64;
const int N = 110;

int arr[N];
int n , m , L , R , MOD;

struct Matrix{
    int64 mat[N][N];
    Matrix operator*(const Matrix& ma)const{
        Matrix tmp;
        for(int i = 0 ; i < n ; i++){
            tmp.mat[0][i] = 0;
            for(int j = 0 ; j < n ; j++)
                tmp.mat[0][i] += mat[0][j]*ma.mat[j][i]%MOD;
            tmp.mat[0][i] %= MOD;
        }
        for(int i = 1 ; i < n ; i++)
            for(int j = 0 ; j < n ; j++)
                tmp.mat[i][j] = tmp.mat[i-1][(j-1+n)%n];
        return tmp;
    }
};

void init(Matrix &ma){
    memset(ma.mat , 0 , sizeof(ma.mat));
    ma.mat[0][1] = L ; ma.mat[0][n-1] = R;
    ma.mat[n-1][0] = L ; ma.mat[n-1][n-2] = R;
    ma.mat[0][0] = ma.mat[n-1][n-1] = 1;
    for(int i = 1 ; i < n-1 ; i++){
        ma.mat[i][i-1] = R;
        ma.mat[i][i+1] = L;
        ma.mat[i][i] = 1;
    }
}

void Pow(Matrix &ma){
    Matrix ans;
    memset(ans.mat , 0 , sizeof(ans.mat));
    for(int i = 0 ; i < n ; i++)
        ans.mat[i][i] = 1;
    while(m){
        if(m&1)
            ans = ans*ma;
        m >>= 1;
        ma = ma*ma;
    }
    for(int i = 0 ; i < n ; i++){
        int64 sum = 0;
        for(int j = 0 ; j < n ; j++)
            sum += ans.mat[i][j]*arr[j]%MOD;
        if(i) printf(" ");
        printf("%I64d" , sum%MOD);
    }
    puts("");
}

int main(){
    int cas;
    Matrix ma;
    scanf("%d" , &cas);
    while(cas--){
        scanf("%d%d%d" , &n , &m , &L);
        scanf("%d%d" , &R , &MOD);
        for(int i = 0 ; i < n ; i++)
            scanf("%d" , &arr[i]);
        init(ma);
        Pow(ma);
    }
    return 0;
}


时间: 2013-08-30
Tags: void

FZU 1692 Key problem的相关文章

矩阵快速幂专题【完结】

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

FZU 1752 a^b%c

题目连接:http://acm.fzu.edu.cn/problem.php?pid=1752 解题思路:要用快速幂,但不是单纯的用,如果单纯的用的话就会爆掉,要把乘法转化为加法,然后再用而且尽量用位运算... 上代码: #include <iostream> #include <cstdio> using namespace std; typedef long long LL; LL multi(LL a, LL b, LL c) { LL ans=0; a=a%c; while

acm问题-FOJ 2126问题解法思路

问题描述 FOJ 2126问题解法思路 福大oj上的一道题目 http://acm.fzu.edu.cn/problem.php?pid=2126 那位大神帮忙看下,给个解题思路?? (当然能有伪代码或代码就更好了!!)

Foj 1075 分解素因子

题目链接:http://acm.fzu.edu.cn/problem.php?pid=1075 思路:分解素因子 #include <iostream> #include <cstring> #include <cstdio> using namespace std; const int maxn=65535+5; typedef long long LL; bool prime[maxn]; int p[maxn/10]; int k; void isprime()

The Log

The Log: What every software engineer should know about real-time data's unifying abstraction 译文 Jay Kreps Principal Staff Engineer Posted on 12/16/2013 I joined LinkedIn about six years ago at a particularly interesting time. We were just beginning

The Log: What every software engineer should know about real-time data&#039;s unifying abstraction

主要的思想,  将所有的系统都可以看作两部分,真正的数据log系统和各种各样的query engine  所有的一致性由log系统来保证,其他各种query engine不需要考虑一致性,安全性,只需要不停的从log系统来同步数据,如果数据丢失或crash可以从log系统replay来恢复  可以看出kafka系统在linkedin中的重要地位,不光是data aggregation,而是整个系统的核心 Part One: What Is a Log? log定义 很简单的结构,最关键的属性是,

SpringMVC源码总结(一)HandlerMapping和HandlerAdapter入门

刚接触SpringMVC,对它的xml文件配置一直比较模模糊糊,最近花了一点时间稍微看了下源代码,再加上调试,开始逐渐理解它,网上的类似的内容有很多,写本文主要是自己加深一下理解.本文适合用过SpringMVC的开发者,言归正传,首先搭建一个最简单的工程体验一下.  该工程是基于maven的,pom配置不再说明,所使用的spring版本4.0.5.  首先是web.xml文件配置,最简单的配置  ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 <!DOCT

SQL Server中关于基数估计如何计算预估行数的一些探讨

   关于SQL Server 2014中的基数估计,官方文档Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator里有大量细节介绍,但是全部是英文,估计也没有几个人仔细阅读.那么SQL Server 2014中基数估计的预估行数到底是怎么计算的呢? 有哪一些规律呢?我们下面通过一些例子来初略了解一下,下面测试案例仅供参考,如有不足或肤浅的地方,敬请指教!   下面实验测试的环境主要为SQL Serve

【故障处理】队列等待之enq: TX - row lock contention

[故障处理]队列等待之enq: TX - row lock contention 1  BLOG文档结构图   2  前言部分 2.1  导读和注意事项 各位技术爱好者,看完本文后,你可以掌握如下的技能,也可以学到一些其它你所不知道的知识,~O(∩_∩)O~: ① enq: TX - row lock contention等待事件的解决 ② 一般等待事件的解决办法 ③ 队列等待的基本知识 ④ ADDM的使用 ⑤ 如何获取历史执行计划 ⑥ 查询绑定变量的具体值 ⑦ 很多有用的查询性能的SQL语句