A

手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 $x$ 个数，那么 $x \times x$ 的方格的数都没用了，并且剩下的是一个 L 形方格。剩下的 L 形方格内对角线一定是最大值，所以我们只需要每次取最大值，将这个数和已经确定的数的 $\gcd$ 删掉即可。注意要删两次。

B

可以猜测一下选择方案一定是前面可能有某些增加值的地方，后面值就一直不变了。所以我们先一直跑 dp，跑到快要 T 的时候就相当于要从剩下的块中选出一些数字。由于我们可以将这个块添加到任意位置，所以选最大出现次数的数字即可。

可以证明其实只需要跑 $n$ 块即可。。因为你最坏情况是每一块增加一次。这一块不增加后面完全没有必要增加。

C

一个经典结论是设长度为 $s$，设 $g = \gcd(s,n)$，那么新的序列的第 $i$ 位会对应原序列的 $i,i+g,i+2g,\ldots i+kg$ 位。所以我们复制一遍序列，枚举 $g|n$，将下标按照 $\bmod g$ 分类，一个点合法当前仅当它是和它一组中的最大值，一个方案合法当且仅当区间内所有点合法，倒着扫一遍维护一个指针，差分维护前缀加，求出所有长度的区间的方案数，判断 $\gcd$ 即可解决。

注意这里需要预处理一下 $\gcd(i,n)$，要不然会 T。。时间还是很紧的。

D

设 $v_p(x)$ 表示 $x$ 的唯一分解中 $p$ 上面的指数。

首先我们有 $v_p(n!) = \sum_{i \geq 1} \lfloor \frac{n}{p^i} \rfloor$，并且还有 $v_p(ab) = v_p(a)+v_p(b)$，如果考虑将 $n$ 分解成 $p$ 进制下的数，那么 $v_p(n!)$ 的每一位贡献都是将比这一位低的位都去掉的数的和。

那么我们知道 $v_p(\binom n m) = v_p(n!)-v_p(m!)-v_p((n-m)!)$，我们考虑 $m+(n-m) = n$ 这个加法运算，如果在第 $i$ 位它进位了，那么在前 $i$ 位贡献不变，在第 $i+1$ 位答案会多 $1$。所以 $v_p(\binom n m)$ 就是 $n-m$ 和 $m$ 做 $p$ 进制下加法的进位次数。

这个好像叫做库默尔定理？

然后我们可以考虑设计一个数位dp：我们在第 $i$ 位需要知道它后面那一位是否进位才可以确定限制等因素，设 $f_{i,j,0/1,0/1}$ 从高到低考虑前 $i$ 位，进了 $j$ 次位，当前的和是否卡上界，下一位是否进位，转移细节可以看代码（我注释写的很详细了）。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 3500+5;
const int ha = 1e9 + 7;
const int inv2 = (ha+1)>>1;
int p,_,n;
char str[MAXN];
int b[MAXN],a[MAXN];
int f[2][MAXN][2][2],now;
// 考虑前i位 当前进位了j次 现在是否卡上界 下一位是否进位

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

inline int calc(int n){ // sum of [x <= b,y <= n,x+y <= n]
    if(n < 0) return 0;
    if(n == 0) return 1;
    return (1ll*(n+1)*(n+1)%ha+ha-1ll*n*(n+1)%ha*inv2%ha)%ha;
}

inline int calc2(int n){ // sum of [x <= p-1,y <= p-1,x+y <= n]
    // p <= n+1-i => i <= n+1-p
    int res = 0;
    if(n+1-p >= 0) add(res,1ll*(n+1-p+1)%ha*p%ha);
    // p > n+1-i => i >= n+2-p
    if(n+2-p <= p-1){
        // p-1 +p-2 + ....
        int len = (p-1)-(n+2-p)+1;
        add(res,1ll*(p-1)*p%ha*inv2%ha);
        len = (p-1)-len;
        if(len > 0) add(res,ha-1ll*(len+1)*len%ha*inv2%ha);
    }
    return res;
}

int main(){
    scanf("%d%d",&p,&_);// 进制转换
    scanf("%s",str+1);int len = strlen(str+1);
    FOR(i,1,len) a[i] = str[i]-'0';
    std::reverse(a+1,a+len+1);
    while(len){
        int t = 0;
        ROF(i,len,1) t = (10ll*t+a[i]) % p;
        b[++n] = t;
        a[1] -= t;
        FOR(i,1,len){
            if(a[i] < 0){
                int tt = (-a[i])/10;
                if(a[i]+10*tt < 0) ++tt;
                a[i] += 10*tt;
                a[i+1] -= tt;
            }
        }
        while(len && !a[len]) --len;
        LL r = 0; // up to O(p^2)
        ROF(i,len,1){
            r = 10*r+a[i];
            a[i] = r/p;
            r %= p;
        }
        while(len && !a[len]) --len;
    }
    std::reverse(b+1,b+n+1);
    f[now=0][0][1][0] = 1;
    // int tt = 0;FOR(x,0,p-1) FOR(y,0,p-1) tt += (x+y <= 3);
    // DEBUG(tt);DEBUG(calc2(3));
    // DEBUG(calc2(3)-calc2(2));
    // exit(0);
    FOR(i,1,n){
        // 打破限制 <=> (x+y)%p < b[i]
        // 有进位  <=>  x+y>=p
        // 无进位 <=> x+y <= p-1
        // 卡上界 <=> (x+y)%p = b[i]
        // +1 <=> 这一位的值 +1=
        // 这一位有限制 上一位必然有限制
        // (x+1)^2-x*(x+1)/2
        CLR(f[now^1],0);
        FOR(j,0,i){// 设两个数分别为x,y
            int t = 0;
            int c1 = calc(p-1);
            int c2 = calc(p-2);
            int c3 = calc(b[i]-1);
            int c4 = (calc2(p+b[i]-1)+ha-calc2(p-1))%ha;

            add(f[now^1][j][0][0],1ll*f[now][j][0][0]*(c1/*不进位*/)%ha);
            add(f[now^1][j][0][0],1ll*f[now][j][0][1]*(c2/*有进位*/)%ha);
            add(f[now^1][j][0][0],1ll*f[now][j][1][0]*(c3/*打破限制 不进位*/)%ha);
            add(f[now^1][j][0][0],1ll*f[now][j][1][1]*(c4/*打破限制 有进位*/)%ha);
            
            c1 = calc(p-2);
            c2 = calc(p-2);add(c2,p);
            c3 = calc(b[i]-2);
            c4 = (calc2(std::min(2*p-2,b[i]+p-2))+ha-calc2(p-2))%ha;
            
            add(f[now^1][j+1][0][1],1ll*f[now][j][0][0]*(c1/*不进位 +1*/)%ha);
            add(f[now^1][j+1][0][1],1ll*f[now][j][0][1]*(c2/*有进位 +1*/)%ha);
            add(f[now^1][j+1][0][1],1ll*f[now][j][1][0]*(c3/*打破限制 不进位 +1*/)%ha);
            add(f[now^1][j+1][0][1],1ll*f[now][j][1][1]*(c4/*打破限制 有进位 +1*/)%ha);
        
            c3 = b[i]+1;
            c4 = std::min(b[i]+p,p-1)-std::max(1+b[i],0)+1;
            c4 = std::max(c4,0);
            // add(f[now^1][j][1][0],f[now][j][0][0]*(/*不存在*/));
            // add(f[now^1][j][1][0],f[now][j][0][1]*(/*不存在*/));
            add(f[now^1][j][1][0],1ll*f[now][j][1][0]*(c3/*卡上界 不进位*/)%ha);
            add(f[now^1][j][1][0],1ll*f[now][j][1][1]*(c4/*卡上界 有进位*/)%ha);
            
            c3 = b[i]-1+1;
            c4 = std::min(b[i]+p-1,p-1)-std::max(1-p+b[i]+p-1,0)+1;
            // add(f[now^1][j+1][1][1],f[now][j][0][0]*(/*不存在*/));
            // add(f[now^1][j+1][1][1],f[now][j][0][1]*(/*不存在*/));
            add(f[now^1][j+1][1][1],1ll*f[now][j][1][0]*(c3/*卡上界 不进位 +1*/)%ha);
            add(f[now^1][j+1][1][1],1ll*f[now][j][1][1]*(c4/*卡上界 有进位 +1*/)%ha);
        }
        now ^= 1;
    }
    int ans = 0;
    FOR(i,_,n) add(ans,f[now][i][0][0]),add(ans,f[now][i][1][0]);
    printf("%d\n",ans);
    return 0;
}

E

首先表达式问题肯定不能做，要建表达式树。

建数每次扫出一个完整的括号就在这个地方划分就好了（详情请看代码）。

发现只有 $4$ 个变量也就是 $16$ 种取值，我们相当于限制了在多个变量取值情况的总取值，所以我们考虑将所有可能取值的总取值都压缩起来：设 $f_{i,S}$ 表示 $i$ 子树内，变量取值为 $1$ 的集合 $T \in S$ 的时候总取值都为 $1$，其余都为 $0$ 的方案数。换言之 $S$ 是字母取值集合的集合（所以大小 $2^{16}$）。

在底层的时候如果是确定的点就枚举所有的 $v \in T$，将这些 $T$ 组成的集合 $S$ 的 $f_{v,S} = 1$。如果不确定的话就把所有可能枚举一遍。这里要预处理所有类型的点而不是每次暴力要不然时间可能不太行。

然后合并的时候相当于是一个集合并卷积或者集合交卷积，FWT即可。

这种将所有可行的取值的状态压起来的状压还是要多想。。好好复习一下。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 500+5;
const int MAXM = 16;
const int ha = 1e9 + 7;

inline void add(int &x,int y){
    x += y;if(x >= ha) x -= ha;
}

int ch[MAXN][2],tot;
char a[MAXN],str[MAXN];
int rt;

inline int work(int l,int r){
    if(l > r) return 0;
    if(l == r){
        a[++tot] = str[l];
        return tot;
    }
    int sm = 0,ps = 0;
    FOR(i,l,r){
        if(str[i] == '(') ++sm;
        if(str[i] == ')') --sm;
        if(sm == 0){
            ps = i;break;
        }
    }
    if(ps == r) return work(l+1,r-1);
    int x = ++tot;
    a[x] = str[ps+1];
    ch[x][0] = work(l+1,ps-1);
    ch[x][1] = work(ps+3,r-1);
    return x;
}

int f[MAXN][(1<<16)+3];
int g[9][(1<<16)+3];
// 子树v内, 四个字母每种可能的取值 T 对应的表达式取值集合是S,方案数

inline int ctoi(char c){
    if(c >= 'A' && c <= 'D') return c-'A';
    if(c >= 'a' && c <= 'd') return c-'a';
    return -1;
}

int N = (1<<16);

inline void OR(int f[]){for(int mid = 1;mid < N;mid <<= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+mid+j],f[i+j]);}
inline void iOR(int f[]){for(int mid = N>>1;mid;mid >>= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+mid+j],ha-f[i+j]);}
inline void AND(int f[]){for(int mid = 1;mid < N;mid <<= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+j],f[i+mid+j]);}
inline void iAND(int f[]){for(int mid = N>>1;mid;mid >>= 1) for(int i = 0;i < N;i += (mid<<1)) FOR(j,0,mid-1) add(f[i+j],ha-f[i+mid+j]);}
inline void COR(int A[],int B[],int C[]){OR(A);OR(B);FOR(i,0,N-1) C[i] = 1ll*A[i]*B[i]%ha;iOR(C);iOR(A);iOR(B);}
inline void CAND(int A[],int B[],int C[]){AND(A);AND(B);FOR(i,0,N-1) C[i] = 1ll*A[i]*B[i]%ha;iAND(C);iAND(A);iAND(B);}

int tmp[(1<<16)+5];

inline void dfs(int v){
    if(!ch[v][0] && !ch[v][1]){
        int id = ctoi(a[v])+(4*(a[v] >= 'a' && a[v] <= 'd'));
        if(id == -1) id = 8;
        FOR(S,0,(1<<16)-1) f[v][S] = g[id][S];
        return;
    }
    dfs(ch[v][0]);dfs(ch[v][1]);
    if(a[v] == '&') return CAND(f[ch[v][0]],f[ch[v][1]],f[v]);
    if(a[v] == '|') return COR(f[ch[v][0]],f[ch[v][1]],f[v]);
    CAND(f[ch[v][0]],f[ch[v][1]],tmp);
    COR(f[ch[v][0]],f[ch[v][1]],f[v]);
    FOR(S,0,N-1) add(f[v][S],tmp[S]);
}

int main(){
    FOR(i,0,3){
        int t = 0;
        FOR(S,0,(1<<4)-1) t |= (((S>>i)&1)<<S);
        ++g[i][t];++g[i+4][t^((1<<16)-1)];
        ++g[8][t];++g[8][t^((1<<16)-1)];
    }
    scanf("%s",str+1);int len = strlen(str+1);
    rt = work(1,len);
    dfs(rt);
    int n;scanf("%d",&n);
    int t0=0,t1=0;
    FOR(i,1,n){
        int a,b,c,d,e;scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
        int t = a|(b<<1)|(c<<2)|(d<<3);
        if(e) t1 |= (1<<t);
        else t0 |= (1<<t);
    }
    int ans = 0;
    FOR(S,0,(1<<16)-1) if(((S&t1) == t1) && ((S&t0) == 0)) add(ans,f[rt][S]);
    printf("%d\n",ans);
    return 0;
}