rctc:

模拟赛T1map大暴力水过了...T3在GTX大佬一句“SPFA就好了呀”下乱口胡了一个SPFA里面套个DP竟然也A了...感觉RP用光了

题目描述

 

小 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)，你能帮助她吗？

 

题解：

　　看数据范围显然是DP无疑了，但是考试的时候感觉T3更可做，于是先做了T3，T2只打了暴力（其实想DP的时候还是推出过一个错误的转移式子的，幸好没肝T2）

　　两个数相等就相当于两个数的 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]

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]

　　这是官方题解...上面的转移方程应该看得懂了...然后刷表法刷去就好了

　　注意①：转移的时候因为and操作是无法“逆”过来的，所以我们把原数组倒过来存即可

　　注意②：这里当前状态仅与另外一个状态有关，显然可以把i的那一维压掉

　　恶心的是，这样只有60分...发现爆long long了

　　然而尝试了unsigned long long ,__int128,unsigned __int128均是60分

　　于是只好打起了高精度

　　然后,神TM。。。TLE了，出题人有毒啊*1

　　压位高精我按题解改的，题解压了9位，我想看看出题人到底有没有那么毒瘤，于是压了7位试试

　　没错7位是过不了的...出题人有毒啊*2

　　压了8位的代码：

 

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define writeln(x)  write(x),puts("")
 5 #define writep(x)   write(x),putchar(' ')
 6 using namespace std;
 7 inline int read(){
 8     int ans=0,f=1;char chr=getchar();
 9     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
11     return ans*f;
12 }void write(int x){
13     if(x<0) putchar('-'),x=-x;
14     if(x>9) write(x/10);
15     putchar(x%10+'0');
16 }const int M=1e8;
17 struct P{
18     int len,a[40];
19     P():len(1){memset(a,0,sizeof a);}
20     void operator +=(const P &x){
21         if(x.len>len) len=x.len;
22         for(int i=1;i<=len;++i){
23             a[i]+=x.a[i];
24             if(a[i]>=M) a[i]-=M,++a[i+1];
25         }if(a[len+1]) ++len;
26         return;
27     } 
28     void Print(){printf("%d",a[len]);
29         for(int i=len-1;i>=1;i--)printf("%08d",a[i]);
30     }
31 }f[2][2048][3];
32 int a[1005],n;
33 signed main(){
34     freopen("sequence.in","r",stdin);
35     freopen("sequence.out","w",stdout);
36     n=read();
37     for(int i=n;i>=1;--i) a[i]=read();
38     f[0][1023][0].a[1]=1;
39     for(int i=0;i<n;i++){
40         int npw=i&1^1;
41         for(int j=0;j<1024;++j)
42             for(int k=0;k<=2;k++)
43                 f[npw][j][k]=f[!npw][j][k];
44         for(int j=0;j<1024;j++){
45             int x=a[i+1]&j,y=a[i+1]^j;
46             f[npw][x][1]+=f[!npw][j][0],f[npw][x][1]+=f[!npw][j][1];
47             f[npw][y][2]+=f[!npw][j][1],f[npw][y][2]+=f[!npw][j][2];
48         }
49     }f[n&1][0][2].Print();
50     return 0;
51 }