首页 > 试题广场 >

小强爱数学

[编程题]小强爱数学
  • 热度指数：5958 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
小强发现当已知以及时,能很轻易的算出的值.但小强想请你在已知 和的情况下,计算出的值.因为这个结果可能很大,所以所有的运算都在模1e9+7下进行.

输入描述:
第一行输入一个正整数.表示有组数据
接下来行,每行输入三个整数,和.





输出描述:
输出行,每一行表示每组数据的结果.
示例1

输入

3
4 4 3
2 3 4
5 2 6

输出

16
999999993
9009
算法知识视频讲解
添加回答
爆爆只是想帮忙头像 爆爆只是想帮忙 
#include<bits/stdc++.h>
using namespace std;
const int ll = 1000000007;

//递推公式 f[i] = A * f[i - 1] - B * f[i - 2]
//f[i] = x ^ i + y ^ i
int helper(int A, int B, int n){
    vector<long> dp(3);
    dp[0] = 2;
    dp[1] = A;
    for(int i = 2; i <= n; i++){
        dp[2] = ((A * dp[1] % ll) - (B * dp[0] % ll) + ll) % ll;
        dp[0] = dp[1];
        dp[1] = dp[2];
    }
    return dp[2];
}

int main(){
    int count;
    cin >> count;
    while(count-- > 0){
        int A, B, n;
        cin >> A >> B >> n;
        cout << helper(A, B, n) << endl;
    }
    return 0;
}
发表于 2022-03-13 16:30:33 回复(2)
牛Coding头像 牛Coding
数学问题
记 Rn = x^n + y^n, a = x + y, b = x * y
递推公式：Rn = a * Rn-1 - b * Rn-2 
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<set>
#include<string>
#include<queue>
#include<math.h>
#include<time.h>
#include<sstream>
#include<map>
#include<list>
#include<iterator>
#include<stack>
#include<thread>
using namespace std;

/*
1
2 3 4
*/
class Solution {
private:
	static const int mod = 1e9 + 7;
	int a, b, n;
	void solve() {
		long long r0 = a, r1 = (a * a % mod - 2 * b % mod + mod) % mod;
		long long r2;
		n -= 2;
		while (n) {
			r2 = (a * r1 % mod - b * r0 % mod + mod) % mod;
			r0 = r1, r1 = r2;
			--n;
		}
		cout << r1 << endl;
	}
public:
	Solution() {
		int t;
		cin >> t;
		while (t) {
			cin >> a >> b >> n;
			a %= mod, b %= mod;
			solve();
			--t;
		}
	}
};

int main() {
	Solution s;
	return 0;
}


发表于 2021-05-24 08:56:59 回复(0)
牛客576990316号头像 牛客576990316号
根据规律进行递归，也可以把结果存入数组或变量之中，后面进行更新
发表于 2021-08-04 23:26:54 回复(0)
pein531头像 pein531
题目避开了n=0的说明，其实n=0时x0+y0=2，假设f(n)=xn+yn，试两个n能够发现规律：
  • x2+y2=(x+y)2-2xy=A*(x+y)-B*2，其实就是f(2)=Af(1)-Bf(0)，接下来强行去凑这个结构
  • x3+y3=(x+y)3-3x2y-3xy2 = (x+y)*(x2+y2+2xy)-3x2y-3xy2=(x+y)(x2+y2)+2x2y+2xy2-3x2y-3xy2=A*(x2+y2)-B*(x+y)=A*f(2)-B*f(1)
到这里就可以类似斐波那契数列那么求解了，第i项依赖前面两项。但这个数据量给爷整跪了，为了避免思考数据类型溢出用了python，结果超时。然后改用java抠这个溢出的边界 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static final int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            String[] params = br.readLine().split(" ");
            int A = Integer.parseInt(params[0]);
            int B = Integer.parseInt(params[1]);
            int n = Integer.parseInt(params[2]);
            if(n == 1){
                System.out.println(A);
            }else if(n == 2){
                System.out.println(A*A - 2*B);
            }else{
                long dp1 = 2L, dp2 = (long)A, dp = 0L;
                for(int i = 2; i <= n; i++){
                    // 注意相减之后可能越界，加上个MOD防止溢出
                    dp = ((A * dp2) % MOD - (B * dp1) % MOD + MOD) % MOD;
                    dp1 = dp2;
                    dp2 = dp;
                }
                System.out.println(dp);
            }
        }
    }
}

编辑于 2021-11-23 15:09:07 回复(4)
C/C++
DeeGLMath头像 DeeGLMath 
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int t, n;
ll a, b;
ll dp[N];
int main(){
    cin >> t;
    while(t--){
        cin >> a >> b >> n;
        dp[1] = a;
        dp[2] = ((a*a)%mod - (2*b)%mod + mod)%mod;
        if(n == 1){
            cout << a << endl;
            return 0;
        }
        if (n == 2){
            cout << dp[n] << endl;
            return 0;
        }
        for(int i=3; i<=n; i++){
            dp[i] = ((a * dp[i-1])%mod - (b * dp[i-2])%mod + mod)%mod;
        }
        cout << dp[n] << endl;
    }
    return 0;
}
标准C++解法，不多比比。
发表于 2022-03-04 15:29:47 回复(0)
聪明的托尼拒绝pua头像 聪明的托尼拒绝pua 
"""
得到递归规律后，使用矩阵快速幂求解，注意python里负数的取余结果就行
"""
MOD = int(1e9+7)
 
def two_num_pow_sum(a, b, n):
    if n == 1:
        return a
    matrix=[[a, -b], [1, 0]]
    res = matrix_pow(matrix, n - 1)
    return (res[0][0] * a + res[0][1] * 2 ) % MOD
 
def matrix_pow(matrix, n):
    ans = [[1, 0], [0, 1]]
    while n > 0:
        if n & 1 != 0:
            ans = matrix_mul(ans, matrix)
        n >>= 1
        matrix = matrix_mul(matrix, matrix)
    return ans
 
def matrix_mul(ma, mb):
     
    ans = [[0] * 2 for _ in range(2)]
    for i in range(2):
        for j in range(2):
            ans[i][j] = ma[i][0] * mb[0][j] + ma[i][1] * mb[1][j]
            if ans[i][j]>=0:
                ans[i][j] %= MOD
            else:
                ans[i][j] = - (abs(ans[i][j]) % MOD)
    return ans
 
while True:
    try:
        t = int(input())
        ans = []
        for i in range(t):
            a, b, n = list(map(int, input().split()))
            ans.append(two_num_pow_sum(a, b, n))
        for num in ans:
            print(num)
    except:
        break

发表于 2022-03-12 16:09:37 回复(1)
风景旧曾谙！头像 风景旧曾谙！
没想到T*n的算法复杂度居然能过，我一看1e5就觉得得用快速幂来着 
#include <bits/stdc++.h>
using namespace std;

const int N=2;

void multi(vector<vector<long long>> &a,vector<vector<long long>> b,long long mod){
    vector<vector<long long>> tmp(2,vector<long long>(2,0));
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++){
                tmp[i][j]+=a[i][k]*b[k][j];
                tmp[i][j] = (tmp[i][j]%mod+mod)%mod;
            }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            a[i][j]=tmp[i][j];
}
 

void Pow(vector<vector<long long>> &a,int n,long long mod){
    vector<vector<long long>> res(2,vector<long long>(2,0));
    for(int i=0;i<N;i++) res[i][i]=1;
    while(n){
        if(n&1)multi(res,a,mod);
        multi(a,a,mod);
        n>>=1;
    }
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            a[i][j]=res[i][j];
}



int main(){
    int T;
    long long mod = 1e9+7;
    cin>>T;
    while(T--){
        long long A,B,n;
        cin>>A>>B>>n;
        vector<vector<long long>> a = {{A*A-B,-A*B},{A,-B}};
        
        for(int i = 0;i<2;i++)for(int j = 0;j<2;j++)
            a[i][j] = (a[i][j]%mod+mod)%mod;
        
        if(n==1){
            cout<<A<<endl;
            continue;
        }
        if(n==2){
            long long ans = (A*A-2*B);
            ans = (ans%mod+mod)%mod;
            cout<<ans<<endl;
            continue;            
        }
        long long f0 = 2;
        long long f1 = A;
        long long f2 = (A*A-2*B%mod+mod)%mod;
        
        if(n%2==0){
            int cnt = n/2-1;
            Pow(a,cnt,mod);
            long long fn = ((a[0][0]*f2)%mod+(a[0][1]*f1)%mod+mod)%mod;
            cout<<fn<<endl;
        }
        else{
            int cnt = n/2;
            Pow(a,cnt,mod);
            long long fn = ((a[0][0]*f1)%mod+(a[0][1]*f0)%mod+mod)%mod;
            cout<<fn<<endl;
        }
    }
    return 0;
}

编辑于 2022-03-04 14:07:08 回复(0)
亲切的杰尼龟顶呱呱头像 亲切的杰尼龟顶呱呱
容易出错的点：
1）用long long 类型数据做运算; 
2）数据溢出和输入是负数的情形：
if(f[i] < 0) {
            f[i] += modBase;
        }
发表于 2021-10-27 19:33:56 回复(1)
牛客474721145号头像 牛客474721145号
思路： 动态规划
转移方程：x^(n) + y^(n) = (x^(n-1) + y^(n-1))*(x+y) - x*y*(x^(n-2) + y^(n-2))，dp[n] = dp[n-1]*A + B*dp[n-2];

发表于 2021-08-09 12:06:25 回复(5)
社畜a头像 社畜a

有没有大佬告诉我，下面的代码哪里错了

#include 
#include 
using namespace std;
const int MOD=1e9+7;
int dfs(int a,int b,int c){
    vector vec;
    vec.push_back(0);
    if(c==1) return a;
    if(c==2) return ((a*a)%MOD-(2*b)%MOD+MOD)%MOD;
    vec.push_back(a);
    vec.push_back(((a*a)%MOD-(2*b)%MOD+MOD)%MOD);
    for(int i = 3;i<=c;i++){
        vec.push_back(((a*vec[i-1])%MOD-(b*vec[i-2])%MOD+MOD) % MOD);
    }
    return vec.back();
}
int main() {
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        cout<<dfs(a,b,c)<<endl;
    }
}
编辑于 2024-04-09 13:42:16 回复(0)
愉快的猕猴桃在泡池子头像 愉快的猕猴桃在泡池子 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
光想着还是得利用下快速幂，然而不知道是在哪里溢出了还是咋滴，家人们谁懂呀。。。
(x+y)(x^n+y^n) = x^{n+1} + x^n * y + x * y^n + y^{n+1}
=>  x^{n+1} + y^{n+1} = (x^n+y^n) * (x+y) - (x^{n-1} + y^{n-1}) * xy

x^{2n}+y^{2n} = {x^n + y^n}^2 - 2*(xy)^n
*/
vector<long> xy_to_n(100003,-1);
vector<long> x_plus_y_to_n(100003,-1);
long mod = 1e9+7;

long calculate_xy_to_n(int n){
    if(xy_to_n[n]!=-1)
        return xy_to_n[n];
    long tmp = calculate_xy_to_n(n>>1);
    xy_to_n[n] = tmp*tmp;
    if(n&1) // 奇数
        xy_to_n[n]*=calculate_xy_to_n(1);
    if(xy_to_n[n]>=mod)
        xy_to_n[n] %= mod;
    if(xy_to_n[n]<0)
        xy_to_n[n] += mod;
    return xy_to_n[n];
}

long calculate_x_plus_y_to_n(int n){
    if(x_plus_y_to_n[n]!=-1)
        return x_plus_y_to_n[n];
    if(n&1){ // 奇数
        x_plus_y_to_n[n] = calculate_x_plus_y_to_n(n-1)*calculate_x_plus_y_to_n(1)
                           -calculate_x_plus_y_to_n(n-2)*calculate_xy_to_n(1);
    }else{ //偶数
        x_plus_y_to_n[n] = calculate_x_plus_y_to_n(n>>1)*calculate_x_plus_y_to_n(n>>1)
                           -2*calculate_xy_to_n(n>>1);
    }
    if(x_plus_y_to_n[n]>=mod)
        x_plus_y_to_n[n]%=mod;
    if(x_plus_y_to_n[n]<0)
        x_plus_y_to_n[n]+=mod;
    return x_plus_y_to_n[n];
}

int main() {
    int T;
    cin>>T;
    for(int i=0;i<T;i++){
        long xy,x_plus_y,n;
        cin>>x_plus_y>>xy>>n;
        xy_to_n.resize(n+1);
        std::fill(xy_to_n.begin(),xy_to_n.end(),-1);
        x_plus_y_to_n.resize(n+1);
        std::fill(x_plus_y_to_n.begin(),x_plus_y_to_n.end(),-1);
        xy_to_n[1]=xy;
        x_plus_y_to_n[1] = x_plus_y;
        cout<<calculate_x_plus_y_to_n(n)<<endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 2023-05-06 14:03:53 回复(0)
牛客219521847号头像 牛客219521847号
这道题不TLE的关键是自己写 power方程，每一步都mod一次。。。。

发表于 2021-10-18 12:38:04 回复(0)
onestan头像 onestan
#include <bits/stdc++.h>
using namespace std;
#define MOD (int)(1e9+7)

int f(int a,int b,int n)
{
    vector<long long> func(3);
    func[1]=2;
    func[2]=a;
    for(int i=2;i<=n;++i)
    {
        func[0]=func[1];
        func[1]=func[2];
        func[2]=(a*func[1]-b*func[0])%MOD;
        if(func[2]<0)func[2]+=MOD;
    }
    return func[2];
}

int main()
{
    int t,a,b,n;
    cin>>t;
    for(int i=0;i<t;++i)
    {
        cin>>a>>b>>n;
        cout<<f(a,b,n)<<endl;
    }
    return 0;
}
发表于 2021-08-26 16:21:30 回复(0)
乔木少年头像 乔木少年 
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int helper(int A, int B, int n) {
    if(n == 0) {
        return 2;
    }
    if(n == 1) {
        return A;
    }
    vector<long long> dp(n + 1);
    dp[0] = 2;
    dp[1] = A;
    
    for(int i = 2; i <= n; ++i) {
        dp[i] = (((A * dp[i - 1] % mod) - (B * dp[i - 2] % mod)) + mod) % mod;
    }
    
    return dp[n];
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        int A, B, n;
        cin >> A >> B >> n;
        cout << helper(A, B, n) << endl;
    }
    return 0;
}

发表于 2021-08-11 11:46:48 回复(0)
想要进大厂的牛牛头像 想要进大厂的牛牛
#include<iostream>
#include<cstdlib>
#include<math.h>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include "string"
#include <hash_map>
#include <map>
#include <unordered_map>
#include <stack>
#include <stdio.h>
#include <queue>
#include <functional>
#include <set>
using namespace std;
const int mod = 1e9+7;
long long int XNYN(long long int A,long long int B,long long int n)
{    
    if (n == 0)
    {
        return 2;
    }
    if (n == 1)
    {
        return A;
    }
    vector<long long int> dp(n+1,0);
    dp[0] = 2;
    dp[1] = A;
    dp[2] = (A*A)%mod - (2*B)%mod;
    for (int i = 3; i <= n; i++)
    {
        dp[i] =((A*dp[i-1])%mod - (B*dp[i-2])%mod+mod) %mod;
    }
    return dp[n];
}    
int main()
{
    int cyc;
    cin>>cyc;
    vector<vector<int>> num;
    while (cyc > 0)
    {
        vector<int> tempNum;
        long long int A;
        long long int B;
        int n;
        cin >> A;
        cin >> B;
        cin >> n;
        if (cin.get() == '\n')
        {
            tempNum.push_back(A);
            tempNum.push_back(B);
            tempNum.push_back(n);
        }
        num.push_back(tempNum);
        cyc--;
    }
    for (int i = 0 ; i < num.size(); i++)
    {    
        cout<<XNYN(num[i][0],num[i][1],num[i][2])<<endl;
    }
    system("pause");
    return 0;
}
发表于 2021-08-03 14:49:55 回复(0)
牛客622467775号头像 牛客622467775号 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
class Solution{
public:
    static const int mod = 1e9 + 7;
    vector<LL>res;
    LL a, b, n;
    LL ans0, ans1, ans;
    vector<LL> calculate(vector<vector<LL>>& nums, int len) {
        for (int i = 0; i < len; i++) {
            a = nums[i][0];
            b = nums[i][1];
            n = nums[i][2];
            vector<LL>temp;
            ans0 = a % mod;
            ans1 = (a * a % mod - 2 * b % mod + mod) % mod;
            if (n == 1) {
                res.push_back(ans0);
            }
            if (n == 2) {
                res.push_back(ans1);
            }
            else {
                temp.push_back(ans0);
                temp.push_back(ans1);
                ///ans = a * ans1 - b * ans0;
                ///temp.push_back(ans);
                for (int j = 2; j < n; j++) {
                    LL now = (a * temp[j - 1] % mod - b * temp[j - 2] % mod + mod) % mod;
                    temp.push_back(now);
                }
                LL size = temp.size();
                ans = temp[size - 1];
                res.push_back(ans);
            }
        }
        return res;
    }
     
    //int backtracking(int a, int b, int n, int ans, int ans0, int ans1, int startIndex) {
    //  if (startIndex == n) { return ans; }
    //  else {
    //      ans0 = ans1;
    //      ans1 = ans;
    //      ans = ans = a * ans1 - b * ans0;
    //      backtracking(a, b, n, ans, ans0, ans1, startIndex + 1);
    //  }
    //}
};
 
 
 
int main() {
    LL n;
    LL b;
    LL t;
    vector<vector<LL>>input;
    vector<LL>output;
    cin >> n;
    t = n;
    while (--n >= 0) {
        vector<LL>temp;
        for (int i = 0; i < 3; i++) {
            cin >> b;
            temp.push_back(b);
        }
        input.push_back(temp);
    }
    Solution result;
    output = result.calculate(input, t);
    for (int j = 0; j < t; j++) {
        cout << output[j] << endl;
    }
}

发表于 2021-07-30 11:26:46 回复(0)
Python
OPPO内推码_80378832_必过头像 OPPO内推码_80378832_必过
import math
T = int(input())
for i in range(T):
    A, B, n = map(int, input().split())
    delta = A**2 - 4*B
    if delta >= 0:
        x = (A + math.sqrt(delta))/2
        ans = (x**n + (A-x)**n) % (10**9+7)
        print(int(ans))
    else:
        ans = 999999993
        ans = ans % (10**9+7)
        print(ans)

为什么这样子不行？
发表于 2021-07-27 22:39:26 回复(0)
Java
超级拉布拉多头像 超级拉布拉多 

import java.util.Scanner;

public class Main {
    static int mod = 1000000007;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int groups = sc.nextInt();
        while (groups-- >0){
            long a = sc.nextInt();
            long b=  sc.nextInt();
            int n=  sc.nextInt();
            a%=mod;
            b%=mod;
            System.out.println(new Main().solve(a,b,n));
        }
    }

    long solve(long a,long b,int n){
        
        long[] dp = new long[n+1];
        dp[0]=2;
        dp[1]=a;
        dp[2]=a*a%mod-2*b%mod;
        for(int i=3;i<=n;i++){
            dp[i] = (a*(dp[i-1])%mod-b*(dp[i-2])%mod+mod)%mod;
        }
        return dp[n];
    }
}

发表于 2021-07-02 01:29:14 回复(3)
牛客566012114号头像 牛客566012114号 
import java.util.*;

public class Main{


    /**
     * 阿里2 已知 x+y=A xy = B 求x^n+y^n
     * 递推式 xn = Axn-1 - Bxn-2
     */

    static long mod = (long)Math.pow(10,9)+7;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        for(int i=0;i<m;i++){
            long a = in.nextInt();
            long b = in.nextInt();
            int n = in.nextInt();
            a %= mod;
            b %= mod;
            System.out.println(solve(a,b,n));
        }
    }

    public static long solve(long a, long b,int n){
        long[] nums = new long[n+1];
        nums[1] = a;
        if(n==1) return nums[1];
        nums[2] = (a * a % mod - 2 * b % mod + mod) % mod;
        if(n==2) return nums[2];
        for(int i=3;i<=n;i++)
            nums[i] = ((a*nums[i-1]%mod)-(b*nums[i-2]%mod)+mod)%mod;
        return nums[n];
    }

}

编辑于 2021-06-29 18:26:25 回复(1)
Dominic789654头像 Dominic789654
我这样运行时间超了，大佬能帮忙看看吗 python解法
T = int(input())
mod_num = 10 ** 9 + 7
for _ in range(T):
    A, B, n = map(int, input().split())
    if n == 1:
        print(A)
    elif n == 2:
        print((A ** 2 - 2 * B) % mod_num)
    else:
        rn1, rn2 = (A ** 2 - 2 * B) % mod_num, A
        res = 0
        while n > 2:
            res = (A * rn1 - B * rn2)
            rn2 = rn1
            rn1 = res
            n -= 1
        print(res)

编辑于 2021-06-19 22:31:45 回复(8)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
22条回答 12571浏览

热门推荐

通过挑战的用户

相关试题

小强爱数学

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号