零基础网站开发设计,搜索引擎推广一般包括( ),素材下载,免费搭建淘宝客网站题目
长为n(3n1e9)的数组#xff0c;第i个数ai在[0,m](m1e9)之间
对于i∈[1,n]#xff0c;均满足a[i](a[i-1]a[i1])m#xff0c;求这样可能的数组的方案数
特别地#xff0c;认为a[0]a[n],a[n1]a[1]#xff0c;即这个数组是个环形的数组
思路来源
官…题目
长为n(3n1e9)的数组第i个数ai在[0,m](m1e9)之间
对于i∈[1,n]均满足a[i](a[i-1]a[i1])m求这样可能的数组的方案数
特别地认为a[0]a[n],a[n1]a[1]即这个数组是个环形的数组
思路来源
官方题解
题解
从末位考虑
1. 如果m0只能全是0方案数为1
2. 如果m1由于1(11)20(0x)0所以不能有三个1相邻不能有两个0相邻
将相邻位的数字每两个看成一个点即从01/10/11出发
01可以转移到10或1111可以转移到1010只能转移到01矩阵快速幂求出长为n的方案数
3. 如果m为2的偶数考虑末位是1还是0
①如果是1只能是1(11)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
#includeiostream
#includecstdio
#includevector
#includemap
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 pairint,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#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 N1e510,mod998244353;
struct mat {static const int MAXN3;ll c[MAXN][MAXN];int m, n;mat(){memset(c, 0, sizeof(c));mnMAXN;}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(m0)return 1;//全0if(m1)return ans;if(m%20)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-10bb^n;rep(i,0,2){ans(ansb.c[i][i])%mod;}printf(%d\n,sol(m));return 0;
}
