正題

題目鏈接:https://jzoj.net/senior/#main/show/3889

---

題目大意

一個序列$n$，求兩個集合$S,T\in [1..n]$使得$a_x(x\in S)$的$xor$和就是$a_y(y\in T)$的$and$和，且$x<y(x\in S,y\in T)$，求集合對數(shù)。

---

解題思路

就是把其分成兩部分，然后段的$and$和異或前半段為$0$。
設(shè)$f_{i,j,0/1/2}$。$0$表示前面的都沒選擇，$1$表示到目前的$and$和為$j$，$2$表示到目前$and$的異或的和。

然后要用高精度。

---

$code$

#pragma GCC optimize(2) %:pragma GCC optimize(3) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1100,W=1024,P=42,p=1e9; struct Big_int{int a[P]; }f[2][W][3]; int n,a[N]; void Add(Big_int &a,Big_int &b) {int g=0;for(int i=0;i<P;i++){a.a[i]+=b.a[i]+g;g=a.a[i]/p;a.a[i]%=p;}return; } void print(Big_int a){int w=P;while(w&&!a.a[--w]);printf("%d",a.a[w]);while(w){w--;printf("%09d",a.a[w]);} } int main() {//printf("%d",sizeof(f)/1024);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);f[~n&1][W-1][0].a[0]=1;for(int i=n;i>=1;i--){memset(f[i&1],0,sizeof(f[i&1]));for(int j=0;j<W;j++){Add(f[i&1][j][0],f[~i&1][j][0]);Add(f[i&1][j][1],f[~i&1][j][1]);Add(f[i&1][j][2],f[~i&1][j][2]);Add(f[i&1][j&a[i]][1],f[~i&1][j][0]);Add(f[i&1][j&a[i]][1],f[~i&1][j][1]);Add(f[i&1][j^a[i]][2],f[~i&1][j][1]);Add(f[i&1][j^a[i]][2],f[~i&1][j][2]);}}print(f[1][0][2]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj3889-序列问题【dp,高精度】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。