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

第一题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)

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

看着很简单，就是a不了

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

第二题快速幂都只能9%

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

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

求答案

定点射门 dp？

有a出来的吗😂

只会将直线a坐标处的足球踢到另一条直线的a坐标处。不是只有一条直线吗？一条直线上有多个球门区域，哪里来的另一条直线的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; }

a不了，好气

第二题只能ac9

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

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