Codeforces - Ayoub and Lost Array

题目链接：Codeforces - Ayoub and Lost Array

---

比较显然的dp

dp[i][0,1,2]表示前i为%3余数是多少的数量。

---

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n,l,r,dp[N][3],cnt[3];
signed main(){
	cin>>n>>l>>r;	int pos=l%3,k=(r-l+1)/3,num=(r-l+1)-3*k;
	cnt[0]=cnt[1]=cnt[2]=k;
	while(num--)	cnt[pos%3]++,pos++;
	dp[1][0]=cnt[0],dp[1][1]=cnt[1],dp[1][2]=cnt[2];
	for(int i=2;i<=n;i++){
		dp[i][0]=(dp[i-1][1]*cnt[2]+dp[i-1][2]*cnt[1]+dp[i-1][0]*cnt[0])%mod;
		dp[i][1]=(dp[i-1][1]*cnt[0]+dp[i-1][2]*cnt[2]+dp[i-1][0]*cnt[1])%mod;
		dp[i][2]=(dp[i-1][1]*cnt[1]+dp[i-1][2]*cnt[0]+dp[i-1][0]*cnt[2])%mod;
	}
	cout<<dp[n][0];
	return 0;
}