程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> FZU 1692 Key problem(構造矩陣+矩陣快速冪)

FZU 1692 Key problem(構造矩陣+矩陣快速冪)

編輯:C++入門知識

FZU 1692 Key problem(構造矩陣+矩陣快速冪)


 

【題意】:1 題目的意思是有n個人構成一個圈,每個人初始的有ai個蘋果,現在做m次的游戲,每一次游戲過後第i個人能夠增加R*A(i+n-1)%n+L*A(i+1)%n 個蘋果(題目有錯),問m輪游戲過後每個人的蘋果數

【思路】:

 

根據題目的意思我們能夠列出一輪過後每個人的蘋果數

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)

代碼:

 

/*
Problem id. FZU 1692
RunID: 631373
UserID: ACM_herongwei
Submit time: 2015-09-04 11:58:16
Language: C++
Length: 1806 Bytes.
Result: Accepted
*/

#include 
#include 
#include 
#include 
using namespace std;

typedef long long LL;
const int N=105;

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

struct mut
{
    LL mat[N][N];
    mut()
    {
        memset(mat,0,sizeof(mat));
    }
    void init()
    {
        for(int i=0; i>=1;
    }
    return unit;
}

void solve()
{
    int ans=0;
    mut unit,a;
    scanf(%d %d %d %d %d,&n,&m,&R,&L,&MOD);
    for(int i=0; i

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved