[WC2017] 挑战

_H17_ · 2024-08-11 21:31:15 · 题解

概括

本题解包括：每道题的题目分析、卡常技巧、以及代码实现。

题目 1

题目分析

对于 Sorting 题目，我们肯定不能使用 STL 的 sort 函数，首先快速排序的时间复杂度是 O(n\log n)，其次 sort 并不自带卡常。

而且快速排序是期望 O(n\log n)，最坏是 O(n^2)。

sort 虽然内部有特判，会尽量稳定，但是时间仍是不可估量。

考虑相对稳定，但是空间高一点的基数排序。

基数排序（拿 10 是基数举例子，不知道什么是基数也可以忽略这个 10）的步骤是：

1. 从个位开始排序，高位不管；

2. 排十位，如果相同则不改变原有顺序；

3. 按照上一条的法则继续排序，直到结束。

为什么第二部不改变原有顺序？显然高位相同，按照低位大小继续排序，然而低位已经排好了，所以就高位相同维持现状。

如何对“个位”、“十位”进行排序？注意到每次数最大是 9，考虑使用桶排序。

桶完之后求前缀和就是当前数的排名。

举例说明

15 28 15 26 16 37
15 15 26 16 37 28
15 15 16 26 28 37

这样就完成了排序

最后解释什么是基数，“个位”、“十位”就是 10 个排一次，基数是 10。如果基数是 100 那就后两位排序一次，然后倒着继续排。

基数排序代码

这里以 10 为基数来给出代码（来自百度百科）。

void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = newint[n];
    int *count = newint[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}

不难发现，基数越大（在桶可以承受的范围内），然而基数是 2^k 时可以获得位运算的外挂。

当然，本题目是 32 位整数排序，尽量用 32 的约数当做 k。

选择 2^{16} 吗？不不不，这道题没那么简单，不光需要位运算的外挂，还需要 Cache 的外挂。

影响 Cache 速度的主要就是它的命中率，提高命中率至关重要。然而 Cache 非常小，2^{16} 作为桶肯定卡不进去，导致 Cache 频繁改变里面的元素，浪费时间。

于是选择 2^8 作为基数，既保证了基数比较大，又让它可以获得二进制的外挂，由于桶小还可以进入 Cache 获得超级提速。

卡常：循环展开、不要每次都把辅助数组 b 的值传回 a（就是示例的 10 是基数的那个代码的写法）。

如果传回：a->b=sort(a)->a=b 是一次。如果不传回 a->b=sort(a) 是一次，然而第二次改成 b->a=sort(b) 就相当于了传回，总共 4 次不要额外传回。

当然我们还可以预处理桶，预处理是无后效性的，不会受到前面变顺序影响，也不会影响后续。

代码实现

这里是我写的 Sorting 部分的代码：

namespace Sorting{
    int cnt0[256],cnt8[256],cnt16[256],cnt24[256];
    void init_data(u32* a,int n,u32 seed){
        for(int i=0;i<n;++i){
            seed=next_integer(seed),
            a[i]=seed,
            ++cnt0[seed&255],
            ++cnt8[seed>>8&255],
            ++cnt16[seed>>16&255],
            ++cnt24[seed>>24&255];
        }
        for(int i=1;i<256;++i)
            cnt0[i]+=cnt0[i-1],
            cnt8[i]+=cnt8[i-1],
            cnt16[i]+=cnt16[i-1],
            cnt24[i]+=cnt24[i-1];//预处理桶
    }
    void main(){
        int n;
        u32 seed;
        scanf("%d%u",&n,&seed);
        u32 *a=new u32[n],*b=new u32[n],*cur;
        init_data(a,n,seed);
        u32 repeat=n>>3,tmp;
        for(tmp=repeat,cur=a+n-1;tmp;--tmp){//1-8 基数排序
            b[--cnt0[cur[0]&255]]=cur[0],
            b[--cnt0[cur[-1]&255]]=cur[-1],
            b[--cnt0[cur[-2]&255]]=cur[-2],
            b[--cnt0[cur[-3]&255]]=cur[-3],
            b[--cnt0[cur[-4]&255]]=cur[-4],
            b[--cnt0[cur[-5]&255]]=cur[-5],
            b[--cnt0[cur[-6]&255]]=cur[-6],
            b[--cnt0[cur[-7]&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:b[--cnt0[cur[-6]&255]]=cur[-6];
            case 6:b[--cnt0[cur[-5]&255]]=cur[-5];
            case 5:b[--cnt0[cur[-4]&255]]=cur[-4];
            case 4:b[--cnt0[cur[-3]&255]]=cur[-3];
            case 3:b[--cnt0[cur[-2]&255]]=cur[-2];
            case 2:b[--cnt0[cur[-1]&255]]=cur[-1];
            case 1:b[--cnt0[cur[0]&255]]=cur[0];
        }
        for(tmp=repeat,cur=b+n-1;tmp;--tmp){//9-16 基数排序
            a[--cnt8[cur[0]>>8&255]]=cur[0],
            a[--cnt8[cur[-1]>>8&255]]=cur[-1],
            a[--cnt8[cur[-2]>>8&255]]=cur[-2],
            a[--cnt8[cur[-3]>>8&255]]=cur[-3],
            a[--cnt8[cur[-4]>>8&255]]=cur[-4],
            a[--cnt8[cur[-5]>>8&255]]=cur[-5],
            a[--cnt8[cur[-6]>>8&255]]=cur[-6],
            a[--cnt8[cur[-7]>>8&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:a[--cnt8[cur[-6]>>8&255]]=cur[-6];
            case 6:a[--cnt8[cur[-5]>>8&255]]=cur[-5];
            case 5:a[--cnt8[cur[-4]>>8&255]]=cur[-4];
            case 4:a[--cnt8[cur[-3]>>8&255]]=cur[-3];
            case 3:a[--cnt8[cur[-2]>>8&255]]=cur[-2];
            case 2:a[--cnt8[cur[-1]>>8&255]]=cur[-1];
            case 1:a[--cnt8[cur[0]>>8&255]]=cur[0];
        }
        for(tmp=repeat,cur=a+n-1;tmp;--tmp){//17-24 基数排序
            b[--cnt16[cur[0]>>16&255]]=cur[0],
            b[--cnt16[cur[-1]>>16&255]]=cur[-1],
            b[--cnt16[cur[-2]>>16&255]]=cur[-2],
            b[--cnt16[cur[-3]>>16&255]]=cur[-3],
            b[--cnt16[cur[-4]>>16&255]]=cur[-4],
            b[--cnt16[cur[-5]>>16&255]]=cur[-5],
            b[--cnt16[cur[-6]>>16&255]]=cur[-6],
            b[--cnt16[cur[-7]>>16&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:b[--cnt16[cur[-6]>>16&255]]=cur[-6];
            case 6:b[--cnt16[cur[-5]>>16&255]]=cur[-5];
            case 5:b[--cnt16[cur[-4]>>16&255]]=cur[-4];
            case 4:b[--cnt16[cur[-3]>>16&255]]=cur[-3];
            case 3:b[--cnt16[cur[-2]>>16&255]]=cur[-2];
            case 2:b[--cnt16[cur[-1]>>16&255]]=cur[-1];
            case 1:b[--cnt16[cur[0]>>16&255]]=cur[0];
        }
        for(tmp=repeat,cur=b+n-1;tmp;--tmp){//25-32 基数排序
            a[--cnt24[cur[0]>>24&255]]=cur[0],
            a[--cnt24[cur[-1]>>24&255]]=cur[-1],
            a[--cnt24[cur[-2]>>24&255]]=cur[-2],
            a[--cnt24[cur[-3]>>24&255]]=cur[-3],
            a[--cnt24[cur[-4]>>24&255]]=cur[-4],
            a[--cnt24[cur[-5]>>24&255]]=cur[-5],
            a[--cnt24[cur[-6]>>24&255]]=cur[-6],
            a[--cnt24[cur[-7]>>24&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:a[--cnt24[cur[-6]>>24&255]]=cur[-6];
            case 6:a[--cnt24[cur[-5]>>24&255]]=cur[-5];
            case 5:a[--cnt24[cur[-4]>>24&255]]=cur[-4];
            case 4:a[--cnt24[cur[-3]>>24&255]]=cur[-3];
            case 3:a[--cnt24[cur[-2]>>24&255]]=cur[-2];
            case 2:a[--cnt24[cur[-1]>>24&255]]=cur[-1];
            case 1:a[--cnt24[cur[0]>>24&255]]=cur[0];
        }
        output_arr(a,n*sizeof(u32));
    }
}

switch 部分处理了循环展开的剩余部分。时间复杂度 O(n)，原因：设 b 是基数，要排序的最大数是 V，桶排序需要 \log_b V 次，由于 n 个数，还应该有 n，时间复杂度 O(n\log_b V)，不严格地说也可以是 O(n)（显然本题基数不能太小，后面也是基本线性的）。

其他思考

对于 2^8 虽然可以通过本题，但是基数未免太小了？刚才说选择 2^8 是因为 8 是 32 的约数，而且足够小，可以进入 Cache。

但是考虑一个数，除 32 取余很小，而且比 8 大，而且可以顺利进入 Cache，不难想到 11>8，2^{11}=2048 足够小，32=11\times 3-1，也就是分成 11,11,10 来进行基数排序。

这同样给了我们动态调整基数（也可以随机化？）的思考空间。

经过试验 2^{16} 的时间（最大点）是 4.84s，2^{11} 是 3.83s，2^{8} 是 4.41s。

代码留给读者来完成（可以仿照我的 2^8 作为基数的代码，细节由作者来处理，加油！这也是这篇题解阅读的检测），经过实测 2^{11} 作为基数的时间更快。

当然这里 8|n 循环展开后面 switch,case 可以丢掉，但是我代码还是写了，可以供手造数据进行测试。

题目 2

题目分析

考虑暴力加循环展开，每种石头剪刀布的结果用一个二维数组维护，让这个东西进入 Cache（显然很容易），然后其他的暴力展开即可。

特别地，建议使用常量（快），而且 const 不是表示常量，而是只读量，只有防止误操作的作用。constexpr 才是常量关键字。

循环展开最好是 6\sim 8 个展开。

循环展开尽量用不同变量来降低数据相关性，来加快速度。

代码实现

namespace Game{
    constexpr u32 mp[3][3]={
        {0,1,0},
        {0,0,1},
        {1,0,0}
    };//结果
    void main(){
        int n,q,x,y,len;
        scanf("%d%d",&n,&q);
        char *s1=new char[n+1];
        char *s2=new char[n+1];
        scanf("%s%s",s1,s2);
        u32 ans0,ans1,ans2,ans3,ans4,ans5,ans6,ans7;
        u32*ans=new u32[n+1];
        for(int i=0;i+7<n;i+=8){
            s1[i]^=48,s2[i]^=48;
            s1[i+1]^=48,s2[i+1]^=48,
            s1[i+2]^=48,s2[i+2]^=48,
            s1[i+3]^=48,s2[i+3]^=48,
            s1[i+4]^=48,s2[i+4]^=48,
            s1[i+5]^=48,s2[i+5]^=48,
            s1[i+6]^=48,s2[i+6]^=48,
            s1[i+7]^=48,s2[i+7]^=48;
        }
        switch(n&7){
            case 7:s1[n-7]^=48,s2[n-7]^=48;
            case 6:s1[n-6]^=48,s2[n-6]^=48;
            case 5:s1[n-5]^=48,s2[n-5]^=48;
            case 4:s1[n-4]^=48,s2[n-4]^=48;
            case 3:s1[n-3]^=48,s2[n-3]^=48;
            case 2:s1[n-2]^=48,s2[n-2]^=48;
            case 1:s1[n-1]^=48,s2[n-1]^=48;
        }//转为数字
        for(int i=0;i<q;i++){
            scanf("%d%d%d",&x,&y,&len);
            ans0=ans1=ans2=ans3=ans4=ans5=ans6=ans7=0;
            for(;len>=8;len-=8,x+=8,y+=8){
                ans0+=mp[s1[x]][s2[y]],
                ans1+=mp[s1[x+1]][s2[y+1]],
                ans2+=mp[s1[x+2]][s2[y+2]],
                ans3+=mp[s1[x+3]][s2[y+3]],
                ans4+=mp[s1[x+4]][s2[y+4]],
                ans5+=mp[s1[x+5]][s2[y+5]],
                ans6+=mp[s1[x+6]][s2[y+6]],
                ans7+=mp[s1[x+7]][s2[y+7]];
            }
            switch(len){
                case 7:ans7+=mp[s1[x+6]][s2[y+6]];
                case 6:ans6+=mp[s1[x+5]][s2[y+5]];
                case 5:ans5+=mp[s1[x+4]][s2[y+4]];
                case 4:ans4+=mp[s1[x+3]][s2[y+3]];
                case 3:ans3+=mp[s1[x+2]][s2[y+2]];
                case 2:ans2+=mp[s1[x+1]][s2[y+1]];
                case 1:ans1+=mp[s1[x]][s2[y]];
            }//处理剩余
            ans[i]=ans0+ans1+ans2+ans3+ans4+ans5+ans6+ans7;
        }
        output_arr(ans,q*sizeof(u32));
    }
}

时间复杂度 O(nq)。

其他思考

可以考虑压位，这堆信息很小，很多数可以压成一个数，然后用 __builtin 家族的位运算、普通的位运算快速解决（注意如果要开 long long 压位 __builtin_xxx 要变成 __builtin_xxxll）。

题目 3

题目分析

显然是个 DP 题目，抛开时间显然非常简单。

考虑 f_{i,j} 表示前 i 个符号，左括号比右括号多 j 个时的方案数。

如果 s_i 是左括号，f_{i,j}=f_{i-1,j-1}，否则 f_{i,j}=f_{i-1,j+1}。如果是问号，那就两者的和。

显然暴力不可能全过，只能过一个测试点。

考虑滚动数组，转移方程和上面差不多。

考虑 DP 优化，首先转移的时候：第 i 次转移（这里的 i 指的是从 1 为起点的下标，程序是以 0 为起点，需要注意）一定 i\equiv j\pmod {2}，原因是不可能奇数出现一对括号，偶数同理。

然后注意到非问号时，每次都要从两边转移，还需要二维滚动数组（第一维是 01，滚动掉 i），常数很大，可以用上述取模优化（奇偶性优化）。

而且对于相同的 i，如果非问号，每次相当于整个数组统一偏移了一次。统一偏移不如让指针偏移。

例如 f_j=f_{j-1} 的转移代码只是 f--; 这样就重新对应了（平时不建议这么写，会有细节）。

需要注意代码最后 t[-1]=0 表示，现在已经继承完了 t[-1] 已经不存在，需要避免之后指针前移之后继承已经不存在的 t[-1]，就是出现类似于 )( 的序列。

代码实现

namespace Parentheses{
    int f[600001];
    void main(){
        int n;
        scanf("%d",&n);
        char*s=new char[n+1];
        int *t=f+300000;
        scanf("%s",s);
        t[0]=1;//初始状态
        for(int i=0;i<n;i++){
            switch(s[i]){
                case'(':{
                    --t;
                    break;//改变指针
                }
                case')':{
                    ++t;
                    break;//同上
                }
                case'?':{
                    int H17=std::min(i,n-i)+1;
                    for(int j=i&1^1;j<=H17;j+=2)
                        t[j]=t[j-1]+t[j+1];//转移，但是奇偶性优化
                    break;
                }
            }
            t[-1]=0;//去掉不合法状态
        }
        printf("%u",t[0]);
    }
}

时间复杂度 O(n^2)，但是常数优化比较大。

整体代码

#include<bits/stdc++.h>
typedef unsigned int u32;
typedef unsigned long long u64;
inline u32 next_integer(u32 x){
    x^=x<<13,
    x^=x>>17,
    x^=x<<5;
    return x;
}
bool output_arr(void*a,u32 size){
    if (size&3)
        return puts("-1"),0;
    u32 blocks=size/4,*A=(u32*)a,ret=size,x=23333333;
    for(u32 i=0;i<blocks;++i){
        ret=ret^(A[i]+x),
        x^=x<<13,
        x^=x>>17,
        x^=x<<5;
    }
    return printf("%u\n",ret),1;
}

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

namespace Sorting{
    int cnt0[256],cnt8[256],cnt16[256],cnt24[256];
    void init_data(u32* a,int n,u32 seed){
        for(int i=0;i<n;++i){
            seed=next_integer(seed),
            a[i]=seed,
            ++cnt0[seed&255],
            ++cnt8[seed>>8&255],
            ++cnt16[seed>>16&255],
            ++cnt24[seed>>24&255];
        }
        for(int i=1;i<256;++i)
            cnt0[i]+=cnt0[i-1],
            cnt8[i]+=cnt8[i-1],
            cnt16[i]+=cnt16[i-1],
            cnt24[i]+=cnt24[i-1];
    }
    void main(){
        int n;
        u32 seed;
        scanf("%d%u",&n,&seed);
        u32 *a=new u32[n],*b=new u32[n],*cur;
        init_data(a,n,seed);
        u32 repeat=n>>3,tmp;
        for(tmp=repeat,cur=a+n-1;tmp;--tmp){
            b[--cnt0[cur[0]&255]]=cur[0],
            b[--cnt0[cur[-1]&255]]=cur[-1],
            b[--cnt0[cur[-2]&255]]=cur[-2],
            b[--cnt0[cur[-3]&255]]=cur[-3],
            b[--cnt0[cur[-4]&255]]=cur[-4],
            b[--cnt0[cur[-5]&255]]=cur[-5],
            b[--cnt0[cur[-6]&255]]=cur[-6],
            b[--cnt0[cur[-7]&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:b[--cnt0[cur[-6]&255]]=cur[-6];
            case 6:b[--cnt0[cur[-5]&255]]=cur[-5];
            case 5:b[--cnt0[cur[-4]&255]]=cur[-4];
            case 4:b[--cnt0[cur[-3]&255]]=cur[-3];
            case 3:b[--cnt0[cur[-2]&255]]=cur[-2];
            case 2:b[--cnt0[cur[-1]&255]]=cur[-1];
            case 1:b[--cnt0[cur[0]&255]]=cur[0];
        }
        for(tmp=repeat,cur=b+n-1;tmp;--tmp){
            a[--cnt8[cur[0]>>8&255]]=cur[0],
            a[--cnt8[cur[-1]>>8&255]]=cur[-1],
            a[--cnt8[cur[-2]>>8&255]]=cur[-2],
            a[--cnt8[cur[-3]>>8&255]]=cur[-3],
            a[--cnt8[cur[-4]>>8&255]]=cur[-4],
            a[--cnt8[cur[-5]>>8&255]]=cur[-5],
            a[--cnt8[cur[-6]>>8&255]]=cur[-6],
            a[--cnt8[cur[-7]>>8&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:a[--cnt8[cur[-6]>>8&255]]=cur[-6];
            case 6:a[--cnt8[cur[-5]>>8&255]]=cur[-5];
            case 5:a[--cnt8[cur[-4]>>8&255]]=cur[-4];
            case 4:a[--cnt8[cur[-3]>>8&255]]=cur[-3];
            case 3:a[--cnt8[cur[-2]>>8&255]]=cur[-2];
            case 2:a[--cnt8[cur[-1]>>8&255]]=cur[-1];
            case 1:a[--cnt8[cur[0]>>8&255]]=cur[0];
        }
        for(tmp=repeat,cur=a+n-1;tmp;--tmp){
            b[--cnt16[cur[0]>>16&255]]=cur[0],
            b[--cnt16[cur[-1]>>16&255]]=cur[-1],
            b[--cnt16[cur[-2]>>16&255]]=cur[-2],
            b[--cnt16[cur[-3]>>16&255]]=cur[-3],
            b[--cnt16[cur[-4]>>16&255]]=cur[-4],
            b[--cnt16[cur[-5]>>16&255]]=cur[-5],
            b[--cnt16[cur[-6]>>16&255]]=cur[-6],
            b[--cnt16[cur[-7]>>16&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:b[--cnt16[cur[-6]>>16&255]]=cur[-6];
            case 6:b[--cnt16[cur[-5]>>16&255]]=cur[-5];
            case 5:b[--cnt16[cur[-4]>>16&255]]=cur[-4];
            case 4:b[--cnt16[cur[-3]>>16&255]]=cur[-3];
            case 3:b[--cnt16[cur[-2]>>16&255]]=cur[-2];
            case 2:b[--cnt16[cur[-1]>>16&255]]=cur[-1];
            case 1:b[--cnt16[cur[0]>>16&255]]=cur[0];
        }
        for(tmp=repeat,cur=b+n-1;tmp;--tmp){
            a[--cnt24[cur[0]>>24&255]]=cur[0],
            a[--cnt24[cur[-1]>>24&255]]=cur[-1],
            a[--cnt24[cur[-2]>>24&255]]=cur[-2],
            a[--cnt24[cur[-3]>>24&255]]=cur[-3],
            a[--cnt24[cur[-4]>>24&255]]=cur[-4],
            a[--cnt24[cur[-5]>>24&255]]=cur[-5],
            a[--cnt24[cur[-6]>>24&255]]=cur[-6],
            a[--cnt24[cur[-7]>>24&255]]=cur[-7];
            cur-=8;
        }
        switch(n&7){
            case 7:a[--cnt24[cur[-6]>>24&255]]=cur[-6];
            case 6:a[--cnt24[cur[-5]>>24&255]]=cur[-5];
            case 5:a[--cnt24[cur[-4]>>24&255]]=cur[-4];
            case 4:a[--cnt24[cur[-3]>>24&255]]=cur[-3];
            case 3:a[--cnt24[cur[-2]>>24&255]]=cur[-2];
            case 2:a[--cnt24[cur[-1]>>24&255]]=cur[-1];
            case 1:a[--cnt24[cur[0]>>24&255]]=cur[0];
        }
        output_arr(a,n*sizeof(u32));
    }
}

namespace Game{
    constexpr u32 mp[3][3]={
        {0,1,0},
        {0,0,1},
        {1,0,0}
    };
    void main(){
        int n,q,x,y,len;
        scanf("%d%d",&n,&q);
        char *s1=new char[n+1];
        char *s2=new char[n+1];
        scanf("%s%s",s1,s2);
        u32 ans0,ans1,ans2,ans3,ans4,ans5,ans6,ans7;
        u32*ans=new u32[n+1];
        for(int i=0;i+7<n;i+=8){
            s1[i]^=48,s2[i]^=48;
            s1[i+1]^=48,s2[i+1]^=48,
            s1[i+2]^=48,s2[i+2]^=48,
            s1[i+3]^=48,s2[i+3]^=48,
            s1[i+4]^=48,s2[i+4]^=48,
            s1[i+5]^=48,s2[i+5]^=48,
            s1[i+6]^=48,s2[i+6]^=48,
            s1[i+7]^=48,s2[i+7]^=48;
        }
        switch(n&7){
            case 7:s1[n-7]^=48,s2[n-7]^=48;
            case 6:s1[n-6]^=48,s2[n-6]^=48;
            case 5:s1[n-5]^=48,s2[n-5]^=48;
            case 4:s1[n-4]^=48,s2[n-4]^=48;
            case 3:s1[n-3]^=48,s2[n-3]^=48;
            case 2:s1[n-2]^=48,s2[n-2]^=48;
            case 1:s1[n-1]^=48,s2[n-1]^=48;
        }
        for(int i=0;i<q;i++){
            scanf("%d%d%d",&x,&y,&len);
            ans0=ans1=ans2=ans3=ans4=ans5=ans6=ans7=0;
            for(;len>=8;len-=8,x+=8,y+=8){
                ans0+=mp[s1[x]][s2[y]],
                ans1+=mp[s1[x+1]][s2[y+1]],
                ans2+=mp[s1[x+2]][s2[y+2]],
                ans3+=mp[s1[x+3]][s2[y+3]],
                ans4+=mp[s1[x+4]][s2[y+4]],
                ans5+=mp[s1[x+5]][s2[y+5]],
                ans6+=mp[s1[x+6]][s2[y+6]],
                ans7+=mp[s1[x+7]][s2[y+7]];
            }
            switch(len){
                case 7:ans7+=mp[s1[x+6]][s2[y+6]];
                case 6:ans6+=mp[s1[x+5]][s2[y+5]];
                case 5:ans5+=mp[s1[x+4]][s2[y+4]];
                case 4:ans4+=mp[s1[x+3]][s2[y+3]];
                case 3:ans3+=mp[s1[x+2]][s2[y+2]];
                case 2:ans2+=mp[s1[x+1]][s2[y+1]];
                case 1:ans1+=mp[s1[x]][s2[y]];
            }
            ans[i]=ans0+ans1+ans2+ans3+ans4+ans5+ans6+ans7;
        }
        output_arr(ans,q*sizeof(u32));
    }
}

namespace Parentheses{
    int f[600001];
    void main(){
        int n;
        scanf("%d",&n);
        char*s=new char[n+1];
        int *t=f+300000;
        scanf("%s",s);
        t[0]=1;
        for(int i=0;i<n;i++){
            switch(s[i]){
                case'(':{
                    --t;
                    break;
                }
                case')':{
                    ++t;
                    break;
                }
                case'?':{
                    int H17=std::min(i,n-i)+1;
                    for(int j=i&1^1;j<=H17;j+=2)
                        t[j]=t[j-1]+t[j+1];
                    break;
                }
            }
            t[-1]=0;
        }
        printf("%u",t[0]);
    }
}

int main(){
    int task_id;
    scanf("%d",&task_id);
    switch(task_id){
        case 1:
            Sorting::main();
            break;
        case 2:
            Game::main();
            break;
        case 3:
            Parentheses::main();
            break;
    }
    return 0;
}