[DP 블록 하위 집합 열거] UOJ#300.[CTSC 2017] 지프트.

2908 단어 DP
DP 마이그레이션은 쓰기 쉽습니다.
폭력은 O(318)입니다.
각 이진수를 전 9위와 후 9위로 나누면 블록 통계의 복잡도는 O(69)이다
#include 
#include 
#include 

using namespace std;

const int N=333333,P=1e9+7;

int n,ans,a[N],f[N];

inline int Query(int x){
  int a=x&~511,b=(~x)&511,ret=0;
  for(int i=b;i;i=(i-1)&b)
    ret=(ret+f[a|((~i)&511)])%P;
  return (ret+f[a|511])%P;
}

inline void Add(int x,int y){
  int a=x>>9,b=x&511;
  for(int i=a;i;i=(i-1)&a)
    f[i<<9|b]=(f[i<<9|b]+y)%P;
  f[b]=(f[b]+y)%P;
}

int main(){
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n;i++){
    int cur=Query(a[i])+1;
    ans=(ans+cur)%P;
    Add(a[i],cur);
  }
  printf("%d
"
,(ans+P-n)%P); return 0; }

좋은 웹페이지 즐겨찾기