只能膜拜 Renamoe 神。
首先可以注意到 \(\operatorname{(i \, or \, j) \, xor \, i}\)​ 其实是 j 与 i 补集的交，即 j & (~i)。

接下来就是神 Renamoe 的表演，首先因为这是跟位运算有关的求和，那么自然想到 fwt 那一套，而且这个东西长得也很 fwt，因为第一步转化后，里面的那一坨变成了 popcnt(j & (~i))，这个东西如果没有取反不就是 xor 卷积的构造吗？​

接下来考虑把他变得更像 xor 卷积，大力打表得到系数矩阵，里面只有 1 0，而我们期望只有 1 -1，发现矩阵乘 2 减 1 后可以变成这样，那么对矩阵乘二减一后，由于原来有 \(b_i = \sum_{j = 0} ^ {n - 1} g(i, j) a_j\)，每个系数更改后就有：

注意到 \(b_{n - 1}\) 其实是 \(a\) 数组求和，于是可以快速得到 \(b'\) 数组，那么现在 \(b'\) 数组乘新构造的矩阵就是 \(a\)​ 了，即 \(b' \times A = a\)，已知 \(b'\) 欲求 \(a\)，诶？这不是和原题没有区别吗？上面那么多都是废话吗？

并不是，注意到原来 popcnt 为偶数的位置系数会是 1，而现在仍然是 \(1\)，原来是奇数的位置是 \(0\)，而现在就会变成 \(-1\)​，这个奇偶关系和系数，就是 \((-1) ^ {\operatorname{popcnt}}\)，于是我们得到：

那什么，不太会公式里打 ~，于是写了中文(有点丑啊)，于是现在 \(b'\) 就是 \(a\) 的 fwt_xor 结果，唯一的区别就是多了一个取反，那么现在有两种做法，要么你按位讨论一下，得到这种构造的 ifwt_xor 如何还原，另一种做法就是手动取反，我们直接把 \(b'\) 序列 reverse 一下，这样每个位置就是标准的 fwt_xor 了，直接对反转后的序列跑 ifwt_xor 即可。

另外我是写一道题的题解然后放一道然后看一遍的，我得说 cnblogs 的样式比 typora 垃圾到不知道哪里去了。

直接暴力 sam 的题我没想到 \(\ldots\)​ 暴力从当前光标处往后在 sam 上查找就好了，对于每个节点维护一个 endpos 最小值，如果往后走的节点的 endpos 最小值满足要求，那就走，否则就输出当前节点对应的 len，如果根本没走，按照题意输出即可，也就是按照题意模拟就好了。

首先因为人是谁并不重要，我们只关心邮票，不关心在谁手里，于是一个人喜欢某个人手里的邮票，就转化为人向邮票连边，那么这个图就是一个二分图，现在一个人要拿某一张邮票，这意味着原来拥有的人必须去找别的邮票，那这是不是很像匈牙利算法？匹配一个人后，找原来的匹配点，你去看是不是仍有匹配，如果有就皆大欢喜，否则不让出手中的邮票，于是这就是一个匈牙利算法，如果最大匹配能恰等于人数，那就是可以让所有人都满足，否则不行。

一开始觉得很像 病毒，于是敲了 AC 自动机上去，暴力跑最长路往后匹配，这样的缺点是你跳 fail，你可能连续多跳几次，而不是只跳到最长的那个位置，所以复杂度并不会分析，然而考场上只跳了一次所以只有 \(50pts\) 的样子，好像很多人说 hash 啊，然而没太听懂，我感觉是任意两个串，长度超过 \(k - 1\) 的链接都要试着匹配，然后建图跑最长路，不清楚复杂度，另外一个比较好的做法是在广义 sam 上跑，大概就是源点向所有可能的起点连边，起点向可能往后走的点连边，所有可能成为终点的点向汇点连边，所有可能的源点就是 \(len \ge k - 1\) 的点，所有可能的汇点就是 \(len \ge k\)​ 的点，往后走的就是 sam 自带的转移，另外，我们还可能跳后缀链接以求得可以走更多的点，当然，这里需要注意的是，跳的后缀链接长度需要 \(\ge k - 1\)，否则的话就会构造出非法的串。

有限制的位置和只有 \(20\) 个，那这不就是 devu 和 鲜花 这道题么？非负整数解计数其实就是不同盒子同样球，允许空盒方案数。容易得到结果就是一个组合数，考虑限制那就容斥好了，暴力枚举破坏了哪些限制，具体破坏就让他超过上界，剩下的进行非负整数解计数即可。

二分答案后，跑费用流就好了，边权设为 1，毕竟费用流跑的是最短路，如果最短路长度小于二分的结果，这时候答案是可以直接计算的，也就是这一波的增广结果可以直接计算，因为已知结束时间了。

另一种做法是在 zzz 先生的博客里提到的，因为你二分其实做的也是每次增广之后计算答案，看答案是否超过 k，那么不妨直接贪心，每次加入一条新流，就用新的时间和上一次的时间差乘上之前的流量和，这就是这段时间里原来的最短路输送的流量，直到一个时刻，剩余的人数小于 0，这时候就可以结束了，每次增广一条流的时候更新一下答案。

using i64 = long long;
constexpr i64 inf = 1e18;

struct Graph {
    std::vector<int> h;
    struct Edge {
        int to, nxt; i64 flow, cost; 
        Edge(int to, int nxt, i64 flow, i64 cost) : to(to), nxt(nxt), flow(flow), cost(cost) {}
    };
    std::vector<Edge> e;
    Graph(int n) : h(n + 1, -1) {}

    inline void add(int x, int y, i64 flow, i64 cost) {
        e.emplace_back(y, h[x], flow, cost);
        h[x] = e.size() - 1;
    }

    inline void add_edge(int x, int y, i64 flow, i64 cost) {
        add(x, y, flow, cost), add(y, x, 0, -cost);
    }

    inline void init(int m) {
        for (int i = 1; i <= m; ++i) {
            int u, v; i64 flow;
            std::cin >> u >> v >> flow;
            ++u, ++v;
            add_edge(u, v, flow, 1);
        }
    }
};

struct Ek {
    Graph &G;
    std::vector<i64> dist, flow;
    std::vector<int> pre, inq;
    Ek(Graph &G, int n) : G(G), dist(n + 1), flow(n + 1), pre(n + 1), inq(n + 1) {}
    
    inline bool spfa(int S, int T) {
        std::fill(dist.begin(), dist.end(), inf);
        std::fill(flow.begin(), flow.end(), 0);
        std::fill(pre.begin(), pre.end(), -1);

        flow[S] = inf;
        dist[S] = 0;

        std::queue<int> q;
        q.push(S);

        while (q.size()) {
            int x = q.front();
            q.pop();
            inq[x] = false;
            for (int y, p = G.h[x]; ~p && (y = G.e[p].to, true); p = G.e[p].nxt) {
                if (G.e[p].flow > 0 && dist[y] > dist[x] + G.e[p].cost) {
                    pre[y] = p;
                    dist[y] = dist[x] + G.e[p].cost;
                    flow[y] = std::min(flow[x], G.e[p].flow);
                    if (!inq[y]) 
                        q.push(y), inq[y] = true;
                }
            }
        }

        return flow[T] > 0;
    }

    inline i64 solve(int n, int k) {
        int S = 1, T = n;
        i64 lst = 0, sflow = 0, ans = inf;
        // lst 上一次时间 sflow 之前的总流量 ans 是答案
        while (k > 0 && spfa(S, T)) {
            int x = T;
            for (; ~pre[x]; x = G.e[pre[x] ^ 1].to) {
                G.e[pre[x]].flow -= flow[T], G.e[pre[x] ^ 1].flow += flow[T];
            }
            k -= (dist[T] - lst) * sflow + flow[T];
            // k 减少之前流以及当前流
            sflow += flow[T];
            // 更新总流量
            lst = dist[T];
            // 更新时间
            ans = std::min(ans, dist[T] + (k - 1) / sflow + 1);
            // 更新答案
        }
        if (ans == inf) 
            return -1;
        else 
            return ans;
    }
};

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    while (std::cin >> n >> m >> k) {
        Graph G(n);
        G.init(m);

        if (!k) {
            std::cout << 0 << '\n';
            continue;
        }

        i64 t = Ek(G, n).solve(n, k);
        if (t == -1) 
            std::cout << "No solution" << '\n';
        else 
            std::cout << t << '\n';
    }
}

还是比较好想的，首先按照到达时间排序，如果一个人到了，去看看有没有工作室，应该占用哪个工作室呢？因为持续时间都是一样的，所以肯定是选择能被使用的最早的工作室，那么可以用一个堆维护。

对于第 $ i $ 个人，如果堆顶时间 \(top + m \lt now\) ，那么弹掉，如果弹掉后存在 \(top \le now \; \and \; top + m \gt now\) 那就可以不用开锁直接让他进入这个工作室，然后弹掉并且加入一个 \(now + len_i\) 即可，(now 就是指 \(s_i\))，否则如果不存在，那说明必须新开一个，答案加一并放入一个 \(now + len_i\) 即可。

考虑反悔贪心，每次取出区间最大子段和，然后取反这段区间，接下来选这里面的数意味着反悔，然后这样取 \(k\)​ 次就好了，当然，一旦贡献为负直接停下来就行了。

为什么这个是对的？

考虑费用流，让 \(S\) 连向一个分流点，流量为 \(k\)。分流点连向每个点，每个点向下一个点连自己的费用，同时向汇点连边，这些边流量都是 1，跑最大费用流。

那你考虑费用流是怎么做的，先找出一条最长路，增广，这可以理解为选取最大区间，然后取反，然后找最长路，一共增广 \(k\) 次，这和上面的操作就一模一样，

由于费用流是对的，所以上面的贪心也是对的，当然，感性理解反悔贪心确实挺对。

然而这还不是终点，终点是你写完代码的时刻。

因为，为了维护最大子段和，线段树上要维护区间和，前缀最大后缀最大和最大子段和，为了维护取反，线段树上需要维护前缀后缀全部最小，为了查询最大子段和之后能知道取反的位置，你需要维护前后缀全局，最大最小段，的左右端点，最后需要维护一个取反的 \(lazy\) 标记，那么这道题就做完了，boss 竟是写代码。