题解

ZOM (zom)

考察点：倍增求 lca。

首先注意到，我们的求LCA可以用倍增维护。

总所周知，我们删除一个叶子节点的倍增信息是容易的，而倍增又是可以动态加入的（考虑倍增向上跳的过程）。

因此，我们叶子节点的倍增信息是可以直接更新的。

然后就做完了，复杂度 $O(n \log n)$。

为什么倍增可以动态加入呢，因为每次加入他的时候祖先的倍增信息都是完好的，因此可以直接维护。

骰子 (dice)

$n \leq 8$

暴力枚举每个骰子选或不选即可。

$n \leq 50$

我们考虑一个 dp。

我们设 $f_{i,j,k}$ 表示前 $i$ 个骰子选了 $j$ 个且和为 $k$ 的方案数。

转移只要枚举这一个骰子是啥就好了。

复杂度 $O(n^4)$。

$n \leq 200$

不难注意到转移的是一段区间，我们使用前缀和优化 dp 即可做到 $O(n^3)$ ，利用滚动数组优化空间即可通过。

忍俊不禁 (laugh)

考察点：乘法逆元，组合数，高斯消元，简单推式子。

sub1

这个部分保证 $m=0$。

也就是说 $a_n=qa_{n-1}+p$。

对于这种题我们有一个套路，把两边都加上一个数，使得柿子化为这个形式：$a_n+t=q(a_{n-1}+t)$。

从而得出 $a_{n}+t$ 是一个等比数列，就很方便的得出通项为 $(a_1+t)q^{n-1}-t$，题目中则需要输出带 $q^n$ 的，把系数除 $q$ 即可。

不难注意到 $t$ 满足 $p+t=qt$，直接解方程即可。

sub2

方法和 sub1 类似，设两边加上的是 $kx+b$ 即可。

sub3

$x_i$ 直接这里写作 $a_i$。

首先我们设 $F\left(n\right)=\sum_{i=0}^{m}a_in^i$。

假设两边加上的多项式是 $G\left(n\right)=\sum_{i=0}^{m}b_in^i$。

那么我们有 $F(n)+G(n)=qG(n-1)$。

我们对于 $G(n-1)$ 利用二项式定理进行展开： $$ G(n-1)=\sum_{j=0}^{m}n^j\sum_{i=j}^{m}(-1)^{i-j}\binom{i}{j}b_i $$ 进行系数对比： $$ q(\sum_{i=j}^{m}(-1)^{i-j}\binom{i}{j}b_i)-b_j=a_j $$ 不难注意到这是一个关于 $b$ 的 $m+1$ 元方程组，利用模意义高斯消元进行求解即可。

答案即为 $\frac{a_1+G(1)}{q} \times q^n-G(n)$。

代码：

#include<bits/stdc++.h>
using namespace std;
namespace gza{
    #define int long long
    #define pb push_back
    #define MT int TTT=R;while(TTT--)
    #define pc putchar
    #define R read()
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    #define rep(i,a,b) for(int i=a;i>=b;i--)
    #define m1(a,b) memset(a,b,sizeof a)
    namespace IO
    {
        inline int read()
        {
            int x=0;
            char ch=getchar();
            bool f=0;
            while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            if(f) x=-x;
            return x;    
        }
        template<typename T> inline void write(T x)
        {
            if(x<0) pc('-'),x=-x;
            if(x>9) write(x/10);
            pc(x%10+'0');
        }
    };
    namespace math
    {
        inline int gcd(int a,int b)
        {
            int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
            b>>=bz;
            while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
            return b<<z;
        }
        inline int qmi(int a,int b,int p)
        {
            int res=1;
            while(b)
            {
                if(b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
            }
            return res;
        }
        const int MAXN=2e6+10;
        int my_fac[MAXN],my_inv[MAXN];
        void init_binom(int mod)
        {
            my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
            my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
        }
        int binom(int a,int b,int mod)
        {
            return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
        }
    };
    using namespace IO;
    using namespace math;

    const int N=310,mod=998244353;
    int m,a1,q;
    int a[N],b[N];
    int d[N][N];
    void main(){
        freopen("laugh.in","r",stdin);
        freopen("laugh.out","w",stdout);
        init_binom(mod);
        m=R,a1=R,q=R;
        fo(i,0,m) a[i]=R;
        fo(j,0,m)
        {
            fo(i,j,m) d[j+1][i+1]=q*(((i-j)%2!=0)?mod-binom(i,j,mod):binom(i,j,mod))%mod;
            (d[j+1][j+1]+=mod-1)%=mod;
            d[j+1][m+2]=a[j];
        }
        int n=m+1;
        fo(i,1,n)
        {
            if(!d[i][i])
            {
                int maxi=0;
                for(int j=i+1;j<=n&&!maxi;j++) if(d[j][i]) maxi=j;
                if(!maxi) continue;
                fo(j,i,n+1) swap(d[i][j],d[maxi][j]);
            }
            fo(j,i+1,n)
            {
                int tmp=d[j][i];    
                if(tmp)
                {
                    fo(k,i,n+1)
                        d[j][k]=(d[j][k]*d[i][i]%mod-d[i][k]*tmp%mod+mod)%mod;
                }
            }
        }
        rep(i,n,1)
        {
            fo(j,i+1,n) d[i][n+1]=(d[i][n+1]-b[j]*d[i][j]%mod+mod)%mod;
            b[i]=d[i][n+1]*qmi(d[i][i],mod-2,mod)%mod;
        }
        int sum=0;
        fo(i,1,n) (sum+=b[i])%=mod;
        write((a1+sum)%mod*qmi(q,mod-2,mod)%mod),puts("");
        fo(i,1,n) write((mod-b[i])%mod),pc(' ');
    }
}
signed main(){

    gza::main();
}

追逐极光者 (aurora)

考察点：DP。

Sub1 & Sub2

暴力。

$2^m$ 枚举链的选择情况，$poly(n)$ 时间 check 即可。时间复杂度 $O(2^mpoly(n))$

Sub4

等价于选最大价值不交区间，我们将区间挂在右端点上。

令 $f_i$ 表示前 $i$ 个点最大价值，$f_i = \max_j f_{l_j - 1} + w_j$

选择喜欢的 DS 优化即可。

Sub3

这一档是留给做出了奇怪 $O(n^2m)$ 做法，或常数巨大的选手或者在一些细节上实现或维护不精导致复杂度错误的选手的。

Sub5

由链的情况启发，我们考虑将路径挂在 Lca 处。

令：$f_x$ 表示以 $x$ 为根的子树的答案，考虑 $Lca$ 为 $x$ 的路径，令 $S$ 表示红线下挂着的所有儿子组成的集合，有 $f_x = \sum_{y\in S}{f_y}$

由于是二叉树，对于跨过子树的链，我们暴力统计答案即可，对于单子树的链，我们记录一下 $L_f$ 与 $R_f$ 最后合并到 $f$ 上就好了。

Sub6

对于多叉树，麻烦的事情是一个 Lca 处会有多条链被选，而被选一条链就会改变一辆棵子树的贡献。

我们考虑在状态里多记一些东西：设 $f_{x,S}$ 表示以 $x$ 为根的子树且不考虑集合 $S$ 中儿子子树贡献的答案。

首先不考虑 Lca 处的链，用 $f_{Son,0}$ 处理出所有 $f_{x,S}$

然后拿链来做更新，我们实际上就是在做一个状态压缩的背包。

我们记 $Id_x$ 表示 $x$ 他父亲中 $x$ 的儿子编号，则有 $f_{x, S\or u\or v} = f_{u,0} + f_{v,0} + \sum_{y\in S} f_{fa_y,Id_y}$

然后暴力做背包·就行。

提高级

提交源程序文件名

编译选项

注意事项（请仔细阅读）

• 文件名（程序名和输入输出文件名）必须使用英文小写。
• C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
• 若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。
• 程序可使用的栈空间内存限制与题目的内存限制一致。
• 只提供Linux格式附加样例文件。

ZOM (zom)

题目背景

居住在 ZOM 国度的小 S 已经完成了种树的基本目标，现在他要对他的树进行一些修改。

题目描述

​ 给定一棵 $n$ 个点的树和 $q$ 次操作，$1$ 为树的根，分为两种：

1. 给定 $u,v$，将 $u$ 的父亲修改为 $v$，保证 $u$ 是叶子结点。
2. 给定 $u,v$，查询 $u$ 和 $v$ 的最近公共祖先。

输入格式

第一行输入两个正整数 $n,q$。

第 $2\sim n$ 行，每行输入两个正整数 $u,v$，表示一条树边。

第 $n+1\sim n+q$ 行，每行三个正整数 $op,u,v$。其中 $op$ 表示操作种类，$u,v$ 含义如题面所述。

输出格式

对于每一个查询操作，输出一行一个整数，表示你的答案。

样例 #1

样例输入 #1

3 3
1 2
1 3
2 2 3
1 3 2 
2 2 3

样例输出 #1

1
2

提示

对于 $30\%$ 的数据，保证 $1\leq n,q\leq 1000$

对于 $60\%$ 的数据，保证 $1\leq n,q\leq 2\times 10^5$

对于另外 $10\%$ 的数据，保证不存在操作 $1$。

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^6$，所有输入均合法。

骰子 (dice)

题目描述

小 C 喜欢骰子，尽管这些骰子非常奇怪。

小 C 的手中有 $n$ 个不同的骰子，其中第 $i$ 个骰子是 $a_i$ 面骰子，每个面上的数字依次为 $1,2,3,\cdots,a_i$。

现在，小 C 要选择其中的 $k$ 个骰子，并对于这 $k$ 个骰子中的每一个骰子，选择一个面朝上。

小 C 想要知道，共有多少种不同的选择骰子和选择朝上的面的方案，可以使所有选择的骰子的朝上的面上的数字之和不大于 $p$。

两种选择骰子和选择朝上的面的方案不同，当且仅当存在一个只在其中一种选择方案中出现的骰子或存在一个同时出现在这两种选择方案的骰子的朝上的面上的数字不同。

由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行三个整数 $n,k,p$。

第二行 $n$ 个整数，表示数组 $a$。

输出格式

一行一个整数，表示满足条件的不同的选择骰子和选择朝上的面的方案数对 $998244353$ 取模的结果。

样例 #1

样例输入 #1

3 2 5
3 4 6

样例输出 #1

28

样例 #2

样例输入 #2

4 4 13
6 4 5 3

样例输出 #2

296

提示

【样例 #3】

见附加文件中的 dice/dice3.in 与 dice/dice3.ans。

该样例满足测试点 $8$ 的限制。

【样例 #4】

见附加文件中的 dice/dice4.in 与 dice/dice4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 dice/dice5.in 与 dice/dice5.ans。

该样例满足测试点 $13$ 的限制。

【样例 #6】

见附加文件中的 dice/dice6.in 与 dice/dice6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$1 \le k \le n \le 200$，$1 \le p \le 1000$，$1 \le a_i \le 10^9$。

特殊性质：保证 $k=n$。

忍俊不禁 (laugh)

题目背景

忍俊不禁题。会做之后，你会笑出声来。

题目描述

给定 $A_1$，求一个序列 $A$ 的通项。

序列 $A$ 满足 $A_n=qA_{n-1}+\sum_{i=0}^{m}n^ix_i$。

其中 $q$ 和序列 $x$ 都是给定的。

如果输出 $A$ 的通项见输出格式。

输入格式

第一行三个整数 $m,A_1,q$，含义见题面。

第二行 $m+1$ 个整数，用空格隔开，第 $i$ 个整数代表 $x_{i-1}$。

输出格式

我们保证 $A$ 的通项为 $A_n=t \times q^n+\sum_{i=0}^{m}y_in^i$ 的格式。且所有输出的数字都保证为有理数，要求输出的结果对于 $998244353$ 取模。

第一行输出一个正整数 $t$，含义见上段。

第二行输出 $m+1$ 个正整数，用空格隔开，第 $i$ 个数代表 $y_{i-1}$。

样例 #1

样例输入 #1

0 3 3
0

样例输出 #1

1
0

样例输入 #2

见下发文件中的 ex_laugh1.in。

样例输出 #2

见下发文件中的 ex_laugh1.ans。

提示

对于 $10\%$ 的数据，保证 $m=0$。

对于 $30\%$ 的数据，保证 $m \leq 1$。

对于 $100\%$ 的数据，保证 $1 \leq m \leq 300$，$0 \leq a_1,x_i(0 \leq i \leq m)<998244353$，$2 \leq q <998244353$。

数据有一定的梯度。

追逐极光者 (aurora)

题目背景

$\text「这人真有意思，明明就在极光城里，却在寻找极光城。」$

$\color{red} \text「不……他从未抵达极光城……」$

从此以后，极光城里多了个找极光城的疯子。

题目描述

极光城形如一颗 $n$ 个点的树，每个点最多只连接了 $10$ 条双向的街道。

$\color{red} \text「你在找什么？」$

$\text「我在找极光城。」$

$\color{red} \text「这里就是极光城。」$

$\text「我快找到了……我一定能找到的！」$

同时，有 $m$ 种风筝在极光城上空飘荡，在 $u_i$ 到 $v_i$ 间飘荡着 $w_i$ 只第 $i$ 种风筝。

Donald 想要顺着风筝找极光城，他可以在极光城每条街道停留并追寻风筝，且 Donald 在每条街道只能追寻其中一种风筝，如果他完整的经过了第 $i$ 种风筝飘荡的路线，则他可以获得这 $w_i$ 只风筝。

Donald 希望获得最多的风筝，他认为这样就能找到极光城了，请 $\color{red} \text「你」$ 告诉他最多能获得多少风筝。

$\text「极光城有风筝……我也有风筝……顺着风筝……我一定能去极光城！」$

$\text「我就快找到极光城了……」$

$\text「我就快找到了！」$

形式化题意

给定一颗 $n$ 个点的树，树上每个点最大度数为 $10$，以及树上 $m$ 条路径，路径有权值 $w$，你需要选出若干路径使得选出的路径边无交，问最大价值。

$n,m\leq 1000,w_i\leq 10^9$

输入格式

第一行两个整数 $n, m$，表示点数以及路径数。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示 $u,v$ 之间有条双向边。

接下来 $m$ 行，每行三个整数 $u,v,w$ 表示 $u,v$ 为路径的两个端点，$w$ 为这条路径的权值。

输出格式

输出一行一个整数，表示最大价值。

输入输出样例

样例#1

样例输入#1

7 3
1 2
1 3
2 4
2 5
3 6
5 7
1 6 1
1 4 3
4 7 1

样例输出#1

4

样例 #2

样例输入 #2

见下发文件中的 ex_aurora1.in。

样例输出 #2

见下发文件中的 ex_aurora1.ans。

样例 #3

样例输入 #3

见下发文件中的 ex_aurora2.in。

样例输出 #3

见下发文件中的 ex_aurora2.ans。

提示

对于所有数据满足 $n,m\leq 1000,w\leq 10^9$