题意:给你一个斐波那契数列,问用其中k个数字最小的组不成的数字是几php
解题思路:多写几个后能够发现规律,斐波那契数列为0 1 1 2 3 5 8 13 21 34 55 89...k=1时答案是4,k=2时答案是12,k=3时答案是33,因此答案是第5.7.9.11....项-1ios
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #include <map> #include <cmath> #include <set> #include <stack> #include <queue> #include <vector> #include <bitset> #include <functional> using namespace std; #define LL long long const int INF = 0x3f3f3f3f; const LL mod=998244353; struct Matrix { LL v[5][5]; Matrix() { memset(v,0,sizeof v); } } dan; Matrix mul(Matrix a,Matrix b,int d) { Matrix ans; for(int i=0; i<d; i++) { for(int j=0; j<d; j++) { for(int k=0; k<d; k++) { ans.v[i][j]+=(a.v[i][k]*b.v[k][j])%mod; ans.v[i][j]%=mod; } } } return ans; } Matrix pow(Matrix a,int k,int d) { Matrix ans=dan; while(k) { if(k&1) ans=mul(ans,a,d); k>>=1; a=mul(a,a,d); } return ans; } int main() { int k; while(~scanf("%d",&k)) { dan.v[0][0]=1,dan.v[0][1]=0; Matrix a; a.v[0][0]=a.v[0][1]=a.v[1][0]=1,a.v[1][1]=0; Matrix ans= pow(a,2*k+2,2); printf("%lld\n",((ans.v[0][0]-1)%mod+mod)%mod); } return 0; }