百度笔试 定点射门，跳跃递推的编程题有讨论的吗

第一题36，第二题9

求的是球门。。。

//// 9 % #include <cstdio> #include <iostream> using namespace std; const long long mod = 1e9 + 7; long long a, b, c, d, n; struct Mat {   long long a[4][4];   Mat() {     for(int i = 0; i < 4; i++)       for(int j = 0; j < 4; j++) a[i][j] = 0LL;   }   void I() {     a[0][0] = a[1][1] = a[2][2] = a[3][3] = 1LL;   } }; Mat operator*(const Mat& a, const Mat& b) {   Mat ret;   for(int i = 0; i < 4; i++) {     for(int j = 0; j < 4; j++) {       for(int k = 0; k < 4; k++) {         ret.a[i][j] += (a.a[i][k] * b.a[k][j]) % mod;         ret.a[i][j] %= mod;       }     }   }   return ret; } Mat quick_pow(Mat a, long long b) {   Mat ret;   ret.I();   while(b > 0) {     if (b&1) ret = ret * a;     a = a * a;     b >>= 1;   }   return ret; } int main() {   Mat M;   M.a[0][3] = 1;   M.a[1][0] = 1; M.a[1][3] = 1;   M.a[2][1] = 1; M.a[2][3] = 0;   M.a[3][2] = 1; M.a[3][3] = 1;   cin >> a >> b >> c >> d >> n;   a %= mod; b %= mod; c %= mod; d %= mod;   long long ans = -1;   if(n == 1) {     ans = a;   }   else if(n == 2) {     ans = b;   }   else if(n == 3) {     ans = c;   }   else if(n == 4) {     ans = d;   }   else {     Mat x;     x = quick_pow(M, n-4);     ans = 0LL;     ans += (a * x.a[0][3]) % mod; ans %= mod;     ans += (b * x.a[1][3]) % mod; ans %= mod;     ans += (c * x.a[2][3]) % mod; ans %= mod;     ans += (d * x.a[3][3]) % mod; ans %= mod;   }   cout << ans % mod << endl; }

这样算不算是O(1)的解 from sympy import Symbol,solve [a,b,c,d,n] = list(map(int,input().split())) MOD = 10**9+7 x = Symbol('x') [x1,x2,x3,x4] = solve(x**4-x**3-x-1,x) q = Symbol('q') w = Symbol('w') e = Symbol('e') r = Symbol('r') d = solve([-a+q*x1+w*x2+e*x3+r*x4,-b+q*(x1**2)+w*(x2**2)+e*(x3**2)+r*(x4**2),        -c+q*(x1**3)+w*(x2**3)+e*(x3**3)+r*(x4**3),-d+q*(x1**4)+w*(x2**4)+e*(x3**4)+r*(x4**4)],[q,w,e,r]) print(int(d[q]*(x1**n)+d[w]*(x2**n)+d[e]*(x3**n)+d[r]*(x4**n))%MOD)

第一题要转化成二分图匹配

第二题算通项公式，但是这个四次方程也太难解了吧

第二题快速幂都只能9%

所以第二题是一定要解出通项公式的O(1)才行么？我用矩阵乘的方法也就9

看着很简单，就是a不了

看起来很简单，就是AC不了

第一题二分图最大匹配，第二题矩阵快速幂，但是第二题感觉题目有问题

快速幂报错是wa不是tle啊，输入输出有问题吧

第二题不知道为啥快速幂就过了9，但肯定不是求通项，求通项要算特征根，带根号，取模会有问题

第一题误导人，我佛了，没仔细看以为是超时没能AC，优化了半天发现是答案错了

跳跃这道题绝壁有问题，百度也太不专业了吧。。。我从后往前做的，心态崩了

我以为我没读懂出题人的意思

我是先把球门区间合并，然后统计得分就可以了

两题9%...都超时 哭泣

a不了，好气

#include<algorithm> #include<vector> #include<iostream> #include<cstring> #include<cstdio> typedef long long LL; using namespace std; long long a[1000]; const LL mod = 1000000007; int main() {     int n;     memset(a, 0, sizeof(a));     for (int i = 1; i <= 4; i++) {         cin >> a[i];     }     cin >> n;     for (int i = 5; i <= n+5; i++) {         a[i] = a[i-1] + a[i-2] + a[i-3] + a[i-4];         cout <<"第"<<i<<"项： "<< a[i] << endl;     }     LL tm = a[n]%mod;     cout <<tm<< endl;     system("pause");     return 0; }