https://codeforces.com/contest/1105/problem/C

C++版本一

題解：DP+矩陣快速冪

參考文章：https://blog.csdn.net/weixin_43272781/article/details/85939539

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; //typedef __int128 lll; const int N=10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,l,r,q; int ans,cnt,flag,temp; int a[N]; char str;int tmp[N][N]; void multi(ll a[][3],ll b[][3]) {memset(tmp,0,sizeof tmp);for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<3;k++)tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%MOD;for(int i=0;i<3;i++)for(int j=0;j<3;j++)a[i][j]=tmp[i][j]; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d%d%d",&n,&l,&r);a[0]=a[1]=a[2]=r/3;if(r%3==1)a[1]++;if(r%3==2)a[1]++,a[2]++;a[0]-=(l-1)/3;a[1]-=(l-1)/3;a[2]-=(l-1)/3;if((l-1)%3==1)a[1]--;if((l-1)%3==2)a[1]--,a[2]--; // b[0]=b[0]*a[0]+b[1]*a[2]+b[2]*a[1]; // b[1]=b[0]*a[1]+b[1]*a[0]+b[2]*a[2]; // b[2]=b[0]*a[2]+b[1]*a[1]+b[2]*a[0];ll b[5][3]={a[0],a[1],a[2],a[2],a[0],a[1],a[1],a[2],a[0]};ll c[5][3]={a[0],a[1],a[2],a[2],a[0],a[1],a[1],a[2],a[0]};n--;while(n){if(n&1){multi(b,c);}multi(c,c);n/=2;}cout<<b[0][0]<<endl;//cout << "Hello world!" << endl;return 0; }

C++版本二

題解：數(shù)位DP

#include<stdio.h> #include<stdlib.h> #include<math.h> #include<algorithm> #define ll long long #define pb push_back #define test printf("here!!!") using namespace std; const int mx=2e5+10; const ll mod=1e9+7; ll a,b,c; ll f[mx][3]; int main() {int n,l,r;scanf("%d%d%d",&n,&l,&r);int ls=l;int rs=r;int ys;while (ls%3!=0){ls++;}while (rs%3!=0){rs--;}if (r-l<3){for (int i=l;i<=r;++i){ys=i%3;if (ys==1) b++;else if (ys==2) c++;else if (ys==0) a++;}}else{if (ls<=rs&&ls<=r&&rs>=l){a=rs/3-ls/3+1;b=a-1;c=a-1;}for (int i=l;i<ls;++i){ys=i%3;if (ys==1) b++;else if (ys==2) c++;else if (ys==0) a++;}for (int i=rs+1;i<=r;++i){ys=i%3;if (ys==1) b++;else if (ys==2) c++;else if (ys==0) a++;}}f[1][0]=a;f[1][1]=b;f[1][2]=c;for (int i=2;i<=n;++i){f[i][0]=(f[i-1][1]*c%mod+f[i-1][2]*b%mod+f[i-1][0]*a%mod)%mod;f[i][1]=(f[i-1][1]*a%mod+f[i-1][2]*c%mod+f[i-1][0]*b%mod)%mod;f[i][2]=(f[i-1][1]*b%mod+f[i-1][2]*a%mod+f[i-1][0]*c%mod)%mod;}printf("%I64d\n",f[n][0]); }

?

與50位技術(shù)專家面對面20年技術(shù)見證，附贈技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的Ayoub and Lost Array的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。