广东省住房和建设网站,wordpress 主题地址,商标注册网上缴费,高端定制开发网站题意#xff1a;
给你一个数组R#xff0c;包含N个元素#xff0c;求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R [ i ] A[0]A[1]…A[N−1] A[0] | ]A[1]… | A [ N − 1 ] 输出答案对1e99取模
题解#xff1a;
参考博客 数位dp问题 如果和等于或的话#xff0c;说明两…题意
给你一个数组R包含N个元素求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R [ i ] A[0]A[1]…A[N−1] A[0] | ]A[1]… | A [ N − 1 ] 输出答案对1e99取模
题解
参考博客 数位dp问题 如果和等于或的话说明两种情况
多个数的该二进制位只有一个1多个数该二进制位的都没有1 说明要满足等式每一位数的二进制只能出现在这个n个数中的某一位上
因为加法是把每个二进制位上的数字加起
而或是最多只能有1
如果有一个二进制位有两个数都是1
那么一定会导致这个位往上一位进1
那就影响其他位了
一定不可能相等的
101和10 111
加起来也是
但11010 1000
110|10 110我们简化问题对于(a,b),如果a b a | b且ar0br1 设dp[len][limit1][limit2]表示枚举到二进制第len位a是否限制b是否限制limit1和limit2的值为0或1, 这样我们只需要暴力考虑当前位二进制填0还是1并考虑是填在a还是b
现在将问题扩展对于(a,b,c,…)根据题目n最多10那我们开个11维的数组就可以了dp[len][2][2]…[2]但是我们注意到从第二位到最后一位都只用来表示0和1那么我们将这些压缩用二进制压缩这样就成二维数组了dp[len][x].x的二进制下表示每个数卡不卡上界
代码
代码里有加注释
#include bits/stdc.h
using namespace std;
typedef long long ll;
const ll N11,M65;
const ll mod1e99;
ll R[N];
int n;
ll dp[M][1N];inline ll dfs(ll s,ll pos)//每个与前面相同情况,现在分配到了第pos位.
{ll ansdp[pos][s];if(pos0) return 1;if(ans) return ans;//先分配0.int sps;for(int i0;in;i){if((s(1i))(R[i](1ll(pos-1))))//假设这一位和R[i]的前pos-1位相同.{sp^(1i);}}ans(ansdfs(sp,pos-1))%mod;//分配一个1.for(int i0;in;i){if((s(1i))){if(!(R[i](1ll(pos-1)))) continue;ans(ansdfs(sp^(1lli),pos-1))%mod;}else ans(ansdfs(sp,pos-1))%mod;}return ans;
}int main()
{scanf(%d,n);for(int i0;in;i){scanf(%lld,R[i]);}printf(%lld\n,dfs((1n)-1,60ll));return 0;
}
