首页 > 代码库 > SRM 508 DIV1 500pt(DP)

SRM 508 DIV1 500pt(DP)

2024-08-07 01:30:27   216人阅读

题目简述

给定一个大小为 n的序列(n<=10)R,要求你计算序列A0, A1, ..., AN-1的数量，要求A序列满足A0 + A1 + ... + AN-1 = A0 | A1 | ... | AN-1(0<=Ai<=R[i])

题解

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

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

代码：

 1 #define MOD 1000000009; 2 ll dp[65][1111]; 3 vector<ll>r; 4 int n; 5 ll DP(int i, int mask) 6 { 7     if (i == -1) return 1; 8     ll &ret = dp[i][mask]; 9     if(ret!=-1) return ret;10     ret=0;11     int next = mask;12     for (int t = 0; t < n; t++)13         if (r[t] & (1LL << i))14             next |= (1 << t);15     ret += DP(i - 1, next);16     ret%=MOD;17     for (int t = 0; t < n; t++)18         if (mask & (1 << t))19         {20             ret += DP(i - 1, next);21             ret %= MOD;22         }23         else if (r[t] & (1LL << i))24         {25             ret += DP(i - 1, next ^ (1 << t));26             ret %= MOD;27         }28     return ret;29 }30 class YetAnotherORProblem31 {32 public:33     int countSequences(vector<long long> R)34     {35         n = R.size();36         r = R;37         memset(dp, -1, sizeof(dp));38         return DP(60, 0);39     }40 };

 

SRM 508 DIV1 500pt(DP)


联系
我们