第五题下棋的小贝
思维 + 图形 + 规律
主要思想就是每个点有以下三种情况4,3,2个相邻的。这时候还要了解要构造一个最大的正方形这样才能够使得总和最大,这样的话再继续考虑外围的点。这时就要需要自己通过图形构造来找出规律
#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
const ll N = 2e6;
ll a[N],tg[N],ans[N];
ll n,m;
ll ls(ll aa){
return aa << 1;
}
void solve(){
ll n;
std::cin >> n;
ll re = std::sqrt(n);//最大正方形的边长
ll res = 0;
res = res + (4 * 2);
res = res + (re - 2) * 3 * 4;
res = res + (re - 2) * (re - 2) * 4;
ll gg = n - re * re;
if(gg >= 1 && gg <= re){
res = res + (gg * 4 - 2);
}
else if(gg > re){
res = res + (gg * 4 - 4);
}
std::cout << res << "\n";
return ;
}
int main(){
ll t = 1;
while(t --)
solve();
return 0;
}
第六题方程
递推 + 矩阵快速幂
递推,f(n)=x^n+1/x^n,f(1)*f(n-1)=f(n-2)+f(n),f(n)=kf(n-1)-f(n-2)
由于n比较大,所以类似于斐波那契,用矩阵快速幂解决
#include <iostream>
#include <cstring>
#define ll long long
const ll mod = 1e9 + 7;
void ww(ll c[2][2],ll a[2][2],ll b[2][2]){
ll jk[2][2] = {0};
for(ll i = 0; i <= 1; i ++){
for(ll j = 0; j <= 1; j ++){
for(ll k = 0; k <= 1; k ++){
jk[i][j] = (jk[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
std::memcpy(c,jk,sizeof jk);
}
void ss(ll a[2][2],ll b){
ll re[2][2] = {0};
re[1][1] = re[0][0] = 1;
while(b){
if(b & 1) ww(re,re,a);
ww(a,a,a);
b >>= 1;
}
std::memcpy(a,re,sizeof re);
}
void solve(){
ll n,k;
std::cin >> n >> k;
ll f1 = k;
ll f2 = ((k * k - 2) % mod + mod) % mod;
if(n == 1){
std::cout << f1 << "\n";
}
else if(n == 2){
std::cout << f2 << "\n";
}
else{
ll a[2][2] = {{k,-1},{1,0}};
ss(a,n - 2);
ll res = a[0][0] * f2 + a[0][1] * f1;
res %= mod;
std::cout << (res + mod) % mod << "\n";
}
return ;
}
int main(){
ll t = 1;
std::cin >> t;
while(t --)
solve();
return 0;
}