标签： 状态压缩DP

---

题目描述

Haiku is a short form of Japanese poetry. A Haiku consists of three phrases with 5, 7 and 5 syllables, in this order.

Iroha is looking for X,Y,Z-Haiku (defined below) in integer sequences.

Consider all integer sequences of length N whose elements are between 1 and 10, inclusive. Out of those 10N sequences, how many contain an X,Y,Z-Haiku?

Here, an integer sequence a0,a1,…,aN−1 is said to contain an X,Y,Z-Haiku if and only if there exist four indices x,y,z,w(0≤x<y<z<w≤N) such that all of the following are satisfied:

ax+ax+1+…+ay−1=X

ay+ay+1+…+az−1=Y

az+az+1+…+aw−1=Z

Since the answer can be extremely large, print the number modulo 109+7.

Constraints

3≤N≤40

1≤X≤5

1≤Y≤7

1≤Z≤5

输入

The input is given from Standard Input in the following format:

N X Y Z

输出

Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 109+7.

样例输入

3 5 7 5

样例输出

1

提示

Here, the only sequence that contains a 5,7,5-Haiku is [5,7,5].

分析

• 用dp[i][j]来表示,长度为i的数组,最后几个数字的状态为j,且这个数组中不存在连续的一些数的和为X,Y,Z的方法数.
• 状态j是这么定义的,把数组中的元素的二进制表示按照顺序串联起来,取后X+Y+Z位
• 如果倒数第Z位,倒数第Y+Z位,倒数第X+Y+Z位都是1,那么就满足了题目中所说的条件.

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;typedef long long ll;const ll MOD=1e9+7;int n,a,b,c;ll dp[42][1<<17];int main(int argc, char const *argv[]){    scanf("%d%d%d%d", &n,&a,&b,&c);    dp[0][0]=1;    int base=(1<<(c-1))+(1<<(b+c-1))+(1<<(a+b+c-1));    for (int i = 0; i < n; ++i)    {        for (int j = 0; j < (1<<(a+b+c)); ++j)        {            for (int k = 0; k < 10; ++k)            {                int x=(j<<(k+1))+(1<