[编程题]小强爱数学
#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)
#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)
数学问题
记 Rn = x^n + y^n, a = x + y, b = x * y
记 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)
题目避开了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)
""" 得到递归规律后，使用矩阵快速幂求解，注意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)
思路： 动态规划
转移方程：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)
有没有大佬告诉我，下面的代码哪里错了
#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)
#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;
}
#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)
#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)
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)
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)
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)
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)
我这样运行时间超了，大佬能帮忙看看吗 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)
问题信息
通过挑战的用户
-
2023-03-14 13:42:09
-
2023-03-14 10:59:09 -
2023-03-10 17:24:21 -
2023-03-10 13:39:41 -
2023-03-08 23:07:28
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
