LG题解 P4910 帕秋莉的手环

• Description
• Solution
• Code

Description

对一个长度为 \(n\) 的环 \(01\) 染色，要求相邻两个数之间必须有一个 \(1\)，求方案数。\(T\) 组询问。

Solution

设 \(f_i\) 表示长度为 \(i\) 的环的方案数。

你发现标签里有斐波那契，然后你准备猜一手结论。

用脚想一想就能得到 \(f_1 = 1\)（只有 \(1\) 这一种方案），\(f_2 = 3\) （有 \(11,01,10\) 这三种方案）。然后你想到了斐波那契的递推公式：

你在打草纸上模拟出了 \(f_5 = 11\)。

并花了 \(5min\) 用计算器验证了 \(f_9 = 76,f_{20} = 15127\) 的结果。

然后你花 \(10min\) 写了个矩阵快速幂，然后你把它切了。。。

考虑正确性：

考虑第 \(i\) 个位置，如果上个金在 \(i-2\) 的位置出现，你可以在这里放一个金，如果上个金在 \(i-1\) 的位置出现，你也可以在这里放一个金。不难发现只有这两种转移是合法的，前 \(i-1\) 长度的项链的所有合法方案有且仅有这两种情况，所以到当前位置的方案数就是前两个位置的方案数的和。

这个转移比较套路，矩阵快速幂加速转移即可，如果不懂可以来看一下我写的这篇博客。

总复杂度为 \(O(T \times 2^3 \log n)\)。

Code

/*
Work by: Suzt_ilymics
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include
#include
#include
#include
#include
#include
#define int long long
#define orz cout<<"lkp AK IOI!"<>= 1;
        }
        return res;
    }
}ans, base;

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void Init() {
    ans.a[0][0] = 3, ans.a[0][1] = 1;
    ans.a[1][0] = 0, ans.a[1][1] = 0;
    base.a[0][0] = 1, base.a[0][1] = 1;
    base.a[1][0] = 1, base.a[1][1] = 0;
}

signed main()
{
    int T = read();
    while(T--) {
        int n = read();
        if(n == 1) puts("1");
        else if(n == 2) puts("3");
        else {
            Init();
            base = base ^ (n - 2);
            ans = ans * base;
            printf("%lld\n", ans.a[0][0]);
        }
    }
    return 0;
}