BZOJ 3231: [Sdoi2008]遞歸數列 (JZYZOJ 1353) 矩陣快速冪

http://www.lydsy.com/JudgeOnline/problem.php?id=3231
和斐波那契一個道理在最后加一個求和即可
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 //using namespace std;
 5 const int maxn=10010;
 6 const double eps=1e-8;
 7 long long modn;
 8 long long n,l,r;
 9 long long b[20]={};
10 struct mat{
11     long long e[20][20];
12     mat(){ memset(e,0,sizeof(e)); }
13 };
14 mat a;
15 mat Mul(mat x,mat y){
16     mat z;
17     for(int i=1;i<=n+1;i++){
18         for(int j=1;j<=n+1;j++){
19             for(int k=1;k<=n+1;k++){
20                 z.e[i][j]+=x.e[i][k]*y.e[k][j];
21                 z.e[i][j]%=modn;
22             }
23         }
24     }
25     return z;
26 }
27 mat Pow(mat x,long long k){
28     mat z;
29     for(int i=1;i<=n+1;i++){
30         z.e[i][i]=1;
31     }
32     while(k>0){
33         if(k&1){
34             z=Mul(z,x);
35         }
36         x=Mul(x,x);
37         k/=2;
38     }/*for(int i=1;i<=n;i++){
39         for(int j=1;j<=n;j++){
40             std::cout<<z.e[i][j]<<' ';
41         }
42         std::cout<<std::endl;
43     }*/
44     return z;
45 }
46 long long doit(long long x){
47     if(x<n){
48         return b[x+1];
49     }
50     mat z=Pow(a,x-n+1);
51     long long ans=0,s=0,d=0;
52     for(int i=1;i<=n+1;i++){
53         d+=z.e[n][i]*b[i];
54         s+=z.e[n+1][i]*b[i];
55         d%=modn;s%=modn;
56     }
57     ans=(s+d)%modn;
58     ans%=modn;
59     return ans;
60 }
61 int main(){
62     scanf("%lld",&n);
63     n+=1;
64     for(int i=2;i<=n;i++){
65         scanf("%lld",&b[i]);
66         b[n+1]+=b[i];
67     }
68     b[n+1]-=b[n];
69     for(int i=n;i>1;i--){
70         scanf("%lld",&a.e[n][i]);
71     }
72     long long l,r;
73     scanf("%lld%lld%lld",&l,&r,&modn);
74     for(int i=2;i<=n;i++){
75         b[i]%=modn;
76         a.e[i-1][i]=1;a.e[n][i]%=modn;
77     }
78     a.e[n+1][n+1]=1,a.e[n+1][n]=1;
79     /*for(int i=1;i<=n+1;i++){
80         for(int j=1;j<=n+1;j++){
81             std::cout<<a.e[i][j]<<' ';
82         }
83         std::cout<<std::endl;
84     }*/
85     long long ans=(doit(r)-doit(l-1)+modn)%modn;
86     printf("%lld\n",ans);
87     return 0;
88 }
View Code

?

轉載于:https://www.cnblogs.com/137shoebills/p/7786497.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/281925.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/281925.shtml
英文地址,請注明出處:http://en.pswp.cn/news/281925.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

馬斯克的火箭上天了,SpaceX開源項目也登上了熱榜!

python知識手冊SpaceX于美國東部時間5月30日下午3&#xff1a;22分將兩位美國宇航員送往國際空間站&#xff0c;雖然這只是Demo任務&#xff0c;但SpaceX已經以其卓越工程優勢、低廉的發射成本贏得了全球航天產業的信賴。同時也是除美俄中這些航天國家隊以外&#xff0c;唯一獨…

EasyMock學習筆記

目前在接觸平臺側的開發&#xff0c;發現平臺側的東西和以前javacard開發很不一樣&#xff0c;看來以后要學的東西還有很多很多。今天接觸了下EasyMock。 Mock 方法是單元測試中常見的一種技術&#xff0c;它的主要作用是模擬一些在應用中不容易構造或者比較復雜的對象&#xf…

app啟動廣告頁的實現,解決了廣告圖片要實時更新的問題

網上很多的實現方法很多都是顯示第一次的緩存的圖片&#xff0c;這樣就造成后臺更新廣告圖片App不能實時展示的問題。 我的具體實現思路是&#xff1a; 1.啟動時先獲取啟動頁的圖片全屏展示。 2.設計一個等待時間&#xff0c;如果超過等待時間還沒拿到圖片就把獲取的啟動頁去掉…

vue中點擊插入html_Vue中插入HTML代碼的方法

我們需要吧Hello World插入到My name is Pjee應該如何做&#xff1f;一、使用v-htmlv-html:更新元素的 innerHTMLconst text Hello World>My name is Pjee注意&#xff1a;你的站點上動態渲染的任意 HTML 可能會非常危險&#xff0c;因為它很容易導致 XSS 攻擊。請只對可信…

進程共享變量#pragma data_seg用法

#pragma data_seg介紹用#pragma data_seg建立一個新的數據段并定義共享數據&#xff0c;其具體格式為&#xff1a;   #pragma data_seg &#xff08;"shareddata")   HWND sharedwndNULL;//共享數據   #pragma data_seg() ---------------------------------…

機器視覺Halcon教程(1.介紹)

前言本期教程主要教大家如何使用Halcon機器視覺&#xff0c;通過使用Halcon, 我們可以實現一些機器視覺的應用開發。例如: OCR識別、視覺定位、缺陷檢測等內容。什么是halcon&#xff1f;簡單來說, Halcon就是一款應用于機器視覺的軟件&#xff0c;它提供了一套開發工具&#x…

網絡時間的那些事及 ntpq 詳解

2019獨角獸企業重金招聘Python工程師標準>>> GMT (Greenwich Mean Time)格林威治時間 UTC (Coordinated Universal Time) 協調世界時 IAT (International Atomic Time),TAI 國際原子時 CST (Chinese Standard Time), 北京時間Gentoo&#xff08;也許其他發行版也是&…

【前端芝士樹】Javascript的原型與原型鏈

【前端芝士樹】Javascript的原型、原型鏈以及繼承機制 前端的面試中經常會遇到這個問題&#xff0c;自己也是一直似懂非懂&#xff0c;趁這個機會整理一下0. 為什么會出現原型和原型鏈的概念 1994年&#xff0c;網景公司&#xff08;Netscape&#xff09;發布了Navigator瀏覽器…

神奇的幻方2015提高組d1t1

題目描述 幻方是一種很神奇的N*N矩陣&#xff1a;它由數字1,2,3,……,N*N構成&#xff0c;且每行、每列及兩條對角線上的數字之和都相同。 當N為奇數時&#xff0c;我們可以通過以下方法構建一個幻方&#xff1a; 首先將1寫在第一行的中間。 之后&#xff0c;按如下方式從小到大…

goldengate mysql_使用GoldenGate實現MySQL到Oracle的數據實時同步

step 1: 配置mysql修改配置文件my.ini#for goldengatelog-bin "C:/mysql/logbin/logbin.log"binlog-format ROWlog-bin-index "C:\mysql\logindex"binlog_cache_size32mmax_binlog_cache_size512mmax_binlog_size512m添加數據庫用戶ggs&#xff0c;具有…

C# 反射之Activator用法舉例

概述程序運行時&#xff0c;通過反射可以得到其它程序集或者自己程序集代碼的各種信息&#xff0c;包括類、函數、變量等來實例化它們&#xff0c;執行它們&#xff0c;操作它們&#xff0c;實際上就是獲取程序在內存中的映像&#xff0c;然后基于這個映像進行各種操作。Activa…

MyBatis批量插入

轉載于:https://blog.51cto.com/12701034/1929672

狐貍文│區塊鏈發展的正路

&#xff08;圖片出自網絡&#xff0c;版權歸原作者所有&#xff09;最近看了一本書&#xff1a;《美國增長的起落》。這本書是大部頭&#xff0c;但看起來很過癮。通過對這本書的閱讀&#xff0c;我更新了自己對區塊鏈發展的理解。這一年&#xff0c;“區塊鏈”很熱&#xff0…

mysql 一主一備_Mysql一個主一備

Mysql主從復制 -- 一主一備主從復制原理&#xff1a;Mysql的主從復制是mysql本身自帶的一個功能&#xff0c;不需要額外的第三方軟件可以實現&#xff0c;其復制功能并不是copy文件實現的&#xff0c;而是借助binlog日志文件里面的SQL命令實現的主從復制&#xff0c;可以理解為…

解決安裝Weblogic domain卡住問題(Primeton BPS)

這兩天一直有一個問題困擾我&#xff0c;在suse10weblogic(920,923,100,103)上安裝bpm產品失敗。有些版本是創建domain的時候卡在create security information上&#xff0c;有些版本卡在安裝包start weblogic上。但是在winXPweblogic10.3bpm安裝成功。 經過幾番GOOGLE,終于找到…

cocos2d-js 熱更新具體解釋(一)

本文將會具體解說cocos2d-js下的熱更新機制。這篇內容先給大家介紹一下兩個manifest文件就當熱身了。首先介紹project.manifest&#xff1a; 舉個樣例 {"packageUrl" : "http://192.168.1.108/games/dragon_gold","remoteManifestUrl" : "…

Qt之水平/垂直布局(QBoxLayout、QHBoxLayout、QVBoxLayout)

簡述 QBoxLayout可以在水平方向或垂直方向上排列控件&#xff0c;由QHBoxLayout、QVBoxLayout所繼承。 QHBoxLayout&#xff1a;水平布局&#xff0c;在水平方向上排列控件&#xff0c;即&#xff1a;左右排列。 QVBoxLayout&#xff1a;垂直布局&#xff0c;在垂直方向上排列控…

Optaplanner終于支持多線程并行運行 - Multithreaded incremental solving

Optaplanner 7.9.0.Final之前&#xff0c;啟動引擎開始對一個Problem進行規劃的時候&#xff0c;只能是單線程進行的。也就是說&#xff0c;當引擎對每一個possible solution進行分數計算的過程中&#xff0c;細化到每個步驟(Caculation)&#xff0c;都只能排隊在同一個線程中依…

python棋盤格_干貨必看 | Python的turtle庫之經典棋盤格

國際棋盤格是一個由9橫9縱的線組成的格子正方形&#xff0c;用Python的turtle庫進行繪制的時候&#xff0c;先做9橫9縱的線&#xff0c;再填上灰色小正方形&#xff0c;這就可以完成一個棋盤格了&#xff0c;下面是具體的操作步驟。(一)整體代碼1、import turtleimport turtle2…

一位技術老人給.NET初學者的一些建議

.NET平臺應用領域眾多&#xff0c;隨著這些年的不斷更新迭代&#xff0c;日趨臻善&#xff0c;也受到越來越多的開發者青睞。自從2000 年6 月22 日 微軟推出Microsoft.NET 戰略 &#xff0c;至今已有22載&#xff0c;這些年新技術&#xff0c;新框架層出不窮&#xff0c;目不暇…