A. Anu Has a Function

容易发现 f(x,y) 实际上就是把 x 中 x 和 y 的二进制表示都为 1 的位抠掉。那么只和第一个数选的是什么有关，与剩下的数的顺序无关。预处理每个前缀和后缀的或和，再枚举每一个数作为第一个数即可。

B. Aerodynamic

将图形 P 的一个顶点 (x,y) 移动到原点 (0,0) 处，相当于将整个图形沿向量 (-x,-y) 移动。对于所有顶点，可以发现有 T=P+(-P)，+ 表示闵可夫斯基和。于是可以归并起来直接求 T，再大力判相似。

但这样做不够好，观察样例可以看出，这个图形必须是中心对称的。那么就有结论：n 为偶数，且 \overrightarrow{P_iP_{i+1}}+\overrightarrow{P_{i+\frac{n}{2}}P_{i+\frac{n}{2}+1}},\forall i\in[1,\frac{n}{2}]。这就很容易做了。

C. Water Balance

一道和 【NOI2016】国王饮水记 很相似的题，看到题我就往斜率上想的。。

求字典序最小就是套路的依次确定，也就是固定了一段区间的左端点去找右端点，使这段的平均值最小。设序列的前缀和为 \{s_n\}，考虑当前左端点为 i，右端点的其中两个选择 j,k，选 j 比选 k 优的条件：

对于这个式子，可以将 P_i(i,s_i) 看成二维平面上的一个点，也就是要 P_iP_j 的斜率最小。可以发现只有 P_j 在点集 \{P_0,P_1,\cdots,P_n\} 的下凸包上才有可能被选到。进一步观察可以发现，对于 i=0\to n ，决策在凸包上是单调的。于是一个指针向后扫即可做到均摊 O(1) 决策。时间复杂度 O(n)。代码：

#include <cstdio>
typedef long long ll;
const int MAXN=1100000;
int a[MAXN]; ll s[MAXN];
int q[MAXN];
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    int n, k=0;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    q[++k]=0;
    for (int i=1; i<=n; i++)
    {
        s[i]=s[i-1]+a[i];
        while (k>=2&&(s[i]-s[q[k]])*(q[k]-q[k-1])<=(s[q[k]]-s[q[k-1]])*(i-q[k])) k--;
        q[++k]=i;
    }
    for (int i=1, j=1; i<=n; i=q[j]+1)
    {
        while (j<k&&(s[q[j+1]]-s[i-1])*(q[j]-i+1)<=(s[q[j]]-s[i-1])*(q[j+1]-i+1)) j++;
        double t=1.0*(s[q[j]]-s[i-1])/(q[j]-i+1);
        for (int p=i; p<=q[j]; p++) printf("%.10lf\n", t);
    }
    return 0;
}

D. Around the World

好题。和线性代数有一点相关。

考虑把 1 号点去掉，剩下的点形成了若干个连通分量。这些连通分量可以分为两种，一种是原来与 1 号点只有一条边相连的，另一种是原来有包含 1 号点的三元环的。对于第一种情况，考虑这条边可不可以选；对于第二种情况，考虑可不可以选这个连通分量；如果可以选，那么可不可以包含有 1 的三元环（断其中哪一条边影响相同）。并分别考虑它们中的非平凡环可以构成哪些异或值。

对于一个连通分量，只经过它的非平凡环的异或值的取值实际上就是这个分量里所有简单环的异或值。考虑它的任意一棵 DFS 树，对于它的每条非树边，求出这条边与树边构成的简单环的异或值，把它看成一个向量插入线性基中。那么这个线性基就是这些向量的扩张的最小生成集（感性理解）。如果有一组向量线性相关（即一个向量无法被插入线性基），那么显然这个分量里有异或为 0 的简单环，我们就不能选这个分量。

接下来考虑 DP。对于每个连通分量有 1-3 种决策，每种决策会贡献一个线性基。注意到空间 \mathbb{Z}_2^5 中的向量子空间共有 374 个（可以通过暴力程序得到），那么本质不同的线性基也只有 374 个。记 f(i,j) 为决策到第 i 个连通分量，当前线性基为 j 的方案数。预处理线性基的合并即可 O(1) 转移，最终的答案为最后一个分量的状态总和。时间复杂度 O(374n)。代码：

#include <cstdio>
#include <vector>
#include <set>
using namespace std;
const int MAXN=110000;
const int MAXC=400;
const int P=1E9+7; 
struct Edge
{
    int to, val;
    Edge(int v, int w): to(v), val(w) {}
};
struct XorBasis
{
    int d[5];
    void clear()
    {
        d[0]=d[1]=d[2]=d[3]=d[4]=0;
    }
    bool insert(int x)
    {
        for (int i=4; i>=0; i--)
            if (x&1<<i)
                if (d[i]) x^=d[i];
                else
                {
                    d[i]=x;
                    for (int j=0; j<i; j++)
                        if (d[j]&&d[i]&1<<j) d[i]^=d[j];
                    for (int j=i+1; j<5; j++)
                        if (d[j]&1<<i) d[j]^=d[i];
                    return 1;
                }
        return 0;
    }
    int space()
    {
        return d[0]|d[1]<<1|d[2]<<3|d[3]<<6|d[4]<<10;
    }
};
vector<Edge> g[MAXN];
int dfc, dfn[MAXN], val[MAXN];
int cnt, id[MAXN]; XorBasis bas[MAXC];
int trans[MAXC][MAXC];
int blk, p1[MAXN], p2[MAXN];
int f[MAXN][MAXC];
inline int add(int& x, int y)
{
    x+=y;
    if (x>=P) x-=P;
}
void dfs(int u, int f)
{
    static XorBasis xb;
    static int cir;
    dfn[u]=++dfc;
    for (int i=0; i<g[u].size(); i++)
    {
        int v=g[u][i].to, w=g[u][i].val;
        if (!dfn[v])
        {
            if (u==1) xb.clear(), cir=-1, blk++;
            val[v]=val[u]^w; dfs(v, u);
        }
        else if (dfn[v]<dfn[u]&&v!=f)
            if (v==1) cir=val[u]^val[v]^w;
            else if (!xb.insert(val[u]^val[v]^w))
                p1[blk]=p2[blk]=-1;
    }
    if (f==1&&~p1[blk])
    {
        p1[blk]=xb.space();
        if (~cir)
        {
            p2[blk]=p1[blk];
            if (xb.insert(cir)) p1[blk]=xb.space();
            else p1[blk]=-1;
        }
        else p2[blk]=-1;
    }
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i=1; i<=m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back(Edge(v, w));
        g[v].push_back(Edge(u, w));
    }
    for (int t[5]={0}; t[0]<32; t[0]++)
    for (t[1]=t[0]; t[1]<32; t[1]++)
    for (t[2]=t[1]; t[2]<32; t[2]++)
    for (t[3]=t[2]; t[3]<32; t[3]++)
    for (t[4]=t[3]; t[4]<32; t[4]++)
    {
        XorBasis tmp; tmp.clear();
        for (int i=0; i<5; i++) tmp.insert(t[i]);
        int p=tmp.space();
        if (!id[p]) id[p]=++cnt, bas[cnt]=tmp;
    }
    for (int i=1; i<=cnt; i++)
        for (int j=1; j<=cnt; j++)
        {
            XorBasis tmp=bas[i];
            for (int k=0; k<5; k++)
                if (bas[j].d[k]&&!tmp.insert(bas[j].d[k]))
                { trans[i][j]=-1; break; }
            if (~trans[i][j]) trans[i][j]=tmp.space();
        }
    dfs(1, 0);
    f[0][1]=1;
    for (int i=1; i<=blk; i++)
        for (int j=1; j<=cnt; j++)
        {
            add(f[i][j], f[i-1][j]);
            if (~p1[i]&&~trans[j][id[p1[i]]])
                add(f[i][id[trans[j][id[p1[i]]]]], f[i-1][j]);
            if (~p2[i]&&~trans[j][id[p2[i]]])
                add(f[i][id[trans[j][id[p2[i]]]]], 2*f[i-1][j]%P);
        }
    int ans=0;
    for (int i=1; i<=cnt; i++)
        ans=(ans+f[blk][i])%P;
    printf("%d\n", ans);
    return 0;
}