동적 기획 훈련의 6

https://www.luogu.org/problem/P2467

이것은 좋은 문제다

제목 설명

1-n 배열로 구성된 파동수열의 개수를 구하다
분석은 우선 dp가 틀림없다. 디자인 방안을 고려하면
pp[i, j]는 1-i의 배열로 마지막 j의 방안 수를 나타낸다
dp[i, j]는 dp[i-1, k]에 해당한다. 중원 배열이 j보다 큰 것은 모두 1을 더하고 j를 끝에 꽂은 후의 새로운 합법적인 배열 방안수.
유사 테스트 10.7의 배열 문제
답은'M'형과'W'형이 있는데 분명히 방안 수는 같다. 여기는'W'형만 생각하고 마지막에 답안*2만 생각하면 된다.
이때 당신은 왜 짝수는 매거[1,j-1]이고 홀수는 매거[j,i-1]인지 의문이 생길 수 있습니다.
'W'형태만 고려하기 때문에 홀수는 반드시 산봉우리이고 짝수는 반드시 산골짜기이다.
그래서 홀수 매거는 반드시 앞자리의 수보다 크고 짝수 매거는 반드시 앞자리의 수보다 작아야 한다

#include
#include
#include
using namespace std;
#define N 4211
#define M(a) ((a)<=mod?(a):(a-mod))
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,mod;
int dp[N][N],ans=0;
int main(){
    n=read(),mod=read();
    for(int i=1;i<=n;i++){
        dp[1][i]=1;
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i&1){
                for(int k=j;k

다음 코드는 트리 배열로 유지되며 실제로 접두사와 함께 사용할 수 있습니다. (코드는 내가 쓴 것이 아닙니다. 그렇지 않으면 접두사와 같습니다) 그리고 O2를 켜야 코드 bystd를 통과할 수 있습니다.

#include
#include
#include
using namespace std;
#define N 4211
#define M(a) ((a)<=mod?(a):(a-mod))
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,mod;
int dp[N][N],ans=0;
int b[N];
int lowbit(int x){
    return x&(-x);
}
void Add(int x,int d){
    while(x<=n){
        b[x]=M(b[x]+d);
        x+=lowbit(x);
    }
}
int Ask(int x){
    int ans=0;
    while(x){
        ans=M(ans+b[x]);
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    n=read(),mod=read();
    for(int i=1;i<=n;i++){
        dp[1][i]=1;
        Add(i,1);
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i&1){
                if(i>j){
                    dp[i][j]=M(Ask(i-1)-Ask(j-1)+mod);
                }
            }
            else{
                dp[i][j]=Ask(j-1);
            }
        }
        memset(b,0,sizeof(b));
        for(int j=1;j<=n;j++){
            Add(j,dp[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        ans=M(ans+dp[n][i]);
    } 
    cout<<2*ans%mod<