A
手玩一下样例，我们从大到小确定每个数：将确定的数挪到序列的最前面，设确定了 (x) 个数，那么 (x imes 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)，将下标按照 (mod g) 分类，一个点合法当前仅当它是和它一组中的最大值，一个方案合法当且仅当区间内所有点合法，倒着扫一遍维护一个指针，差分维护前缀加，求出所有长度的区间的方案数，判断 (gcd) 即可解决。
注意这里需要预处理一下 (gcd(i,n))，要不然会 T。。时间还是很紧的。
D
设 (v_p(x)) 表示 (x) 的唯一分解中 (p) 上面的指数。
首先我们有 (v_p(n!) = sum_{i geq 1} lfloor frac{n}{p^i} floor)，并且还有 (v_p(ab) = v_p(a)+v_p(b))，如果考虑将 (n) 分解成 (p) 进制下的数，那么 (v_p(n!)) 的每一位贡献都是将比这一位低的位都去掉的数的和。
那么我们知道 (v_p(inom n m) = v_p(n!)-v_p(m!)-v_p((n-m)!))，我们考虑 (m+(n-m) = n) 这个加法运算，如果在第 (i) 位它进位了，那么在前 (i) 位贡献不变，在第 (i+1) 位答案会多 (1)。所以 (v_p(inom 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
",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
",ans);
return 0;
}