后：day7

衢州

备注：下午下课后开始拉肚子，晚上去医院，没整理

预计：60+?+40
实际：60+10+40
第二题写了搜索，考完发现最后一个点是可以重复走的，代码中是不是重复走的，考试时过了小样例之后也没管。

T1花园

考试写了倍增，60分，处理只有一个询问的，单次处理nlogn，调了很久，其实如果把一个点拆成两个点做倍增的话，会简单些。
最后在倍增上bfs好像可以处理，最后没调出。

正解：
不啰唆了，代码注释。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 150010;
struct Edge{
    int to, nxt, ty;
    Edge() {}
    Edge(int a,int c,int d) {to = a,ty = c,nxt = d;}
}e[N << 1];
int head[N], Enum;
int sum[2][N << 2], Circle[2], cnt[2][N << 2], fir[N], dgr[N];
int P;
void add_edge(int u,int v,int w) {
    ++Enum; e[Enum] = Edge(v, w, head[u]); head[u] = Enum;
}
// w->u->v。原图：v->u->w
//ty 0 w->u为最长边，下一条不必是最长的。原图：u->w走了最长的了，所以说v->u一定不能走u的最长边。
//typ 1为从次长边过来 下条只能走最长边。原图：u->w走了次长的，所以说v->u一定走u的最长边。
void dfs(int u,int dis,int ty,int dir) { 
    if (!ty) cnt[dir][dis] ++; // 现在是走的反向，的就是从P往会走，所以如果上一次是走的最长边到达的u，就是u走的最长边到达上一个点
    for (int i=head[u]; i; i=e[i].nxt) {
        int v = e[i].to;
        if (!ty && v == fir[u] && dgr[u] > 1) continue;
        if (ty && v != fir[u]) continue;
        if (v == P && e[i].ty == dir) Circle[dir] = dis + 1; // 计算环的长度
        else dfs(v, dis + 1, e[i].ty, dir);
    }
}
int main() {
    int n = read(), m = read();P = read() + 1;
    //原图中，每个点只保留最大的边，和次大的边。真正建图时，建的反向边。
    for (int i=1; i<=m; ++i) {
        int u = read() + 1, v = read() + 1;
        if (!dgr[u]) add_edge(v, u, 0), dgr[u] ++, fir[u] = v; // 建反向边，fir[u]：原图中u走出的最大的点，反向图中到u的最大的点。
        else if (dgr[u] == 1) add_edge(v, u, 1), dgr[u] ++;
        if (!dgr[v]) add_edge(u, v, 0), dgr[v] ++, fir[v] = u;
        else if (dgr[v] == 1) add_edge(u, v, 1), dgr[v] ++;
    }
    dfs(P, 0, 0, 0); //反向搜索，从P出发，走非最长边，即原图中从非最长边到P，从最长边出
    if (dgr[P] > 1) dfs(P, 0, 1, 1); // 走最长边，原图中从最长边到P，从非最长边出
    for (int i=0,lim=(n<<2); i<lim; ++i) { // 所有能到P的点在2n步内一定可以到达P一次，所以2n之后，sum[0/1][i]=sum[0/1][i+Circle[0/1]] 预处理4n
        sum[0][i] = cnt[0][i]; // 第i个时刻，多少个点从非最长边到P
        if (Circle[0] && i - Circle[0] >= 0) sum[0][i] += sum[0][i - Circle[0]]; // 从非最长边到P后，存在环的情况，从P的最长边出
        sum[1][i] = cnt[1][i]; // 第i个时刻，多少个点从最长边到P
        if (Circle[1] && i - Circle[1] >= 0) sum[1][i] += sum[1][i - Circle[1]]; // 从最长边到P后，存在环的情况，从非最长边出
    }
    int Q = read();
    // 从2n往后，sum[0/1][i]=sum[0/1][i+Circle[0/1]]，所以首先特判k是否小于2n，然后判断k>2n的情况试k回到2n~4n之间。
    // k一定是走了很多次圆圈，所以首先k%Circle，这是走圆圈之前走的步数，然后为了让k在[2n+1,4n]，让圆圈的步数是2n内最大的。即2n/Circle*Circle
    while (Q --) {
        int k = read(), ans = 0, t;
        if (k <= n * 2) ans = sum[0][k] + sum[1][k];
        else {
            if (Circle[0]) {
                t = (2 * n) / Circle[0]; 
                ans += sum[0][k % Circle[0] + t * Circle[0]];
            }
            if (Circle[1]) {
                t = (2 * n) / Circle[1]; 
                ans += sum[1][k % Circle[1] + t * Circle[1]];
            }
        } 
        printf("%d ",ans);
    }
    return 0;
}

T2

写完T1的60，已经花费了不少时间了，看T2的时候，感觉不太会做，写了暴力没管，（考完试刚结束，发现了一句话“一个字符串可以重复经过，但只算一次”，发现写错了，本来以为30分，感觉变成了?）。
总结：

没有判断出难度，实际上比T1简单。以后多做题。应该仔细想想。

正解：tarjan缩环，然后DAG上最长路。
一个字符串看成一个点，经过操作后可以到的点，可以看成一条边，然后相当于在图上跑一个最长路。
求出所有的字符串，然后暴力建边。对于每个操作，$n^4$枚举字符串，然后暴力建边。复杂度$O(n^4m)$
发现第一个操作，交换相邻位置，实际上是没有用的，有用的只是ABCD的个数，一定个数的ABCD的一状态，通过交换相邻位置，可以得到ABCD个数不变的所有状态。（就是对于一个字符串s='AABBCDDD'，如果这一状态可达，那么所有两个A两个B一个C三个D的字符串都可以由它交换相邻位置得到）。每个点只记录ABCD的个数。然后总点数是$33 \choose 3$隔板法。每个点的权值就是ABCD这些个数的所有的排列。为$\frac{n!}{a!b!c!d!}$
这个式子直接乘会爆，然后考虑这个式子怎么推。
$C_{a+b}^b = \frac{(a+b)!}{a!b!}$
$C_{a+b+c}^c = \frac{(a+b+c)!}{(a+b)!c!}$
$C_n^d = \frac{n!}{(n-d)!d!} =\frac{n!}{(a+b+c)!d!}$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 6000;
vector<int> e[N], T[N];
int dfn[N], low[N], sk[N], bel[N], dgr[N], q[N];
bool vis[N];
LL val[N], siz[N], dis[N], C[31][31];
int id[31][31][31];
int CntNode, Time_Index, tot, Top;
void getnum(int *num) {
    char ch = getchar();
    while (ch != 'A' && ch!='B' && ch!='C' && ch!='D') ch = getchar();
    while (ch == 'A' || ch=='B' || ch=='C' || ch=='D') num[ch-'A'] ++, ch=getchar();
}
void init(int n) {
    for (int i=0; i<=n; ++i) {
        C[i][0] = 1;
        for (int j=1; j<=i; ++j) 
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    for (int a=0; a<=n; ++a) 
        for (int b=0; a+b<=n; ++b) 
            for (int c=0; a+b+c<=n; ++c) 
                id[a][b][c] = ++CntNode, 
                val[CntNode] = C[a+b][b] * C[a+b+c][c] * C[n][n-a-b-c];
}
void tarjan(int u) {
    dfn[u] = low[u] = ++Time_Index;
    sk[++Top] = u;
    vis[u] = true;
    for (int sz=e[u].size(),i=0; i<sz; ++i) {
        int v = e[u][i];
        if (!dfn[v]) {
            tarjan(v); 
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++tot;
        do {
            siz[tot] += val[sk[Top]];
            vis[sk[Top]] = false;
            bel[sk[Top]] = tot;
            Top--;
        } while (sk[Top + 1] != u);
    }
}
LL topo() {
    int L = 1, R = 0;
    for (int i=1; i<=tot; ++i) 
        if (!dgr[i]) q[++R] = i, dis[i] = siz[i];
    LL Ans = 0;
    while (L <= R) {
        int u =q[L ++];
        Ans = max(Ans, dis[u]);
        for (int sz=T[u].size(),i=0; i<sz; ++i) {
            int v = T[u][i];
            dis[v] = max(dis[v], dis[u] + siz[v]);
            if (!(--dgr[v])) q[++R] = v;
        }
    }
    return Ans;
}
int main() {
    freopen("1.txt","r",stdin);
    int n = read(), m = read();
    init(n);
    for (int i=1; i<=m; ++i) {
        int num1[4] = {0, 0, 0, 0}, num2[4] = {0, 0, 0, 0};
        getnum(num1); getnum(num2);
        if (num1[0] == num2[0] && num1[1] == num2[1] && num1[2] == num2[2]) continue;
        for (int a=num1[0]; a<=n; ++a) {
            for (int b=num1[1]; a+b<=n; ++b) {
                for (int c=num1[2]; a+b+c<=n; ++c) {
                    if (n - a - b - c < num1[3]) break;
                    e[id[a][b][c]].push_back(id[a-num1[0]+num2[0]][b-num1[1]+num2[1]][c-num1[2]+num2[2]]);
                }
            }
        }
    }
    for (int i=1; i<=CntNode; ++i) 
        if (!dfn[i]) tarjan(i);
    for (int u=1; u<=CntNode; ++u) {
        for (int sz=e[u].size(),i=0; i<sz; ++i) {
            int v = e[u][i];
            if (bel[u] != bel[v]) T[bel[u]].push_back(bel[v]), dgr[bel[v]] ++;
        }
    }
    cout << topo();
    return 0;
}