T1：
考场转化为数学语言，于是对参数解不等式，判断是否存在整数解
时间复杂度O(Tnk)，考虑区间操作可以通过线段树维护，区间减除。然
而复杂度瓶颈在于k。
正解为首先简化问题，将黑条向前延伸s，显然等价，考虑由于每次
走步长度固定，于是对于每个黑/白条，其出发区间一定，于是判断可行
性可以转化为判断出发点是否存在交集，注意到关键决策点为黑条，判
断黑条出发点区间之并是否能完全覆盖k即可。事实上判断白条出发点集
合是否有交也可做，然而白条并非关键决策点，即白条并不一定全部经过
需要判断至少需要几步才能通过，判断区间之交是否满足即可。
注意取模改变数学系（取模后取区间并需要去重），变量名见名知意
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define B bool
6 const I N = 5e5 + 3;
7 I T,s,k,n,l[N],r[N];
8 struct S { I l,r; } ele[N << 1];
9 struct Q { I l,r; } rea[N << 1];
10 inline I read() {
11 I x(0),y(1); C z(getchar());
12 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
13 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
14 return x * y;
15 }
16 inline B com (const S &a,const S &b) {
17 return a.l == b.l ? a.r > b.r : a.l < b.l;
18 }
19 signed main () {
20 T = read();
21 while (T -- ) {
22 B jud(0); I tmp(0),tot(0),cnt(0);
23 s = read(), k = read(), n = read();
24 for (I i(1);i <= n; ++ i) {
25 tmp += read(); l[i] = r[i - 1] + 1;
26 r[i] = i & 1 ? tmp + s - 1 : tmp;
27 if (i & 1) {
28 if (r[i] - l[i] + 1 >= k) jud = 1;
29 I tmp1(l[i] % k + 1), tmp2(r[i] % k + 1);
30 if (tmp1 <= tmp2) ele[++tot] = (S){tmp1,tmp2};
31 else ele[++tot] = (S){1,tmp2}, ele[++tot] = (S){tmp1,k};
32 }
33 }
34 if (jud) { printf ("NIE\n"); continue; }
35 sort (ele + 1,ele + tot + 1,com);
36 I p1(1),p2(2);
37 while (p1 <= tot) {
38 rea[++cnt] = (Q){ele[p1].l,ele[p1].r};
39 while (ele[p2].l >= ele[p1].l && ele[p2].r <= ele[p1].r && p2 <= tot) p2 ++ ; p1 = p2 ++ ;
40 }
41 for (I i(1);i <= cnt; ++ i) if (rea[i].l > rea[i - 1].r + 1) { jud = 1; break; }
42 if (rea[cnt].r < k) jud = 1;
43 jud ? printf ("TAK\n") : printf ("NIE\n");
44 }
45 }
View Code
T2：
理解并不深刻，三维（状态空间）DP，由于各参数范围很小（可以乱
搞）考虑定义DP：f[l][r][p][c]为之考虑区间l~r第p位以后的位置，并且钦定
第p位至少为c。
状态转移：考虑三维空间下如何覆盖l*r*p*c的体积，首先f[l][r][p][c]可
以由f[l][r][p][c+1]转移而来，对应了l*r*p*(c-1)的体积，考虑如何转移最后
一层，采用状态划分DP的思路，将f[l][r][p][c]划分为f[l][i]与f[i + 1][r]，由于
最后仅剩l*r*p*1（恰好为c的状态），于是考虑钦定f[l][i][p]为c，为保证状
态的合法性，必须满足f[l][i][p + 1][0]，否则可能存在不合法状态，同理，
也必须满足f[i + 1][r][p][c + 1]状态
注意判断边界，及时跳出即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I long long
4 #define C char
5 #define V void
6 const I mod = 990804011;
7 I n,u,f[55][55][25][30],A[55][25];
8 C s[25];
9 inline I max (I a,I b) { return a > b ? a : b; }
10 inline I read () {
11 I x(0),y(1); C z(getchar());
12 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
13 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
14 return x * y;
15 }
16 I dfs (I l,I r,I p,I c) {
17 I &tmp(f[l][r][p][c]);
18 if ( ~ tmp) return tmp;
19 if (l > r) return tmp = 1;
20 if (p > u) return tmp = l == r;
21 if (c > 26) return tmp = 0;
22 tmp = dfs (l,r,p,c + 1);
23 for (I i(l);i <= r; ++ i) {
24 if (!(A[i][p] == c || (A[i][p] == 27 && c))) break;
25 tmp = (tmp + dfs (l,i,p + 1,0) * dfs (i + 1,r,p,c + 1)) % mod;
26 }
27 return tmp;
28 }
29 signed main () {
30 n = read();
31 memset (f,-1,sizeof f);
32 for (I i(1);i <= n; ++ i) {
33 scanf ("%s",s + 1);
34 u = max (u,strlen(s + 1));
35 for (I j(1),tmp(strlen(s + 1));j <= tmp; ++ j)
36 A[i][j] = s[j] == '?' ? 27 : s[j] - 'a' + 1;
37 }
38 printf ("%lld\n",dfs (1,n,1,0));
39 }
View Code
T3：（口胡）
考虑三种函数的数学本质，前两种为直观定义，考虑第三种的贡献，
显然只有当所有x均为1时才会作出1的贡献，于是考虑第三种函数存在多
少种在经过若干次叠变后满足所有x均为1。
观察第三种函数的转化发现，对于每个x-1的情况其都完全考虑，也
就是说，第三种函数的叠变方式实质上是全排列，对于每个xi，将其叠变
为1需要叠变xi - 1次，由于叠变方式为全排列且每次只叠变1，于是考虑将
xi - 1视为xi - 1个1，现在对每组xi中的xi - 1个1全排列即可得到所有方案（
可以理解为赋予时间参数，对于1的排列代表在何时将xi减1），由于每组
xi中的1等价，于是问题就是可重集排列。
现在考虑对于f函数的贡献，即判断其奇偶性，发现分母2因子个数必
定大于等于分子2因子个数，于是暴力思路为利用素因子筛法logn分别求
出分母分子2因子个数比较大小判断奇偶性，然而这种求解方法到此结束
因为问题瓶颈在于优化搜索树，即如何高效判断[l,r]区间的决策。
于是考虑更改思路，尝试通过分子分母本身的性质做到高效判断，避
免冗余转移，于是利用库默尔定理（详见数学杂项），发现只需要判断2进
制下，分子中是否存在进位即可，于是可以数位DP每组[l,r]，使其尽量不
发生进位，对此数位DP即可