题解 AT3958 【[AGC024A] Fairness】

· · 题解

已知：

$B_i=C_{i-1}+A_{i-1}$ ， $C_i=A_{i-1}+B_{i-1}$ ， 求 $A_k-B_k$ 。 三种方法 。 ### 法1 $A_k-B_k=(B_{k-1}+C_{k-1})-(C_{k-1}+A_{k-1}) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =B_{k-1}-A_{k-1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(-1)^k(A_{0}-B_{0}) 
#include <iostream>

using namespace std;

int a,b,c,k;

int main() 
{
    int i,j,k;
    cin>>a>>b>>c>>k;
    cout<<(-(k%2*2-1))*(a-b);
    return 0;
}

法2

令S_k=A_k+B_k+C_k=2(A_{k-1}+B_{k-1}+C_{k-1})=2^k(A_0+B_0+C_0)

A_k=B_{k-1}+C_{k-1} \ \ \ \ \ \ =A_{k-2}+S_{k-2} \ \ \ \ \ \ =A_{k-2}+2^{k-2}(A_0+B_0+C_0)

若2|k

A_k=\sum_{i=1}^{\frac{k}{2}-1}4^i(A_0+B_0+C_0)+A_0 B_k=\sum_{i=1}^{\frac{k}{2}-1}4^i(A_0+B_0+C_0)+B_0 C_k=\sum_{i=1}^{\frac{k}{2}-1}4^i(A_0+B_0+C_0)+C_0

若2|k+1

A_k=2\sum_{i=1}^{\frac{k}{2}-1.5}4^i(A_0+B_0+C_0)+B_0+C_0 B_k=2\sum_{i=1}^{\frac{k}{2}-1.5}4^i(A_0+B_0+C_0)+A_0+C_0 C_k=2\sum_{i=1}^{\frac{k}{2}-1.5}4^i(A_0+B_0+C_0)+A_0+B_0

此时若是还没有发现 A_k-B_k 能够消掉那么可以用一些等比数列求和公式加快速幂。

法3

考虑暴力方法。

A_i\\B_i\\C_i \end{pmatrix}\begin{pmatrix} 0&1&1\\1&0&1\\1&1&0 \end{pmatrix}=\begin{pmatrix} A_{i+1}\\B_{i+1}\\C_{i+1} \end{pmatrix}

所以

A_{k}\\B_{k}\\C_{k} \end{pmatrix}=\begin{pmatrix} A_0\\B_0\\C_0 \end{pmatrix}\begin{pmatrix} 0&1&1\\1&0&1\\1&1&0 \end{pmatrix}^k

用矩阵快速幂求之 。