CF450B Jzzhu与数列问题的解释
CF450B Jzzhu与数列问题的解释
Content
有一个长度为\(n\)的序列\(\{a_1，a_2，\dots，a_n\}\)，它满足以下递归公式：
\(a_1=x\)当\(i=1\)时。
\(a_2=y\)当\(i=2\)时。
\(I \ geq plant 3 \)，\(a_i=a_{i-1} a_{i 1}\)。
求\ (a _ n \ bmod10 9 7 \)的值。
数据范围：\(1\leqslant n\leqslant 2\times 10^9\)，\(|x|,|y|\leqslant 10^9\)。
Solution
对于\(I \ geq plant 3 \)，我们不妨将这个表达式进行移位，得到\(a_{i 1}=a_i-a_{i-1}\)。然后先写下下面的公式：
\[\ begin { aligned } a _ 3=a _ 2-a _ 1=y-x \ \ a _ 4=a _ 3-a _ 2=(y-x)-y=-x \ \ a _ 5=a _ 4-a _ 3=-x-(y-x)=-y \ \ a _ 6=a _ 5-a _ 4=-y-(-x)=x-y \ \ a _ 7=a _ 6-a _ 5=x-y-(-y)=x \ color { Red }=a _ 1 \ \ a _ 8
\]我们发现当\(i=7\)时，\(a_7\)的值变回\(a_1\)。因此，我们发现了一个长度为(6)的循环节点。那么\(a_i\)就不难表达了：
\[a _ I=\ begin { cases } Xi \ b mod 6=1 \ \ yi \ b mod 6=2 \ \ y-Xi \ b mod 6=3 \ \-Xi \ b mod 6=4 \ \-yi \ b mod 6=5 \ \ x-yi \ b mod 6=0 \ end { cases }
\]直接按照这个公式计算\(a_n\)就行了，也就是\(a_{n\bmod 6}\)。负数取模前注意加模。
Code
const int mod=1e 9 7；
int f[7]；
int main(){ 0
int x=Rint，y=Rint，n=Rint
f[1]=x，f[2]=y，f[3]=y – x，f[4]=-x，f[5]=-y，f[6]=x-y；
返回写((f[(n – 1) % 6 1] % mod mod) % mod)，0；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/147910.html