[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;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ]11048(python)

python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다