SRM 508 DIV1 500pt(DP)

给定一个大小为 n的序列(n<=10)R,要求你计算序列A₀, A₁, ..., A_{N-1的数量，要求A序列满足A₀ + A₁ + ... + A_N-1 = A₀ | A₁ | ... | A_{N-1(0<=Ai<=R[i])}}

题解

把n个数看成二进制，如果要求n个数的和等于n个数的或值，那么对于n个数的每一位，最多只可能有一个1,因为超过一个一就会产生进位。

由于第i个数如果当前位放置的是0，但 R[i]的当前位是1,那么之后的位置上就可以随意放了，没有限制，所以我们可以用DP[i][j]表示在第i位，当前状态为j的符合要求的方案数有多少(j的二进制中1表示放置的数没有限制，不然就是有限制)，用记忆化搜索很好实现～～

代码：

 #define MOD 1000000009;

 ll dp[][];

 vector<ll>r;

 int n;

 ll DP(int i, int mask)

 {

     if (i == -) return ;

     ll &ret = dp[i][mask];

     if(ret!=-) return ret;

     ret=;

     int next = mask;

     for (int t = ; t < n; t++)

         if (r[t] & (1LL << i))

             next |= ( << t);

     ret += DP(i - , next);

     ret%=MOD;

     for (int t = ; t < n; t++)

         if (mask & ( << t))

         {

             ret += DP(i - , next);

             ret %= MOD;

         }

         else if (r[t] & (1LL << i))

         {

             ret += DP(i - , next ^ ( << t));

             ret %= MOD;

         }

     return ret;

 }

 class YetAnotherORProblem

 {

 public:

     int countSequences(vector<long long> R)

     {

         n = R.size();

         r = R;

         memset(dp, -, sizeof(dp));

         return DP(, );

     }

 };

巴特西

SRM 508 DIV1 500pt(DP)

最新文章

热门文章