Atcoder TUPC 2023（東北大学プログラミングコンテスト 2023）E. And DNA（矩阵快速幂+拆位讨论）

题目

长为n(3<=n<=1e9)的数组，第i个数ai在[0,m](m<=1e9)之间

对于i∈[1,n]，均满足a[i]+(a[i-1]&a[i+1])=m，求这样可能的数组的方案数

特别地，认为a[0]=a[n],a[n+1]=a[1]，即这个数组是个环形的数组

思路来源

官方题解

题解

从末位考虑，

1. 如果m=0，只能全是0，方案数为1

2. 如果m=1，由于1+(1&1)=2，0+(0&x)=0，所以不能有三个1相邻，不能有两个0相邻

将相邻位的数字每两个看成一个点，即从01/10/11出发，

01可以转移到10或11，11可以转移到10，10只能转移到01，矩阵快速幂求出长为n的方案数

3. 如果m为>=2的偶数，考虑末位是1还是0，

①如果是1，只能是1+(1&1)=2，此时还给倒数第二位贡献了1，需要再递归求m/2-1的方案

②如果是0，只能是全0，需要再递归求m/2的方案

有f(m)=f(m/2)+f(m/2-1)

4. 如果m为>=3的奇数，末位只能是1，并且由于没有进位，可以分开来看

有f(m)=f(1)+f((m-1)/2)

代码

#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=998244353;
struct mat {static const int MAXN=3;ll c[MAXN][MAXN];int m, n;mat(){memset(c, 0, sizeof(c));m=n=MAXN;}mat(int a, int b) : m(a), n(b) {memset(c, 0, sizeof(c));}void clear(){memset(c, 0, sizeof(c));}mat operator * (const mat& temp) {mat ans(m, temp.n);for (int i = 0; i < m; i ++)for (int j = 0; j < temp.n; j ++){for (int k = 0; k < n; k ++){ans.c[i][j] += c[i][k] * temp.c[k][j];ans.c[i][j]%=mod;}}return ans;}mat operator ^(ll n){mat M(*this),ans(M.m, M.m);for (int i = 0; i < M.m; i ++)ans.c[i][i] = 1;while (n > 0) {if (n & 1) ans = ans * M;M = M * M;n >>= 1;}return ans;}
}b;
//01 10 11 没有相邻两个0或者三个1的方案数
int n,m,ans;
int sol(int m){if(m==0)return 1;//全0if(m==1)return ans;if(m%2==0)return (sol(m/2)+sol(m/2-1))%mod;//进位和不进位return 1ll*ans*sol(m/2)%mod;
}
int main(){scanf("%d%d",&n,&m);b.c[0][1]=b.c[0][2]=1;//01->10 01->11b.c[1][0]=1;//10->01b.c[2][1]=1;//11->10b=b^n;rep(i,0,2){ans=(ans+b.c[i][i])%mod;}printf("%d\n",sol(m));return 0;
}