# 算法竞赛进阶指南-0x02基本算法-递推与递归

25 盏灯排成一个 5×5 的方形。

Solution:

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int inf = 0x7f7f7f7f;

int t;
int n;
char g[6][6], b[6][6];
int dir[5][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {0, 0}};

void turn(int x, int y){
for(int i = 0; i < 5; i ++){
int dx = dir[i][0] + x;
int dy = dir[i][1] + y;
if(dx >= 0 && dx < 5 && dy >= 0 && dy < 5){
g[dx][dy] = (g[dx][dy] == '0' ? '1' : '0');
}
}
}

void solve(){
int ans = inf;
for(int k = 0; k < 32; k ++){
int res = 0;

memcpy(b, g, sizeof g);
for(int j = 0; j < 5; j ++){
if(k >> j & 1){
res ++;
turn(0, j);
}
}

for(int i = 0; i < 4; i ++){
for(int j = 0; j < 5; j ++){
if(g[i][j] == '0'){
res ++;
turn(i + 1, j);
}
}
}

int f = 0;
for(int j = 0; j < 5; j ++){
if(g[4][j] == '0'){
f = 1;
break;
}
}
if(!f)  ans = min(ans, res);
memcpy(g, b, sizeof b);
}
if(ans > 6)  puts("-1");
else    printf("%d\n", ans);
}

int main(){
__;
cin >> t;
while(t --){
for(int i = 0; i < 5; i ++){
for(int j = 0; j < 5; j ++){
cin >> g[i][j];
}
}
solve();
}
return 0;
}



Solution:

f[i] = min(f[i], 2 * f[i] + D[n-i]), f[1]=1

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int n;
int f[15], d[15];

int main(){
__;
for(int i = 1; i <= 12; i ++){
d[i] = d[i - 1] * 2 + 1;
}
memset(f, 0x3f, sizeof f);
f[1] = 1;
for(int i = 2; i <= 12; i ++){
for(int j = 1; j < i; j ++){
f[i] = min(f[i], 2 * f[j] + d[i - j]);
}
}
for(int i = 1; i <= 12; i ++){
printf("%d\n", f[i]);
}
return 0;
}



S \ mod \ 9901 ，其中 0 <= A,B <= 5×10^7

Solution1:

k偶数时：

f\left( p,k \right) =p^0+p^1+p^2+\cdot \cdot \cdot +p^{k/2-1}+p^{k/2}+p^{k/2+1}+\cdot \cdot \cdot +p^{k-1}

f\left( p,k \right) =p^0+p^1+p^2+\cdot \cdot \cdot +p^{k/2-1}+p^{k/2}\left( p^0+p^1+\cdot \cdot \cdot +p^{k/2-1} \right)

f\left( p,k \right) =f\left( p,k/2 \right) +p^{k/2}f\left( p,k/2 \right)

f\left( p,k \right) =f\left( p,k/2 \right) \left( 1+p^{k/2} \right)

k奇数时：

f\left( p,k \right) =f\left( p,k-1 \right) +p^{k-1}

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b;
ll ans = 0;
ll p[N], c[N];
int cnt = 0;

void div(ll n){
for(int i = 2; i <= n / i; i ++){
if(n % i == 0){
p[++ cnt] = i;
while(n % i == 0){
n /= i;
c[cnt] ++;
}
}
}
if(n > 1){
p[++ cnt] = n;
c[cnt] = 1;
}
}

ll qpow(ll a, ll b){
ll ans = 1ll % mod;
while(b){
if(b & 1)   ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}

ll f(ll p, ll k){
if(k == 1)  return 1;
if(k % 2 == 0){
return  (qpow(p, k / 2) + 1ll) * f(p, k / 2) % mod;
}
return qpow(p, k - 1) + f(p, k - 1) % mod;

}

int main(){
__;
cin >> a >> b;
ans = 1;
if(a == 0)  ans = 0;
else{
div(a);
for(int i = 1; i <= cnt; i ++){
ll pr = p[i], k = c[i] * b;
ans = ans * f(pr, k + 1) % mod;
}
}

printf("%lld\n", ans % mod);
return 0;
}



Solution2:

\left( p_1^0+p_1^1+p_1^2+\cdot \cdot \cdot +p_1^k \right) ^B\left( p_2^0+p_2^1+p_2^2+\cdot \cdot \cdot +p_2^k \right) ^B\cdot \cdot \cdot \left( p_n^0+p_n^1+p_n^2+\cdot \cdot \cdot +p_n^k \right) ^B

=\left( p_1^0+p_1^1+p_1^2+\cdot \cdot \cdot +p_1^{kB} \right) \left( p_2^0+p_2^1+p_2^2+\cdot \cdot \cdot +p_2^{kB} \right) \cdot \cdot \cdot \left( p_n^0+p_n^1+p_n^2+\cdot \cdot \cdot +p_n^{kB} \right)

=\frac{\left( 1-p_1 ^{kB+1} \right)}{1-p_1}\frac{\left( 1-p_2^{kB+1} \right) }{1-p_2}\cdot \cdot \cdot \frac{\left( 1-p_n^{kB+1} \right) }{1-p_n}

=\frac{\left( p_1^{kB+1}-1 \right)}{p_1-1}\frac{\left( p_2^{kB+1}-1 \right)}{p_2-1}\cdot \cdot \cdot \frac{\left( p_n^{kB+1}-1 \right)}{p_n-1}

1+p_1+p_1^2+\cdot \cdot \cdot +p_1^k

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

ll a, b;
ll ans = 0;
int p[N], c[N];
int cnt = 0;

void div(ll n){
for(int i = 2; i <= n / i; i ++){
if(n % i == 0){
p[++ cnt] = i;
while(n % i == 0){
n /= i;
c[cnt] ++;
}
}
}
if(n > 1){
p[++ cnt] = n;
c[cnt] = 1;
}
}

ll qpow(ll a, ll b){
ll ans = 1ll % mod;
while(b){
if(b & 1)   ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}

int main(){
__;
cin >> a >> b;
ans = 1;
if(a == 0)  ans = 0;
else{
div(a);
for(int i = 1; i <= cnt; i ++){
if((p[i] - 1) % mod == 0){
ans = ans % mod * (1ll * c[i] * b + 1ll) % mod;
}
else{
ll x = (qpow(p[i], (1ll * c[i] * b + 1ll)) % mod - 1ll + mod) % mod;
ll y = qpow(p[i] - 1ll, mod - 2ll) % mod;
ans = ans % mod * x % mod * y % mod;
}
}
}

printf("%lld\n", ans);
return 0;
}



Solution:

Code:

#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const int N = 3e5+10;
const ll mod = 9901;

#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())

#define __ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int t;

P f(ll n, ll m){
if(n == 0)  return {0, 0};
ll len = 1ll << (n - 1);// n - 1级图构成n级图平移时的单位长度
ll cnt = 1ll << (n - 1) * 2;// n - 1级图中所含的元素个数
ll cnk = m / cnt; // 在n级图中，编号为m的元素所属块的编号
ll idx = m % cnt; // 在n级图中，编号为m的元素在所属块中的编号
P pos = f(n - 1, idx); // 在n级图中，编号为m的元素在所属块中的坐标
// 根据n级图中某个块的编号和这个块中某个元素的坐标，确定n - 1级图的坐标变换
ll x = pos.fi, y = pos.se;
if(cnk == 0)   return {y, x};
else if(cnk == 1)   return {x, y + len};
else if(cnk == 2)   return {x + len, y + len};
else    return {2 * len - 1 - y, len - 1 - x};
}

int main(){
__;
cin >> t;
while(t --){
ll n, a, b;
cin >> n >> a >> b;
P pa = f(n, a - 1);
P pb = f(n, b - 1);
double dis = sqrt((double)(pa.fi - pb.fi) * (pa.fi - pb.fi) + (pa.se - pb.se) * (pa.se - pb.se));
printf("%.0lf\n", 10 * dis);
}
return 0;
}