Codeforces 1105C (DP)

题面

传送门

分析

这种计数问题，要不是纯数学推公式，要不就是dp

先处理出[l,r]中除3余0,1,2的数的个数，记为cnt0,cnt1,cnt2

设\(dp[i][j]\)表示前i个数的和除3余j的个数

则\(dp[1][0]=cnt0,dp[1][1]=cnt1,dp[1][2]=cnt2\)

最终答案为\(dp[n][0]\)

状态转移方程为

\(dp[i][0]=dp[i-1][0]*cnt0+dp[i-1][1]*cnt2+dp[i-1][2]*cnt1\)

\(dp[i][1]=dp[i-1][1]*cnt0+dp[i-1][2]*cnt2+dp[i-1][0]*cnt1\)

\(dp[i][2]=(dp[i-1][2]*cnt0+dp[i-1][0]*cnt2+dp[i-1][1]*cnt1\)

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#define maxn 200005

#define mod 1000000007

using namespace std;

int n;

long long l,r;

long long cnt0,cnt1,cnt2;

long long dp[maxn][3];

int solve(int x,int k){

	int t;

	if(x%3==0) t=3;

	else t=x%3;

	return (x-t)/3+(x%3==k);

}

int main(){

	scanf("%d %I64d %I64d",&n,&l,&r);

	int l1,l2,l3;

	l1=l%3;

	l2=(r+1-l);

	l3=l2%3;

	l2=l2/3;

	cnt1=cnt2=cnt0=l2;

	if(l3==1){

		if(l1==1) cnt1++;

		else if(l1==2) cnt2++;

		else cnt0++;

	}

	if(l3==2){

		cnt1++,cnt2++,cnt0++;

		if(l1==1) cnt0--;

		else if(l1==2) cnt1--;

		else cnt2--;

	}

	dp[1][0]=cnt0;

	dp[1][1]=cnt1;

	dp[1][2]=cnt2;

	for(int i=2;i<=n;i++){

		dp[i][0]=(dp[i-1][0]*cnt0%mod+dp[i-1][1]*cnt2%mod+dp[i-1][2]*cnt1)%mod;

		dp[i][1]=(dp[i-1][1]*cnt0%mod+dp[i-1][2]*cnt2%mod+dp[i-1][0]*cnt1)%mod;

		dp[i][2]=(dp[i-1][2]*cnt0%mod+dp[i-1][0]*cnt2%mod+dp[i-1][1]*cnt1)%mod;

	}

	printf("%I64d\n",dp[n][0]);

}

巴特西

Codeforces 1105C (DP)

题面

分析

代码

最新文章

热门文章