发表于 | 分类于 |

这篇题解写的是官方正解。

正解需要以下知识

  • 整体DP
  • 多项式初步
  • 拉格朗日插值法 (可以在这里学)
  • 生成函数
  • 线段树合并

题目大意：

​ 给一颗有$N$个点的树，点权在$1 \sim W$之间，求树的每一个联通块的第$K$大点权之和。

看到这个题时，我的心里是懵逼的。

我们首先开始考虑转化题目。

$(1)$到$(2)$的过程是枚举每个权值的贡献。

$(2)$到$(3)$的过程比较难理解，我们直接考虑从每个$i$在公式$(2)$中会被算多少次，显然是$i$次。

那在公式$(3)$中也是会被算$i$次。

$(3)$到$(4)$的过程就比较显然了，这里不再赘述。

那么到现在，问题就变得比较显然了：

枚举权值$v$,求树上权值$v$出现次数超过$k$的联通块个数。

我们设计一个DP。

$f[i][j][k]$表示以$i$为根的子树中，权值大于等于$j$的权值出现为$k$次的方案数。

转移显然

最后答案就是$\sum\limits{k’=1}^{k}\sum\limits{j=1}^{W}\sum\limits_{i=1}^{N} f[i][j][k’]$

复杂度$\mathcal{O}(N^2*k)$，据说有人大力过了。

我们考虑优化这个转移，不难发现，这个DP其实是背包的一种，而转移就是背包的合并。

那我们不妨直接考虑生成函数。

设$F[i][j]$表示以$i$为根的子树中，权值大于等于$j$的权值的生成函数。

则$F[i][j]=\sum\limits_{k=0}^{n} f[i][j][k] \times x^k$，这是一个$N$次多项式。

但是最后我们要求的是整棵树的所有$F[i][j]$之和，所以我们不妨再设一个$G[i][j]$。

$G[i][j]=\sum\limits_{x \in subtree(i)}F[x][j]$

$F[i][j]$在转移时是多项式卷积，还是很慢，$G[i][j]$在转移时只要维护一下就行了。

所以我们考虑将它转换为$N+1$个点值，这样的话转移时就是普通乘法了。

我们就令$x=1 \sim N+1$，然后将所有$G[i][j]$在$x$时的值都求出来，最后进行拉格朗日插值法将原始的多项式差出来就行了，可具体怎么实现呢？

我们首先在最外层枚举$x \in [1,N+1]$，然后每次进行一次$DFS$，但具体如何进行转移呢？

我们不难发现，$F[i][j] \leftarrow F[son[i]][j]$转移过程中其实就是$[j]$的对应位置相乘。

所以我们可以使用整体$DP$的思想在每个点上都维护一颗线段树，然后在转移时进行线段树合并就可以了。

正解差不多就是这个意思。

具体合并方法如下：

初始化：

转移时： $F[i][j] \times =(F[son[i]][j]+1) , G[i][j]+=G[son[i]][j]$

最后，$G[i][j]+=F[i][j]$。

我们可以将$F[son[i]][j]+1$的操作放在$DFS$ son[i]后进行。

可是你说了这么多，线段树到底应该怎么写？

我们设变换$(a,b,c,d)$可以使$(f,g)$变换为$(a \times f+b,c \times f+d+g)$

然后每个线段树维护一个变换即可。

变换结合的话手推一下即可。

注意：变换在普遍情况下没有交换律，只有结合律。

剩下的实现方法详见代码。

注意以下坑点：

  • 模数是64123，做乘法时要用unsigned int。
  • unsigned int 取模时模数必须是unsigned类型。
  • 初始化变换时应该是$(1,0,0,0)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<stack>
typedef unsigned int uint;
using namespace std;
const uint P=64123;
const int MAXN=1700;
const int MAXM=5000;
struct __edge{
    int nxt,v;
}Edge[MAXM];
int head[MAXN],cnt_e,rt[MAXN],stk[MAXN<<6],top,cnt,d[MAXN],n,k,w,u,v,ans[MAXN],f[MAXN],tmp[MAXN];
int inv[P+10];
inline void add(int u,int v) {Edge[++cnt_e].v=v;Edge[cnt_e].nxt=head[u];head[u]=cnt_e;}
struct data{
    uint a,b,c,d;
    inline void clear(){a=1;b=c=d=0;}
    inline data(uint _a=1,uint _b=0,uint _c=0,uint _d=0):a(_a),b(_b),c(_c),d(_d){}
    inline data operator * (const data &rhs) const {return data(a*rhs.a%P,(rhs.b+b*rhs.a%P)%P,(a*rhs.c%P+c)%P,(b*rhs.c%P+d+rhs.d)%P);}
    inline data operator *= (const data &rhs) {return (*this)=(*this)*rhs;}
};
struct node{
    int ls,rs;
    data val;
    node(){val.a=1;val.b=val.c=val.d=ls=rs=0;}
    inline void clear(){val.a=1;val.b=val.c=val.d=ls=rs=0;}
}t[MAXN<<6];
inline int newnode() {if(top) return stk[top--];else return ++cnt;}
inline void delnode(int &x)
{
    if(!x) return;
    delnode(t[x].ls);delnode(t[x].rs);
    stk[++top]=x;t[x].clear();x=0;
}
inline void pushdown(const int &x)
{
    if(!t[x].ls) t[x].ls=newnode();
    if(!t[x].rs) t[x].rs=newnode();
    t[t[x].ls].val*=t[x].val;
    t[t[x].rs].val*=t[x].val;
    t[x].val.clear();
}
void change(int &x,int l,int r,int cl,int cr,data val)
{
    if(!x) x=newnode();
    if(cl<=l&&r<=cr) {t[x].val*=val;return;}
    int mid=(l+r)>>1;pushdown(x);
    if(cl<=mid) change(t[x].ls,l,mid,cl,cr,val);
    if(cr>mid)  change(t[x].rs,mid+1,r,cl,cr,val);
}
int merge(int &x,int &y)
{
    if(!x||!y) return x|y;
    if(!t[x].ls&&!t[x].rs)  swap(x,y);
    if(!t[y].ls&&!t[y].rs)
    {
        t[x].val*=data(t[y].val.b,0,0,0);
        t[x].val*=data(1,0,0,t[y].val.d);
        return x;
    }
    pushdown(x);pushdown(y);
    t[x].ls=merge(t[x].ls,t[y].ls);
    t[x].rs=merge(t[x].rs,t[y].rs);
    return x;
}
uint query(int x,int l,int r)
{
    if(l==r) return t[x].val.d;
    int mid=(l+r)>>1;
    uint ret=0;
    pushdown(x);
    ret=query(t[x].ls,l,mid);
    (ret+=query(t[x].rs,mid+1,r))%=P;
    return ret;
}
void dfs(int x,int fa,int k0)
{
    change(rt[x],1,w,1,w,data(0,1,0,0));
    for(int i=head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].v;
        if(v==fa) continue;
        dfs(v,x,k0);
        merge(rt[x],rt[v]);
        delnode(rt[v]);
    }
    change(rt[x],1,w,1,d[x],data(k0,0,0,0));
    change(rt[x],1,w,1,w,data(1,0,1,0));
    change(rt[x],1,w,1,w,data(1,1,0,0));
}
uint Lagrange_interpolation()
{
    uint ret=0;
    memset(f,0,sizeof f);f[0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int j=n+1;j>=1;j--)
            f[j]=f[j]*(P-i)%P,f[j]=(f[j]+f[j-1])%P;
        f[0]=f[0]*(P-i)%P;
    }
    for(int i=1;i<=n+1;i++)
    {
        memcpy(tmp,f,sizeof(uint)*(n+1));
        for(int j=0;j<=n;j++)  //divide by (x-i)
            tmp[j]=P-tmp[j]*inv[i]%P,tmp[j+1]=(tmp[j+1]-tmp[j]+P)%P;
        uint tans=0;
        for(int j=k;j<=n;j++) tans=(tans+tmp[j])%P;
        for(int j=1;j<=n+1;j++)
        {
            if(i==j) continue;
            if(j<i) tans=tans*inv[i-j]%P;
            else tans=tans*(P-inv[j-i])%P;
        }
        ret=(ret+tans*ans[i]%P)%P;
    }
    return ret;
}
int main()
{
    scanf("%d%d%d",&n,&k,&w);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=1;i<n;i++)  scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n+1;i++)
    {
        dfs(1,0,i);
        ans[i]=query(rt[1],1,w);
        delnode(rt[1]);
    }
    inv[1]=1;
    for(int i=2;i<P;i++)
        inv[i]=(P-(P/i)*inv[P%i]%P)%P,assert(inv[i]>0);
    printf("%u\n",Lagrange_interpolation());
}

发表于 | 分类于 |

拉格朗日插值法是个好东西。

它能干什么呢？

比如说你有一个未知的$N$次多项式，并且你有$N+1$ 个点值，那么你可以$\mathcal{O}(N^2)$地求出它的系数。

（高斯消元就不说了）

我们考虑怎么做，

先考虑一个问题，如果你有一个未知的$N$次多项式并且你有$N+1$ 个点值，那么再给你一个$x$，你能不能求出它所对应的函数值。

（编不下去了）直接看公式

考虑这个式子的正确性，我们带入已知的点值，比如说$x_3$，那么只有当$i=3$时，前面的分式值为一，其余时候，前面的分式值为$0$。所以这个式子是对的。（记住就好了）

那这只是带一个值进去的时候，我如果想求多项式怎么办？

这就是我们求多项式时的公式，那我们应该怎么算？

不难发现，真正难算的地方时分子部分，分母部分是一个实数。

那我们应该怎么处理？

不难发现，对于所有$i$，分子的形式很相像，那我们不妨先算出$\prod\limits_{i=1}^{n}(x-x_i)$，然后再除一下就行了。

暴力计算显然是$\mathcal{O}(N^3)$的。

So?

假设我们已经求完了前$i-1$项（记为$f’(x)$），现在要求第$i$项，那我们应该怎么做？

我们要算$f’(x) \times (x-x_i)$。

我们不难发现，答案是先将自己乘$-x_i$，然后将自己加到下一位。

我们就可以从高向低枚举次数，然后做转移即可。

那除法也一样，逆序操作即可。

那么我们就算出来了这个多项式的各个系数。

总复杂度$\mathcal{O}(N^2)$

发表于 | 分类于 |

预备知识

基

​ 基是线性代数中的一个概念，它是描述、刻画向量空间的基本工具。而在OI题目中，线性基描述的向量空间一般是异或空间。

向量空间

定义$(F,V,+,\cdot)$为向量空间，其中$F$为域，$V$为集合，$V$中的元素称为向量，$+$为向量加法，$\cdot$为标量乘法。

线性无关

​ 对于向量空间中 $V$上 $n $个元素的向量组$ (\mathbf{v}1, \ldots, \mathbf{v}_n)$，若存在不全为 $0$ 的数 $a_i \in F$，满$a{1}\mathbf {v} {1}+a{2}\mathbf {v} {2}+\ldots +a{n}\mathbf {v} _{n} = 0$则称这 $n$个向量线性相关，否则称为线性无关。

线性组合

​ 对于向量空间中 $V$ 上 $n$ 个元素的向量组 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$，其线性组合是如下形式的向量

$a{1}\mathbf{v}{1} + a{2}\mathbf {v} {2}+\ldots +a{n}\mathbf {v} {n}$其中 $a_1, \ldots, a_n \in F$a。一组向量线性无关$ \Leftrightarrow $没有向量可用有限个其他向量的线性组合所表示

张成

对于向量空间中 $V$ 上 $n$ 个元素的向量组$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$，其所有线性组合所构成的集合称为$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$的张成，记为$ \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$。

基

若向量空间 $V$ 中向量组 $\mathfrak {B}$ 既是线性无关的又可以张成 $V$，则称其为 $V $的基（basis）。

$\mathfrak {B}$ 中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

性质

设 $\mathfrak {B}​$ 是向量空间 $V ​$的基。则$ \mathfrak {B}​$具有以下性质：

  1. $V$ 是$ \mathfrak {B}$ 的极小生成集，就是说只有 $\mathfrak {B}$ 能张成 $V，而它的任何真子集都不张成全部的向量空间。
  2. $\mathfrak {B}$ 是 $V$ 中线性无关向量的极大集合，就是说 $\mathfrak {B}$ 在 $V $中是线性无关集合，而且 $V$ 中没有其他线性无关集合包含它作为真子集。
  3. $V $中所有的向量都可以按唯一的方式表达为$ \mathfrak {B}$中向量的线性组合。

第三点尤其重要，感性的理解，基就是向量空间中的一个子集，它可以通过唯一的线性组合，来张成向量空间中所有的向量，这样就可以大大的缩小我们向量空间的大小。

线性相关性引理

如果$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$在 $V$ 中是线性相关的，并且 $\mathbf{v}_1 \neq 0$，则有至少一个 $j \in {2, \ldots, m}$使得下列成立：

  1. $\mathbf{v}j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}{j - 1})$；
  2. 如果从 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 去掉第$j $项，则剩余向量组的张成仍然等于$ \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})$。

线性基介绍(口胡)

线性基是维护了一个数集的某些信息的集合(?)。

它可以将原来大小为$\text{N}$的数集在只求$\text{Xor}$和时压缩为$64$。

换句话说，你原来的数集互相异或出来的数的集合等于线性基中的数互相异或出来的数。

( 还是很有用的东西。)

线性基求法

我在网上看线性基求法时，看到了如下两种线性基求法：

  1. 复杂度$O(64n)$

    1
    2
    3
    4
    5
    6
    7
    for(int i=1;i<=n;i++)
            for(int j=62;~j;j--)
                if(a[i]>>j&1)
                {
                    if(b[j]) a[i]^=b[j];
                    else {b[j]=a[i];break;}
                }

    其中，$\text{a}$数组是原来的数集，$\text{b}$是线性基。

    注意，这种求法求出的线性基是上三角矩阵。

  2. 复杂度$O(64^2n)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    for(int i=1;i<=cnt;i++)
            for(int j=62;~j;j--)
                if(lop[i]>>j&1)
                {
                    if(b[j]) lop[i]^=b[j];
                    else
                    {
                        b[j]=lop[i];
                        for(int k=j-1;k>=1;k--) if(b[k]&&b[j]>>k&1) b[j]^=b[k];
                        for(int k=j+1;k<=62;k++) if(b[k]>>j&1) b[k]^=b[j];
                        break;
                    }
                }

    ​

    可以发现，这种求法只比上面的求法多了两句话：

    1
    2
    for(int k=j-1;k>=1;k--) if(b[k]&&b[j]>>k&1) b[j]^=b[k];
    for(int k=j+1;k<=62;k++) if(b[k]>>j&1) b[k]^=b[j];

    不难发现，这两句话是高斯消元的过程，这种线性基求法求出来的线性基是对角矩阵。

发表于 | 分类于 |

题目大意

你有一张$\text{N}$个点$\text{M}$条边的无向图，每条边上都有权值，现在请你求出来一条路径，使得这条路径上所有边权的异或和最大。

题解

前置技能：线性基 (不会的戳这里线性基学习笔记)

我们可以发现，这张图上会出现很多的环，而如果走一个环，就会只获得这个环的异或和。因为在非环路都走了两遍，所以我们就可以将所有环都求出来，然后随意找一条从$1$到$N$的路径，并使用线性基贪心地选，这样就可以选出最大的路径了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAXN=1E5+5;
const int MAXM=2E5+5;
struct node{
    int nxt,v;
    ll w;
}Edge[MAXM];
int n,m,u,v;
ll w;
int head[MAXN],cnt_e,cnt;
ll dis[MAXN],lop[MAXM],b[64];
bool vis[MAXN];
inline void add(int u,int v,ll w)
{
    Edge[++cnt_e].v=v;
    Edge[cnt_e].nxt=head[u];
    Edge[cnt_e].w=w;
    head[u]=cnt_e;
}
void dfs(int x,int fa)
{
    vis[x]=1;
    for(int i=head[x];i;i=Edge[i].nxt)
    {
        int v=Edge[i].v;
        if(v==fa) continue;
        if(vis[v]) {lop[++cnt]=dis[x]^dis[v]^Edge[i].w;continue;}
        dis[v]=dis[x]^Edge[i].w;
        dfs(v,x);
    }
}
void build()
{
    for(int i=1;i<=cnt;i++)
        for(int j=62;~j;j--)
            if(lop[i]>>j&1)
            {
                if(b[j]) lop[i]^=b[j];
                else
                {
                    b[j]=lop[i];
                    for(int k=j-1;k>=1;k--) if(b[k]&&b[j]>>k&1) b[j]^=b[k];
                    for(int k=j+1;k<=62;k++) if(b[k]>>j&1) b[k]^=b[j];
                    break;
                }
            }
}
ll solve(ll s)
{
    ll ret=s;
    for(int i=62;~i;i--)
        if((ret^b[i])>ret)
            ret^=b[i];
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    dfs(1,0);
    build();
    printf("%lld\n",solve(dis[n]));
}

发表于 | 分类于 |

  1. 题目描述

    求小于 $ 120 $ 且与 $ 120 $ 互质的正整数个数。

  2. 做法

    1. 普通做法

      将 $ 120 $ 分解质因数，可发现 $ 120=2^{3}\times3\times5 $。

      设 $A=\left{x|(2|x)且x\le120\right}$,$ B=\left{x|(3|x)且x\le120\right} $,$ C=\left{x|(5|x)且x\le120\right} $。

      则 $ |A|=59 $ $ |B|=39 $

      则小于 $ 120 $ 的正整数中，与 $ 120 $ 不互质的个数为 $ | A \cup B \cup C | $ 。

      由容斥原理可知。。。（略）

    2. 文艺做法

      由题意可知，要求 $ \varphi(120) $ 。

      将 $ 120 $ 分解质因数，$ 120=2^{3} \times 3 \times 5 $。

      所以 $ \varphi(120)=120 \times \left(1-\frac{1}{2}\right) \times \left(1-\frac{1}{3}\right) \times \left(1-\frac{1}{5}\right) $

    3. 智障做法

      由莫比乌斯反演，可知 $ \varphi= \mu \times id $

      所以 $ \varphi=\sum_{d|120}^{120} \mu(d) \times id(\frac{120}{d}) $

      带值，求出 $ \varphi(120) $

    4. OI做法

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      void init()
      {
          phi[1]=sum[1]=1;
          for(int i=2;i<=siz;i++)
          {
              if(!vis[i])
              {
                  prime[++vnum]=i;
                  phi[i]=i-1;
              }
              for(int j=1;j<=vnum&&prime[j]*i<=siz;j++)
              {
                  vis[prime[j]*i]=1;
                  if(!(i%prime[j]))
                  {
                      phi[prime[j]*i]=phi[i]*prime[j];
                      break;
                  }
                  else phi[prime[j]*i]=phi[i]*phi[prime[j]];
              }
          }
          for(int i=1;i<=siz;i++)
              (sum[i]=sum[i-1]+phi[i])%=P;
      }