序列问题

DP 高精度

题面

现有一个长度为$n$的序列$\{ai\}$,找出两个非空的集合$S$、$T$。
这两个集合要满足以下的条件:

• 两个集合中的元素都为整数,且都在$[1, n]$里,即$S_i,T_i\in[1, n]$。
• 对于集合$S$中任意一个元素$x$,集合$T$中任意一个元素$y$,满足$x<y$。
• 对于大小分别为$p,q$的集合$S$与$T$,满足
  $a[S_1]\bigoplus a[S_2]\bigoplus a[S_3] ... \bigoplus a[s_p] = a[t_1]\&a[t_2]\&a[t_3] ...\&a[t_q]$

询问一共有多少对这样的集合$(S,T)$。

• $60pts$ $n\leq100$
• $100pts$ $n\leq1000,a_i<1024$

解析

$n\leq100$

直接设$lt[i][j]$表前$i$个数中 已取数 异或和 为$j$的方案数。
$rt[i][j]$同理。
然后枚举分割点和相等值统计答案。
注意一下开始分割点要放在取了的数上，否则会计重。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1024;
int n,a[N];
ll lt[1200][1200],rt[1200][1200][2],ans;
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
int main()
{
  freopen("sequence.in","r",stdin);
  freopen("sequence.out","w",stdout);
  n=gi();
  fp(i,1,n) a[i]=gi();
  fp(i,1,n) lt[i][a[i]]=1,rt[i][a[i]][1]=1;
  fp(i,1,n)
    fp(j,0,N)
    {
      lt[i][j^a[i]]+=lt[i-1][j];
      lt[i][j]+=lt[i-1][j];
    }
  fq(i,n,1)
    fp(j,0,N)
    {
      rt[i][j&a[i]][1]+=rt[i+1][j][1]+rt[i+1][j][0];
      rt[i][j][0]+=rt[i+1][j][1]+rt[i+1][j][0];
    }
  fp(i,1,n)
    fp(j,0,N)
    ans+=lt[i-1][j]*rt[i][j][1];
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}

复杂度$O(1024*n*2)$

$n\leq1000$

注意到$lt[i][j]$的值可能以$3!$的比例呈现。。。
所以我们需要高精。。。
然而我们发现强行高精乘效率很低。
于是我们要把$dp$方程式转化一下。
设$dp[i][j][0/1]$表示第$i-n$个数中，已取数"and和"（$0$）或"xor和"$\&$"and和"（$1$）为$j$的方案数。
应选择倒推，这样最后的合法情况中$j$一定为$0$。
则
$dp[i][j\& a[i]][0]+=dp[i+1][j][0]$
$dp[i][j][0]+=dp[i+1][j][0]$
$dp[i][j\bigoplus a[i]][1]+=dp[i+1][j][1]+dp[i+1][j][0]$
$dp[i][j][1]+=dp[i+1][j][1]$
(注意短式不能与长式合并，因长式中第二位取值受到限制）
答案在$dp[1][0][1]$中。
这样只用高精加即可。
同时，如果把$dp$数组转为高精，就需要滚动以省空间。
滚动前：

  n=gi();
  fp(i,1,n) a[i]=gi();
  fp(i,1,n) dp[i][a[i]][0]=1;
  fq(i,n,1)
    fp(j,0,1023)
    {
      dp[i][j&a[i]][0]+=dp[i+1][j][0];
      dp[i][j^a[i]][1]+=dp[i+1][j][1]+dp[i+1][j][0];
      dp[i][j][0]+=dp[i+1][j][0];
      dp[i][j][1]+=dp[i+1][j][1];
    }
  printf("%lld\n",dp[1][0][1]);

滚动后：
注意到$dp$数组进行转移前要先集体赋值，否则可能会加上上两次的方案。并且赋值为$1$改为$++$。

 n=gi();
  fp(i,1,n) a[i]=gi();
  fq(i,n,1)
    {
      re int now=i&1,las=(i&1)^1;
      fp(j,0,N-1) dp[now][j][0]=dp[las][j][0],dp[now][j][1]=dp[las][j][1];
      dp[now][a[i]][0]++;
      fp(j,0,N-1)
      {
        dp[now][j&a[i]][0]+=dp[las][j][0];
        dp[now][j^a[i]][1]+=dp[las][j][1]+dp[las][j][0];
    }
    }
  cout<<dp[1][0][1]<<endl;

更加毒瘤

发现出题人很卡复杂度，高精运算复杂度过高还是会$GG$。
于是我们需要压位。
并且如果高精数位数很大速度也很慢！！！
于是压九位，高精数开五十位即可。
注意一下输出方式。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1024;
int n,a[N];
class BigInteger
{
public:
  int sz,num[50];
  BigInteger(){sz=1;memset(num,0,sizeof(num));}
  void print()
  {
    fq(i,sz,1) if(i^sz) printf("%09d",num[i]);else printf("%d",num[i]);
    puts("");
  }
}dp[2][1200][2],ysn;
BigInteger operator + (BigInteger A,BigInteger B)
{
  BigInteger Ans;
  re int s=max(A.sz,B.sz);
  Ans.sz=s;
  fp(i,1,s) Ans.num[i]=A.num[i]+B.num[i];
  fp(i,1,s)
    if(Ans.num[i]>999999999)
      {
    Ans.num[i+1]+=Ans.num[i]/1000000000;
    Ans.num[i]=Ans.num[i]%1000000000;
      }
  if(Ans.num[s+1]) ++Ans.sz;
  return Ans;
}
il ll gi() 
{
  re ll x=0,t=1;
  re char ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void wri(re int x)
{
  if(x<0) putchar('-'),x=-x;
  if(x>9) wri(x/10);
  putchar(x%10+'0');
}
int main()
{
  freopen("sequence.in","r",stdin);
  freopen("sequence.out","w",stdout);
  n=gi();ysn.num[1]=1;ysn.sz=1;
  fp(i,1,n) a[i]=gi();
  fq(i,n,1)
    {
      re int now=i&1,las=(i&1)^1;
      fp(j,0,N-1) dp[now][j][0]=dp[las][j][0],dp[now][j][1]=dp[las][j][1];
      dp[now][a[i]][0]=dp[now][a[i]][0]+ysn;
      fp(j,0,N-1)
      {
        dp[now][j&a[i]][0]=dp[now][j&a[i]][0]+dp[las][j][0];
        dp[now][j^a[i]][1]=dp[now][j^a[i]][1]+dp[las][j][1]+dp[las][j][0];
      }
    }
  dp[1][0][1].print();
  fclose(stdin);
  fclose(stdout);
  return 0;
  }