LP4461 [CQOI2018] 九连环 [递推]
递推 + 巧 bao 妙 li 的方法
Problem
$n$ 连环方案数,无取模。
Solution
经过半个小时的推导:
111111 -> 110000 -> 010000 -> .... -> 011000 -> 001000
f[4] 1 g[4] 1
得出以下结果:
$$ans_i=f_{i-2}+2^{i-1}$$
$$f_i=2f_{i-1}+[i\%2=0], f_1=1$$
然后就暴力高精度了。会超时呢。于是去学了压位。
用__int128 压了 37 位,就可以很快的过掉了。
// Code by ajcxsu
// Problem: 9 circles
#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;
typedef long long ll;
const int p=37;
__int128 car=1;
void llput(__int128 x, int pre=0) {
char s[40]; int p=0;
while(x) s[p++]=x%10, x/=10;
for(int i=1;i<=pre-p;i++) putchar('0');
for(int i=p-1;i>=0;i--) putchar(s[i]+'0');
}
struct BIGNUM {
static const int N=1000;
__int128 nu[N]={0}, len=0;
void operator = (int x) {
len=0;
while(x) nu[len++]=x%car, x/=car;
if(!len) len++;
}
BIGNUM(int x) { *this=x; }
void add() {
nu[0]++;
if(nu[0]>=car) nu[0]-=car, nu[1]++;
if(nu[1]>=car) nu[1]-=car, nu[2]++;
if(len==1 && nu[1]) len++;
if(len==2 && nu[2]) len++;
}
void operator += (BIGNUM b) {
len=max(len, b.len)+1;
for(int i=0;i<=len;i++) {
nu[i]+=b.nu[i];
if(nu[i]>=car) nu[i+1]++, nu[i]-=car;
}
while(!nu[len-1] && len>1) len--;
}
void putout() {
for(int i=len-1;i>=0;i--)
if(i!=len-1) llput(nu[i], p);
else llput(nu[i]);
putchar('\n');
}
} ;
int main() {
for(int i=0;i<37;i++) car*=10;
int n;
scanf("%d", &n);
int na;
while(n--) {
scanf("%d", &na);
if(na==1) puts("1");
else if(na==2) puts("2");
else {
BIGNUM a=1, b=2;
for(int i=2;i<=na-1;i++) {
b+=b;
if(i<=na-2) {
if(!(i&1)) a+=a;
else a+=a, a.add();
}
}
a+=b, a.putout();
}
}
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-4461.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆