首页 > 其他分享 >1454. 异或和是质数的子集数 01背包

1454. 异或和是质数的子集数 01背包

时间:2022-09-02 21:55:57浏览次数:61  
标签:01 int 质数 1454 异或 背包 dp

题意

给出 n 个互不相同的正整数。

问存在多少个子集,使得子集中所有数的异或和是质数。

由于答案可能很大,请你输出对 109+7 取模后的结果。

分析

题意就是指:
从一堆元素中挑选元素,达到指定的要求的题目,符合01背包的性质。使用01背包即可

求背包大小:
由于数据范围最大不超过5000, 异或是二进制运算,\(2^{12} = 4096 < 5000\), 所以即使是异或后的数,它的二进制表示不超过13位。
\(2^{12}+2^{11}+2^{10}+…+2+1=8191;\)

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
const int N =5010,M=1e9+7;
const int MAX=8192;
int n;
int a[N];
int dp[3][MAX];
bool is_prime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}
void slove()
{
   cin>>n;
   for(int i=1;i<=n;i++){
     cin>>a[i];
   }
    // dp数组初始化,即没有数字可选,但是要达到异或和为0,正好有1种选法:即什么都不选。
   dp[0][0]=1;
   for(int i=1;i<=n;i++){
    for(int j=0;j<MAX;j++){
        dp[i&1][j]=dp[(i-1)&1][j];
        if( (j^a[i]) < MAX){
           dp[i&1][j]+=dp[(i-1)&1][j^a[i]];
        }
        dp[i&1][j]%=M; 
    }
   }
   
   int ans=0;
   for(int i=2;i<MAX;i++){
     if(is_prime(i)){
        ans=(ans+dp[n&1][i])%M;
     }
   }
   cout<<ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        slove();
    return 0;
}

标签:01,int,质数,1454,异或,背包,dp
From: https://www.cnblogs.com/kingwz/p/16651483.html

相关文章

  • 质数筛
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn,primes[N];intget_prime(intu){intcnt=0;memset(primes,true,sizeof......
  • P4551 最长异或路径
    给定树上\(n\)个点和边权,求两点间所有边权的异或和最大。\(n\leq10^5\)。首先如果假定一个根,那么所有点到根的距离\(dis[i]\)中两两异或得到的就是答案。(\(x,y\)......
  • P4735 最大异或和
    给定一个非负整数序列\(\{a\}\),初始长度为\(n\)。有\(m\)个操作,有以下两种操作类型:Ax:添加操作,表示在序列末尾添加一个数\(x\),序列的长度\(n+1\)。Qlrx:询问操......
  • P4592 [TJOI2018]异或
    有一颗以\(1\)为根节点的由\(n\)个节点组成的树,节点从\(1\)至\(n\)编号。树上每个节点上都有一个权值\(v_i\)。现在有\(q\)次操作,操作如下:\(1~x~z\):查询节点......
  • java质数算法
    importjava.util.ArrayList;importjava.util.Iterator;importjava.util.List;importjava.stream.Collectors;importjava.stream.Stream;publicclassMain{publ......
  • 质数判定的常数优化
    注意:下面可能有部分数学符号使用不规范,看懂就行。如何迅速判断\(n\)是否为质数?方法一枚举\(i\)满足\(1<i<n\),则\(n\)不是质数,当且仅当全部的\(i\nmidn\)......
  • 与运算符号问题、异或、短路与、短路或
    异或记忆口诀即:男同女同不可取(为false),男女才能修成正果(为true)......
  • 1006 最短路 dijkstra 异或运算变化的精简操作
     链接:https://ac.nowcoder.com/acm/contest/26077/1006来源:牛客网题目描述企鹅国中有NNN座城市,编号从111到NNN。对于任意的两座城市iii和j......
  • 开关(线段树区间异或板子)
    [TJOI2009]开关题目描述现有\(n\)盏灯排成一排,从左到右依次编号为:\(1\),\(2\),……,\(n\)。然后依次执行\(m\)项操作。操作分为两种:指定一个区间\([a,b]\),然后改变......
  • swap(a, b)异或骚操作方法
    众所周知,平日里我们如果要交换两个变量的时候,通常都是voidswap(inta,intb){inttemp=a;a=b;b=temp;}通过创建temp变量,保存其中一个的值,再交......