題目描述

小可可參觀科學博物館時，看到一件藏品，上面有密密麻麻的數字，如下所示： 1 2 3 5 8 13 21 34 55 89 144 ... 4 7 11 18 29 47 76 123 199 322 521 ... 6 10 16 26 42 63 110 178 288 466 754 ... 9 15 24 39 63 102 165 267 432 699 1131 ... 12 20 32 52 84 136 220 356 576 932 1508 ... 14 23 37 60 97 157 254 411 665 1076 1741 ... 17 28 45 73 118 191 309 500 809 1309 2118 ... 19 31 50 81 131 212 343 555 898 1453 2351 ... 22 36 58 94 152 246 398 644 1042 1686 2728 ... 25 41 66 107 173 280 453 733 1186 1919 3105 ... 27 44 71 115 186 301 487 788 1275 2063 3338 ... ... 仔細一分析，發現還挺有規律。 原來，第一行是Fibonacci數列。即，該行中除了第一個和第二個數分別為1和2之外，其他數都是其左側相鄰的兩個數之和。 其后各行也類似于Fibonacci數列。只是第i行的第一個數是前 行中未出現的最小正整數，而其第二個數與該行第一個數以及所在行的編號相關，即A[i,2]=A[i,1]*2-(i-1) 。如在第一行中未出現的最小正整數為4，前三行中未出現的最小正整數為9。故第二行以4和7開頭，而第四行以9和15開頭。 小可可高興地把這個發現告訴了爺爺。爺爺問道：你能否一口報出第i行、第j列的那個數對m取模的結果是多少呢？ 聰明的小可可通過心算就能知道答案。你是否能編寫程序求解呢？

輸入

每行有三個分別用一個空格隔開的正整數，分別是i、j和m。其中，i, j<=1000000000 ，2<=m<=10000 。

輸出

每行輸出對應的第i行、第j列的那個正整數對m取模的結果。

樣例輸入

1 2 99

樣例輸出

2

【分析】

這題賊強啊，想了好久還是沒搞出來啊。最原始的想法顯然是直接搞出第一項啊。顯然是可以用暴力的。但是數據量太大了，數組肯定是開不了的。所以直接放棄了。然后就是找規律了。按照上面給的一個表，可以很明顯的發現，如果只看首項的話，顯然有每兩行之間的差值是2或者3，然后我就寫了一發暴力程序，弄出了前面兩百項，however，雖然都是2和3，但是2，3出現的毫無規律，如果說有的話，可能就是3比2多（-_-!）。然后就沒辦法了，只有問大佬怎么搞得，終于學到了。說是什么斐波那契最小拆分。果然強啊。

首先，對于第i行來說，你用fibonacci數列里面的數來表示i-1，轉換成二進制，然后在后面加上兩個數0，1。然后對應到fibonacci里面去求和。就得到了首項。舉個栗子：

對于第5行來說，你先弄出i-1，也就是4，4用fibonacci數列來表示就是101（也就是1+3），然后加上01，變成10101（也就是1+3+8=12），所以第五行第一列就是12。

雖然我也不知道為啥。

然后剩下的事就是矩陣快速冪的事了。輕松水過。

【代碼】

#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> #include<sstream> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS_1(a) memset(a,-1,sizeof(a)) #define MSinf(a) memset(a,0x3f,sizeof(a)) #define sin1(a) scanf("%d",&(a)) #define sin2(a,b) scanf("%d%d",&(a),&(b)) #define sin3(a,b,c) scanf("%d%d",&(a),&(b),&(c)) #define sll1(a) scanf("%lld",&(a)) #define sll2(a,b) scanf("%lld%lld",&(a),&(b)) #define sll3(a,b,c) scanf("%lld%lld%lld",&(a),&(b),&(c)) #define sdo1(a) scanf("%lf",&(a)) #define sdo2(a,b) scanf("%lf%lf",&(a),&(b)) #define sdo3(a,b,c) scanf("%lf%lf%lf",&(a),&(b),&(c)) #define pin1(a) printf("%d",(a)) #define pin2(a,b) printf("%d%d",(a),(b)) #define pin3(a,b,c) printf("%d%d%d",(a),(b),(c)) #define pll1(a) printf("%lld",(a)) #define pll2(a,b) printf("%lld%lld",(a),(b)) #define pll3(a,b,c) printf("%lld%lld%lld",(a),(b),(c)) #define pdo1(a) printf("%f",(a)) #define pdo2(a,b) printf("%f%f",(a),(b)) #define pdo3(a,b,c) printf("%f%f%f",(a),(b),(c)) #define huiche puts("") #define inf 0x3f3f3f3f //#define lson i<<1,l,mid //#define rson ((i<<1)|1),mid+1,r #define uint unsigned int typedef pair<int,int> PII; #define A first #define B second #define pb push_back #define MK make_pair #define ll long long template<typename T> void read1(T &m) {T x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}m = x*f; } template<typename T> void read2(T &a,T &b) {read1(a);read1(b); } template<typename T> void read3(T &a,T &b,T &c) {read1(a);read1(b);read1(c); } template<typename T> void out(T a) {if(a>9) out(a/10);putchar(a%10+'0'); } template<typename T> void outn(T a) {if(a>9) out(a/10);putchar(a%10+'0');puts(""); } ///------------------------------------------------------------------------------------------------------------------ long long fbonacci[50]; long long mod; void init(void) {long long last = 0;long long now = 1;rep0(i,0,50) {fbonacci[i]=now;int t = now;now+=last;last = t;} } long long get(long long ind) {long long ret =1;rep_1(i,49,0){if(ind>=fbonacci[i]){ret += fbonacci[i+2];ret%=mod;ind-=fbonacci[i];}}return ret; } struct juzhen {int m[2][2]; }; juzhen mul(juzhen a,juzhen b) {juzhen c;MS0(c.m);rep0(i,0,2)rep0(j,0,2)rep0(k,0,2){c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[j][k])%mod;}return c; } juzhen my_pow(juzhen a,long long b) {juzhen c;rep0(i,0,2)rep0(j,0,2)c.m[i][j]=(i==j);while(b){if(b&1)c = mul(c,a);a = mul(a,a);b>>=1;}return c; } int main() { // freopen("in.txt","r",stdin);init();long long i,j;while(sll3(i,j,mod)!=EOF){long long f1 = get(i-1);long long f2 = (f1*2-i+1)%mod;if(j==1){pll1(f1);huiche;continue;}if(j==2){pll1(f2);huiche;continue;}juzhen a;rep0(i,0,2) rep0(j,0,2) a.m[i][j]=1;a.m[1][1]=0;a = my_pow(a,j-2);printf("%lld\n",(a.m[0][0]*f2+a.m[0][1]*f1)%mod);}return 0; }

總結

以上是生活随笔為你收集整理的数字迷阵的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。