题目链接：http://codeforces.com/problemset/problem/1105/C
题目大意：给你一个n, l, r; 让你构造阵列满足以下条件：

  1. 阵列长度为n；
  2. 阵列中所有的整数位于[l, r]之间
  3. 这个阵列所有的整数和能被3整除

让你求有多少个构造方案：结果mod 1e9+7。

思路：首先把所有[l, r]区间内所有整数 mod 3=0， mod 3=1， mod 3=2的个数统计出来。当时就是觉得是组合数学。当时一直不知道怎么去重。后来听群里有人说直接dp。然后用一维dp。

dp[i]代表：长度为i的阵列的个数。然后发现，这个状态不好推。
dp[i]可以由dp[j](j<i)的所有状态转化。

然后用了二维dp
dp[i][j]代表：长度为i，整数和mod 3=j的个数。

所以状态的转移方程：
dp[i][0]=(dp[i-1][0]*a[0]) + (dp[i-1][1]*a[2]) + (dp[i-1][2]*a[1])；
dp[i][1]=(dp[i-1][0]*a[1]) + (dp[i-1][1]*a[0]) + (dp[i-1][2]*a[2]);
dp[i][2]=(dp[i-1][0]*a[2]) + (dp[i-1][1]*a[1]) + (dp[i-1][2]*a[0]);

思路：之前dp很少用来计数的。现在知道了还有这种用法。

代码：

#include<bits/stdc++.h>
#define ll long long
//#define p1 first
//#define p2 second
using namespace std;
const int mod=1e9+7;
const int N=1e5+5;
//memset(a, 0, sizeof(a));
//stack堆栈 queue队列 priority_queue优先队列
//vector向量 multiset平衡二叉树 deque双端队列
//pair{T1 first;T2 second;} greater<T>
//unordered_map 哈希map

ll a[3];
ll dp[200005][3];
int main()
{
    int n, l, r;
    scanf("%d%d%d",&n,&l,&r);
    a[0]=(r-l+1)/3;
    a[1]=(r-l+1)/3;
    a[2]=(r-l+1)/3;
    int k=l%3;
    for(int i=r;i>=l;i--)
    {
        if(i%3!=(k+3-1)%3)
        {
            a[i%3]++;
        }
        else
        {
            break;
        }
    }
    dp[1][0]=a[0], dp[1][1]=a[1], dp[1][2]=a[2];
    for(int i=2;i<=n;i++)
    {
        dp[i][0]=((dp[i-1][0]*a[0])%mod+(dp[i-1][1]*a[2])%mod+(dp[i-1][2]*a[1])%mod)%mod;
        dp[i][1]=((dp[i-1][0]*a[1])%mod+(dp[i-1][1]*a[0])%mod+(dp[i-1][2]*a[2])%mod)%mod;
        dp[i][2]=((dp[i-1][0]*a[2])%mod+(dp[i-1][1]*a[1])%mod+(dp[i-1][2]*a[0])%mod)%mod;
    }
    printf("%lld\n", dp[n][0]);

    return 0;
}