递推

百度之星递推题（用矩阵乘法加速，用费马小定理缩小）

思路：因为只有1->0的情况是0，其他都是1，所以我们考虑递推。$f[n] = 2 ^ n - f[n - 1] \(,\) 2^n$是所有情况，因此唯一可能的情况是在原来 \(f[n - 1]\) 的末尾接上一个 \(0\)，最终结果才是 \(0\)。由容斥原理可得 \(f[n] = 2^n - f[n - 1]\)(后一项为0的方案) 。接下来我们将 \(f[n + 1] = 2 ^ (n + 1) - f[n]\) 和 \(2 * f[n] = 2 * 2 ^ n - 2 * f[n - 1]\) 进行互减，形成递推式：\(f[n] = f[n - 1] + 2 * f[n - 2]\)。我们建立一个 \(2 * 2\) 的矩阵加速一下即可。

注意读入的数据很大，我们一边读一遍对(mod - 1)取模即可。

时间复杂度：O(8logn)

代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
#define ll long long
const int N = 2, mod = 998244353;
void mul(ll f[2],ll a[2][2]){
	ll c[2];
	memset(c,0,sizeof(c));
	for(int j=0;j<2;j++)
	{
		for(int k=0;k<2;k++){
			c[j]=(c[j]+(ll)f[k]*a[k][j])%mod;
		}
	}
	memcpy(f,c,sizeof(c));
}
void mulself(ll a[2][2]){
	ll c[2][2];
	memset(c,0,sizeof(c));
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%mod;
			}
		}
	}
	memcpy(a,c,sizeof(c));
}
ll qdt(int n){
	ll f[2]={1,1};//可变
	ll a[2][2]={{0,2},{1,1}};//可变
	for(;n;n>>=1){
		if(n&1) mul(f,a);
		mulself(a);
	} 
	return f[0];
}
signed main()
{
    string s;
    cin >> s;
    int n = 0;
    for(int i = 0 ; s[i] ; i ++ )
        n = (n * 10 + s[i] - '0') % (mod - 1);//费马小定理处理大数读入 
    cout<<qdt(n);
    
    return 0;
}