我我我我居然独立做出了全场只有不到 $400$ 人过的 E 题！

——可惜是在比赛结束以后……

A

水题

B

水题

C

交换两个或者把前一半和后一半交换，求 $m$ 次变换后的结果。

直接把前面一半和后面一半分开存就可以了。

D

$n$ 个点 $m$ 条边的无向图，求用三种颜色染色后每条边相连的点不同的图有几种。

一看数据范围显然是一个搜索题，不过直接搜索会有一些问题，因为先搜到哪个的不同可能图染色后是相同的，会造成重复，既然如此，那我们随便指定一个顺序就可以了。

然后居然错了三次才过，原因如下（全都是很傻的）：

1. 没定顺序，以为搜一个退出就行
2. 认为度数有 $3$ 以上的都不行
3. 数组开小！

E

看了 standing 发现通过人数甚至比 D 要多！一下子就有了信心，不放弃地想。

看到题目大概就是两种想法，一是神奇的组合数学，二是 dp。通过组合数可以非常方便的算出一条限制的结果，但是对于多条限制的合并，组合数似乎吃不消了，因为它会变得无比复杂。

那么考虑的 dp, 数据范围只有 $18$, 可以进行状压，而且非常容易想到一个 dp, $f[S]$ 表示已选的数集合为 $S$ 的方案数，那么再枚举下一个，然后再进行验证是否可行以及转移，时间复杂度为 $2^nn^2m$, 显然会超时。

而转移的瓶颈在状态的验证。稍加观察就可以发现每一个条件只对状态中恰好有 $x$ 个 $1$ 的情况下有效，因为前面的都被前面的约束了，而且这种约束只和当前的状态有关，那么就可以分开来独立计算了。

时间复杂度的瓶颈仍然在验证状态是否可行，时间大约是 $2^nn^2$ 的，因为那个 $m$ 是被分掉的，不是乘上去的。

好耶，这些我都想到了，那么我的排名是不是要杀进前 $400$ 了呢？

并不，因为我 $i$ 和 $j$ 写反了！

痛失 $500$ 分，呜呜。 可能最后时间有点紧了，因为到最后 $15$ 分钟才想到以上的正解，到最后三分钟才写完，没有什么时间调试了。不过若没有这个手残还是可以过的。

代码。

#include <cstdio>
#include <algorithm>
#define int long long
const int N = 20;
struct twt {
    int x, y, z;
    bool operator < (twt b) { return x < b.x; }
} a[N];
int n, m, L[N], R[N], g[N], f[(1 << 19) + 5];
bool flag[(1 << 19) + 5];
int popcount(int x) { return (x != 0) ? (popcount(x&(x-1))+1) : 0; }
signed main() {
    scanf("%lld%lld", &n, &m);
    for(int i = 1; i <= m; i++) scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
    std::sort(a+1, a+1+m);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) 
            if(a[j].x == i) {
                L[i] = j;
                break;
            }
        for(int j = m; j >= 1; j--) 
            if(a[j].x == i) {
                R[i] = j;
                break;
            }
    }
    for(int S = 1; S < (1 << n); S++) {
        flag[S] = 1;
        int k = popcount(S);
        if(L[k] == 0) continue;
        for(int i = 1; i <= n; i++) g[i] = 0;
        for(int i = 1, j = 1; i <= k; i++) {
            while((S & (1 << j)) == 0) j++;
            for(int l = j; l <= n; l++) g[l] ++;
            j++;
        }
        for(int i = L[k]; i <= R[k]; i++) 
            flag[S] &= (g[a[i].y] <= a[i].z);
    }
    f[0] = 1;
    for(int S = 0; S < (1 << n); S++) 
        for(int i = 0; i <= 18; i++)
            if(((S & (1 << i)) == 0) && flag[S | (1 << i)]) f[S | (1 << i)] += f[S];
    printf("%lld", f[(1 << n) - 1]);
    return 0;
}

不过还是上分了！