P4604 [WC2017]挑战

https://www.luogu.com.cn/problem/P4604
怎么最近一直在做乐子题啊（

第一个就基排，然后复杂度大概是 \(O((n+BASE)\log_{BASE}w)\)？然后选 \(BASE=256\) 可以让基排用的那个桶塞进一级缓存里，就跑的很快
然后没怎么卡就过了这一个

第二个朴素 \(O(nq)\) 大概率是没戏，也没什么数据结构能维护，然后发现可以压位，两个序列分别预处理然后每次与一下再 __builtin_popcountll 就行，于是除以了 \(w=64\) 的常数，就过了

第三个就是 dp，每往后一个如果是左括号就 \(f_j=f_{j-1}\)，右括号就 \(f_j=f_{j+1}\)，问号就 \(f_j=f_{j-1}+f_{j+1}\)
然后又意识到考虑到第 \(i\) 位（编号从 \(0\) 开始）的时候，如果 \(j> \min(i+1,n-i)\)，那这个状态就已经寄了，不用管他，这样一来就除以了一个 \(4\) 的常数
此时已经只有最后两个点过不去了
又仔细考虑了一下发现只有 \(i\equiv j\bmod 2\) 的状态不是 \(0\)，然后就只存这些不是 \(0\) 的状态就行了，转移稍微变一变（讨论 \(i\) 的奇偶性），常数又除以了要给 \(2\)，就能过了

似乎不需要什么循环展开之类的奇技淫巧（
代码是 c 的

#include 
#include 
#include 

#define bool int
#define true 1
#define false 0

typedef unsigned int u32;
typedef unsigned long long u64;


int min(int a,int b);
inline int min(register int a,register int b){return a> 17;
        x ^= x << 5;
    }

    return printf("%u\n", ret), 1;
}

//inline u32 nextInteger(u32 x) {
//    x ^= x << 13;
//    x ^= x >> 17;
//    x ^= x << 5;
//    return x;
//}

// ===== header ======

#define MAX_DIGIT 4
#define BASE 255
void Sorting_main() {
    int n;
    u32 seed;
    scanf("%d%u", &n, &seed);
    u32 *a = malloc(n * sizeof(u32));
    for (register int i = 0; i < n; i++) {
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        a[i] = seed;
    }

    // sort(a, n);
    u32 *cnt=malloc((BASE+1)*sizeof(u32)),*tmp=malloc(n*sizeof(u32));
    __builtin_memset(cnt,0,(BASE+1)*sizeof cnt[0]);
    
   	for(register int j=0;j>8)&BASE]+=1;
   	for(register int j=1;j<=BASE;j++) cnt[j]+=cnt[j-1];
   	for(register int j=n-1;~j;j--) cnt[(tmp[j]>>8)&BASE]-=1,a[cnt[(tmp[j]>>8)&BASE]]=tmp[j];
	__builtin_memset(cnt,0,(BASE+1)*sizeof cnt[0]);
	
   	for(register int j=0;j>16)&BASE]+=1;
   	for(register int j=1;j<=BASE;j++) cnt[j]+=cnt[j-1];
   	for(register int j=n-1;~j;j--) cnt[(a[j]>>16)&BASE]-=1,tmp[cnt[(a[j]>>16)&BASE]]=a[j];
	__builtin_memset(cnt,0,(BASE+1)*sizeof cnt[0]);
	
   	for(register int j=0;j>24)&BASE]+=1;
   	for(register int j=1;j<=BASE;j++) cnt[j]+=cnt[j-1];
   	for(register int j=n-1;~j;j--) cnt[(tmp[j]>>24)&BASE]-=1,a[cnt[(tmp[j]>>24)&BASE]]=tmp[j];
    
	output_arr(a, n * sizeof(u32));
}
#undef MAX_DIGIT
#undef BASE

void set(u64 (*f)[14063],int pos);
inline void set(u64 f[][14063],int pos){
	for(register int i=0,j;i<64&&i<=pos;i++){
		j=pos-i;
		f[i][j>>6]|=1ll<<(j&63);
	}
}
u64 f1[64][14063],f2[64][14063];
void Game_main() {
    int n, q;
    scanf("%d%d", &n, &q);

    char *s1 = malloc((n + 1) * sizeof(char));
    char *s2 = malloc((n + 1) * sizeof(char));
    scanf("%s%s", s1, s2);
    for(register int i=0;i>6),*b=f2[y&63]+(y>>6);
		register int o=0,ll=len>>6;
		while(ll--){
			o+=__builtin_popcountll(*a&*b);
			a+=1;b+=1;
		}
		ans[i]=o+__builtin_popcountll(*a&*b&((1ll<<(len&63))-1));
//			printf(" ans [%d] = %d\n",i,ans[i]);
    }

    // solve(n, q, s1, s2, q_x, q_y, q_len, anss);

    output_arr(ans, q * sizeof(u32));
}

#define N 266666
u32 __f[N*2+10],*f=__f+N+5;
void Parentheses_main() {
    int n;
    scanf("%d", &n);

    char *str = malloc((n + 1) * sizeof(char));
    scanf("%s", str);

    f[0]=1;
    for(register int i=0,len;i>=1;len++;
    	if(str[i]=='?'){
    		if(i&1) for(register int j=len;j;j--) f[j]+=f[j-1];
    		else for(int j=0;j