hihocoder 1279（状压）
坑爹的题目。不过不能说不是一道挺好的题目。
坑主要坑在，妹的我一样的复杂度，写的姿势略差了点然后就一直超时。
比赛的时候我还直接就看错题目，把AND运算看成了OR。。。还敲完交了一发。
这题很容易想到:
因为给出的数字只有13位，所以每位用2位二进制表示。
如：
00 1的个数为偶数，最后的结果为0
01 1的个数为奇数，最后的结果为0
10 1的个数为偶数，最后的结果为1
11 1的个数为奇数，最后的结果为1
这样就可以转移求出最后的结果。然而这样做的复杂度是O(50*2^26)>1e9. 肯定不行。
仔细想想我们可以发现，当出现了0以后结果一定为0。这样用2位二进制位表示这个信息有些多余了。我们可以用三进制0,1,2和多余附加的一个标志位来表示这种信息。
如果某一位一直都是1则用0表示，如果出现了0，则用1，2分别代表出现奇数个1和偶数个1。 再配上附加的标志位来记录当前为止已加入数个数的奇偶性。分析下就可以发现，这样是能够把每一种情况表示出来的。
原先得用2^26=67108864种状态表示，现在只需要2*3^13=3188646. 直接就相差了20倍。wonderful！
然后剩下来还有一个关键问题，怎样将转移的O(13)->O(1)
PS：我原先的思想是，预处理，对于2*3^13的每种状态对应2^26某一种。结果一直TLE，这种做法会有比较大的内存消耗，而且预处理时间也较长。
可以预处理7位的所有情况，也就是把13位分成两半，因为对这两半的操作都是一样的，所以只需要预处理一半就行了，然后空间消耗变得非常小，转移操作变成O(1).
Rikka with Sequence
描述
众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：
勇太有n个[0,8192)中的整数，现在六花可以从中选出若干个数（不可以不取），她的方案需要满足她选出的所有数的异或和恰好等于它们AND（二进制与运算）起来的值，现在勇太想让六花求出满足条件的方案数。
当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
输入
第一行一个整数n，接下来一行里n个整数。
1<=n<=50
输出
输出一行表示答案。
- 样例输入
-
3
1 1 1 - 样例输出
-
4
//
// main.cpp
// hiho19
//
// Created by 陈加寿 on 16/3/20.
// Copyright © 2016年 chenhuan001. All rights reserved.
// #include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <time.h>
#include <math.h>
#include <algorithm>
using namespace std; #define K 8200 int g[];
long long dp[][][];
int chg[][][];
int chg1[][][]; void init()
{
int save[];
memset(save,,sizeof(save));
for(int i=;i<;i++)
{
for(int j=;j<(<<);j++)
{
for(int p=;p<;p++)
{
//然后你想怎么搞就怎么搞吧。
int tmp1=,tmp2=;
for(int k=;k<;k++)
{
if(save[k] == )
{
tmp1 |= (<<k);
}
}
for(int k=;k<;k++)
{
if(save[k] == )
{
if(p) tmp2|=(<<k);
}
else if(save[k] == ) tmp2|=(<<k);
}
tmp1 &= j;
tmp2 ^= j;
//然后再转变回去。
int tmp=;
int sum=;
for(int k=;k<;k++)
{
if( (tmp1&(<<k))!= )
{
;
}
else if( (tmp2&(<<k))!= )
{
sum += tmp;
}
else if( (tmp2&(<<k))== )
{
sum += *tmp;
}
tmp *=;
}
chg[i][j][p] = sum;
chg1[i][j][p] = (chg[i][j][p]/)*;
}
} int tj=;
save[tj]++;
while(save[tj]>=)
{
save[tj+]++;
save[tj]=;
tj++;
} }
} //是与运算
//clock_t be,ed;
//void checktime()
//{
// ed=clock();
// cout<<(double)(ed-be)/CLOCKS_PER_SEC<<endl;
// be=clock();
//
//}
int main() {
//看错题目？？？ 不思考看题解？？？ 你是SB吗
int n;
cin>>n; // 我真是日了狗了
for(int i=;i<n;i++)
{
scanf("%d",g+i);
//13 = 1594323(nn,13);
//1594323 = 1594323(1594323,tcnt);
}
// if(13 == 0)
// {
// cout<<((1LL)<<n)-1<<endl;
// return 0;
// } //be=clock();
init();
//checktime(); int a=;
memset(dp,,sizeof(dp));
dp[a][][] = ; for(int i=;i<n;i++)
{
memset(dp[a^],,sizeof(dp[a^])); int up=g[i]>>;//这个应该是移6位吧
int down = g[i]&((<<)-); int j1=,j2=;
for(int j=;j<;j++)
{
j2= j/; j1=j%;
for(int p=;p<;p++)
{
//dp[a^1][j] += dp[a][j];
int sum=;
if(dp[a][j][p] != )
{
dp[a^][j][p] += dp[a][j][p];
sum = chg1[j2][up][p]+chg[j1][down][p];
dp[a^][sum][p^] += dp[a][j][p];
} }
// j2++;
// if(j2>=(2187))
// {
// j2=0;j1++;
// }
}
a = a^;
}
//checktime(); long long ans=;
int save[];
memset(save, , sizeof(save));
for(int j=;j<;j++)
{
for(int p=;p<;p++)
{
int flag=;
for(int k=;k<;k++)
if(save[k]==)
{
flag=;
break;
}
else if(save[k]== && p==)
{
flag=;
break;
} if(flag==) ans += dp[a][j][p];
}
int tj=;
save[tj]++;
while(save[tj]>=)
{
save[tj+]++;
save[tj]=;
tj++;
}
}
//checktime(); cout<<ans<<endl; return ;
}
最新文章
- VS2013全攻略
- Utility2：Appropriate Evaluation Policy
- PHP的魔法方法__set() __get()
- 当编译AFNetworking 2.0时出现了Undefined symbols for architecture i386
- 复制 VS 复用 -04
- Codeforces Round #277 (Div. 2)
- Linux系统调用（转载）
- asp.net 字符帮助类 类型转换类
- 一键搞定Java桌面应用安装部署 —— exe4j + Inno Setup 带着JRE, 8M起飞
- maven setting配置
- windows composer安装
- laravel整合JWT遇到的问题及解决方案
- 在deepin上安装YouCompleteMe
- vue-router的学习
- MySql+EF <二>
- C#调用java方法踩坑记
- 阿里云oss，简单上传
- Django1.11加载静态文件
- asp.net core 基于角色的认证登陆
- ubuntu14.04 配置g++工具，并运行一个简单的c++文件