技术标签： 动态规划
题目描述
输入
输出
样例输入
2
3
1 2 3
4
1 2 3 3
样例输出
1
4
题解：是一道dp常规题，思路很常规，但并不简单，特别是最后的去重，不细心的话很容易忽略就连样例都过不了。s【i】【j】表示前i位选出数^得到j的方案数，t【i】【j】表示后i位选数&得到j的方案数，最后通过乘法原理得出答案。，一定注意最后的ss【i】【0】--去重！！！
总结:dp很多题都是求前i个数……后i个数……，难点就是怎么讲前后连接，而求前i个数……、后i个数……通常都要枚举中间值k。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define N 30000
#define mod 1000000007
using namespace std;
int n,date[N],T;
int ss[1024][1024],st[1024][1024],fs[1024][1024],ft[1024][1024],ans;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&date[i]);
memset(ss,0,sizeof(ss));memset(st,0,sizeof(st));memset(fs,0,sizeof(fs));memset(ft,0,sizeof(ft));
ss[0][0]=1;st[n+1][1023]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<1024;j++) fs[i][j^date[i]]=(fs[i][j^date[i]]+ss[i-1][j])%mod;
for(int j=0;j<1024;j++) ss[i][j]=(ss[i-1][j]+fs[i][j])%mod;
}
for(int i=n;i;i--){
for(int j=0;j<1024;j++) ft[i][j&date[i]]=(ft[i][j&date[i]]+st[i+1][j])%mod;
for(int j=0;j<1024;j++) st[i][j]=(st[i+1][j]+ft[i][j])%mod;
}
ans=0;
for(int i=1;i<n;i++){
ss[i][0]--;//!!!
for(int j=0;j<1024;j++)
ans = ( ans + 1ll*ss[i][j]*ft[i+1][j] )%mod;
}
printf("%d\n",ans);
}
return 0;
}
/*
2
3
1 2 3
4
1 2 3 3
*/
文章浏览阅读991次。2019独角兽企业重金招聘Python工程师标准>>> ..._dockercompose thinkphp
文章浏览阅读1.4k次。java去除字符串中的空格、回车、换行符、制表符。_java去掉json字符串空格换行
文章浏览阅读8.9k次，点赞124次，收藏434次。「学习笔记」JavaScript基础前言最近一直研究JavaScript内容，遂把这一阶段的学习内容整理成笔记，巩固所学知识，同时也会参考一些博客，书籍上的内容，查漏补缺，给自己充充电????????文章内容如有错误，欢迎指正批评️️工欲善其事，必先利其器，为了提高开发效率，选用VScode。 管理-设置-常用设置-字体Consolas, '微软雅黑 Light', monospace Chinese汉化Vscode Prettier格式化代码(缩进2格)_var num=1; var result=num-- + --num + ++num +num++ +num++; console.log(resul
文章浏览阅读1.6k次，点赞36次，收藏17次。实现了一个基于Scapy库的科研级TCP端口存活探测工具，通过动态生成并发送TCP SYN数据包，检测指定IP地址范围内的主机端口是否活跃。该工具采用了多线程并发技术以提高扫描效率，并提供了命令行参数接口方便用户自定义探测目标和参数。同时，为确保运行过程中的日志管理，代码中对Scapy库的日志输出进行了严格控制。_使用多线程和scapy实现syn端口扫描
文章浏览阅读8.2w次，点赞68次，收藏574次。1.概述CAN-FD：可以理解成CAN协议的升级版，只升级了协议，物理层未改变。CAN与CAN-FD主要区别：传输速率不同、数据长度不同、帧格式不同、ID长度不同。由传统CAN转移到CANFD比较方便2. 传输速率不同CAN：最大传输速率1Mbps。CAN-FD：速率可变，仲裁比特率最高1Mbps（与CAN相同），数据比特率最高8Mbps。3. 数据域长度不同CAN：一帧数据最长8字节CAN-FD：一帧数据最长64字节。4. 协议内容改变—取消远程帧5. CANFD报文_canfd和can的区别
文章浏览阅读5.9k次，点赞6次，收藏31次。虚拟机与主机互ping一、前期准备1、虚拟机VMware1.1虚拟网络编辑器1.2 设置2、主机二、得到双方的ip地址1、主机2、虚拟机的ip ：输入ifconfig三、互相ping1、主机ping2、虚拟机ping一、前期准备1、虚拟机VMware1.1虚拟网络编辑器1.2 设置2、主机二、得到双方的ip地址1、主机在cmd中输入ipconfig2、虚拟机的ip ：输入ifconfig三、互相ping1、主机ping2、虚拟机ping..._虚拟机ping通主机步骤
文章浏览阅读438次。其次，你得会找资料，电子书我一般去。_猿编程c4课程学什么
文章浏览阅读868次，点赞22次，收藏7次。1.背景介绍随着计算机图像处理技术的不断发展，图像生成已经成为了人工智能领域的一个重要研究方向。图像生成的主要目标是通过计算机算法生成具有视觉吸引力和艺术价值的图像。在过去的几年里，随着深度学习和神经网络技术的兴起，图像生成的技术已经取得了显著的进展。在深度学习领域，图像生成通常涉及到一些常见的技术，如生成对抗网络(GANs)、变分自动编码器(VAEs)和循环生成对抗网络(CGANs)等。...
文章浏览阅读1.2k次，点赞2次，收藏2次。OS: Android 8.1需求分析1、禁止系统来电铃声，提供接口给客户自己播放铃声2、禁止系统拉起来去电页面(InCallActivity),消息通知客户拉起自己的来去电页面3、禁止来电消息 Notification 显示(包括未接来电)，点击跳转至 InCallActivity(未接来电消息可通知客户或者将 PendingIntent 改成客户的)上代码1、系统来电铃声播放在 T..._禁止com.android.incallui.incallactivity被teams拉起
注意：有负权的可能没有最短路，我们最外面循环了k次，他的含义是最多经过k条边的最短路，因此若循环超过该次数说明有环，这样子就是有负环了，但是有负环不一定说明答案不存在比方说一个与答案路径无关的负环，因此一般无法用该算法判断。同时维护cnt[x]表示当前最短路的边数，我们cnt[x]=cnt[t]+1，若有cnt[x]>=n，说明有了负环。我们让s表示当前已经确定的最短距离的点，我们找到一个不在s中的距离最近的点t，并用t来更新其他的点。实现：循环n次，每一次循环所有边并更新。
半监督节点分类：标签传播和消息传递
文章浏览阅读839次。为什么要学习 JavaJava这门语言如今是互联网行业炙手可热的编程语言，像阿里、美团这些大厂，技术体系都是建立在 Java 之上。这些大厂又是很多新兴互联网企业的技术风向标，因此 Jav..._java 技术编年史