题目描述
小H是个善于思考的学生，她正在思考一个有关序列的问题。
她的面前浮现出了一个长度为n的序列{ai}，她想找出两个非空的集合S、T。
这两个集合要满足以下的条件：
1. 两个集合中的元素都为整数，且都在 [1, n] 里，即Si，Ti ∈ [1, n]。
2. 对于集合S中任意一个元素x，集合T中任意一个元素y，满足x < y。
3. 对于大小分别为p, q的集合S与T，满足
a[s1] xor a[s2] xor a[s3] ... xor a[sp] = a[t1] and a[t2] and a[t3] ... and a[tq].
小H想知道一共有多少对这样的集合(S,T)，你能帮助她吗？
输入格式
第一行，一个整数n
第二行，n个整数，代表ai。
输出格式
仅一行，表示最后的答案。
样例输入
4
1 2 3 3
样例输出
4
样例解释
S = {1,2}, T = {3}， 1 ^ 2 = 3 = 3 (^为异或)
S = {1,2}, T = {4}, 1 ^ 2 = 3 = 3
S = {1,2}， T = {3，4} 1 ^ 2 = 3 & 3 = 3 （&为与运算）
S = {3}， T = {4} 3 = 3 = 3
数据范围
30%: 1 <= n <= 10
60%: 1 <= n <= 100
100%: 1 <= n <= 1000, 0 <= ai < 1024
题解
我觉的这是一道很考综合能力的题。不过事实证明，我很弱……
首先我们可以想出一种两边分开的dp：f[i][j]和g[i][j]表示前i个xor值为j，后i个and值为j的方案数， 随后枚举分界点k来求总方案数。复杂度O(n * 1024 * 3)。最终分数：60分。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n,a[1002];
ll f[1002][3000],g[1002][3000],add[1002][3000];
ll ans;
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
void dp()
{
int i,j;
f[1][a[1]]=1; add[1][a[1]]=1;
for(i=2;i<=n;i++)
{f[i][a[i]]++; add[i][a[i]]++;
for(j=0;j<3000;j++)
{if(f[i-1][j]>0)
{f[i][j^a[i]]+=f[i-1][j]; add[i][j^a[i]]+=f[i-1][j];
f[i][j]+=f[i-1][j];
}
}
}
g[n][a[n]]=1;
for(i=n-1;i>0;i--)
{g[i][a[i]]++;
for(j=0;j<3000;j++)
{if(g[i+1][j]>0)
{g[i][j]+=g[i+1][j];
g[i][j&a[i]]+=g[i+1][j];
}
}
}
for(i=1;i<n;i++)
for(j=0;j<3000;j++)
ans+=add[i][j]*g[i+1][j];
printf("%I64d\n",ans);
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
init(); dp();
return 0;
}
那天在考试的时候，我觉得这样就能A了。然而，这一题没有“取mod”操作，剩下的40分需要高精度，这一点我没有想到，所以这道题的一个收获就是：没有取mod的题要考虑它结果的范围。
那么既然需要高精度，我们肯定不能再在上面那种做法上“数组+一维”，这样空间不允许。所以，我们需要将空间也优化，并且像上面那种dp，又乘又加的不得写死……这里提出一种新的dp方程：因为“两个数相等就相当于两个数的xor为0”。设 f[i][j][k=0..2]代表从后往前处理到第 I 个数，如果 k = 1代表and值为j,如果k = 2代表xor值为 j,如果k = 0则代表之前一个元素都没取。所以很容易得到方程：
f[i][j][0] = f[i + 1][j][0]——————————其实只有j=1023且k=0时f[i][j][0]才有值且恒为1.
f[i][j & ai][1] = f[i + 1][j][1] + f[i + 1][j][0] + f[i + 1][j & ai][1]
f[i][j ^ ai][2] = f[i + 1][j][1] + f[i + 1][j][2] + f[i + 1][j ^ ai][2];
最后f[1][0][2]就是答案, 复杂度为O(n * 1024 * 3)这样统计答案就只需要高精加了。不过为什么说我弱呢？是因为我自己写的高精加只有70分。原因大概是我重载+号的算法里有许多赋值的操作。而且其他的一些细节常数很大。这里蛮贴一下。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define M 1024
#define N 1000000000
using namespace std;
int n,a[1002];
struct shu{int s[50],l;} f[2][1030][3];
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
shu operator + (const shu &x,const shu &y)
{
shu ans;
memset(ans.s,0,sizeof(ans.s));
int i;
ans.l=max(x.l,y.l);
for(i=1;i<=ans.l;i++)
{ans.s[i]+=x.s[i]+y.s[i];
if(ans.s[i]>=N)
{ans.s[i+1]++;
ans.s[i]%=N;
}
}
if(ans.s[ans.l+1]>0) ans.l++;
return ans;
}
void PRINT(const shu &x)
{
int i;
printf("%d",x.s[x.l]);
for(i=x.l-1;i>0;i--) printf("%09d",x.s[i]);
printf("\n");
}
void dp()
{
int i,j,k,now=0,next,vx,vy;
f[0][1023][0].s[1]=1; f[0][1023][0].l=1;
for(i=n;i>0;i--)
{next=now^1;
for(j=0;j<M;j++)
for(k=0;k<3;k++)
f[next][j][k]=f[now][j][k];
for(j=0;j<M;j++)
{vy=j&a[i]; vx=j^a[i];
f[next][vy][1]=f[next][vy][1]+f[now][j][0];
f[next][vy][1]=f[next][vy][1]+f[now][j][1];
f[next][vx][2]=f[next][vx][2]+f[now][j][1];
f[next][vx][2]=f[next][vx][2]+f[now][j][2];
}
now=now^1;
}
PRINT(f[now][0][2]);
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
init(); dp();
return 0;
}
所以比较好的方法是，重载+=，并且将其写入高精度专门的结构体内。当然常数问题自己解决，这样就能过了。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define M 1024
#define N 100000000
using namespace std;
int n,a[1002];
struct shu
{
int s[50],l;
void operator += (const shu &x)
{
int i;
l=max(x.l,l);
for(i=1;i<=l;i++)
{s[i]+=x.s[i];
if(s[i]>=N)
{s[i+1]++; s[i]%=N;}
}
if(s[l+1]>0) l++;
}
}
f[2][1030][3];
void init()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
}
void PRINT(const shu &x)
{
int i;
printf("%d",x.s[x.l]);
for(i=x.l-1;i>0;i--)
printf("%08d",x.s[i]);//这种写法很好，大概是压x位写“%0xd”
printf("\n");
}
void dp()
{
int i,j,k,now=0,next,vx,vy;
f[0][1023][0].s[1]=1; f[0][1023][0].l=1;
for(i=n;i>0;i--)
{next=now^1;
for(j=0;j<M;j++)
for(k=0;k<3;k++)
f[next][j][k]=f[now][j][k];
for(j=0;j<M;j++)
{vy=j&a[i]; vx=j^a[i];
f[next][vy][1]+=f[now][j][0];
f[next][vy][1]+=f[now][j][1];
f[next][vx][2]+=f[now][j][1];
f[next][vx][2]+=f[now][j][2];
}
now=now^1;
}
PRINT(f[now][0][2]);
}
int main()
{
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
init(); dp();
return 0;
}