LP4461 [CQOI2018] 九连环 [递推]

Author Avatar
空気浮遊 2019年01月20日
  • 在其它设备中阅读本文章
  • 递推
  • 暴力
  • 高精
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

递推 + 巧 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 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material