树上路径（phantasm）
题目背景
Akari是一个普通的初中生。
题目描述
Akari的学校的校门前生长着一排n棵树，从西向东依次编号为1∼n。相邻两棵树间的距离都是1。Akari上课的教学楼恰好在树1旁，所以每个课间，Akari都很想走出教室，上树活动。Akari会依次经过m棵树，从树1一路向东跳到树n。临近上课时，Akari会再次上树，经过m棵树从树n一路向西跳到树1，准备上课。由于Akari睡眠很充足，Akari每次跳跃至少会移动k的距离，因此Akari在上树前需要合理规划她的跳跃路线。我们称每次上树过程中Akari跳过的全部m棵树（包含树1和树n）的集合为一条树上路径。Akari喜欢按不同的顺序观察各种树木，因此她每次上树时选择的树上路径不会与之前选择过的重复。这意味着，Akari不会选择之前的课间选过的树上路径，且在从树n跳回树1时，也不会沿这次跳到树n的树上路径原路返回。如果一次课间开始时，Akari找不到符合条件的树上路径，那么她从此会放弃上树活动，开始专心学习。如果一次课间即将即将结束时，Akari还在树n且找不到符合条件的树上路径回到树1，她就会十分沮丧，选择逃课。请你帮助Akari判断，她是否会在某个课间选择逃课。
输入格式
从文件phantasm.in中读入数据。每个测试点可能包含多组数据。第一行一个正整数T，表示数据组数。每组数据包括一行三个正整数n,m,k，含义见题目描述。
输出格式
输出到文件phantasm.out中。对于每组数据，输出一行一个字符串。如果Akari会逃课，输出Yes，否则输出No。
请.注.意.输.出.字.符.串.的.大.小.写
样例1输入
3
10 3 2
5 3 11
5 5 3
样例1输出
No
Yes
No
样例1解释
第一组数据中，除了起点和终点外，合法的树上路径只能经过3,4,5,6,7,8这6棵树，所以合法的树上路径只有6种，经过3个课间后Akari就会停止上树活动。第二组数据中，合法的树上路径有3种，Akari会在第2个课间结束时逃课。第三组数据中，合法的树上路径有10种。
样例2输入
4
15 4 3
15 4 4
15 5 3
16 3 7
样例2输出
Yes
No
No
No
分析
先转化一下题意。将n个球拆分成m组，每组要求大于k个，求方案数奇偶性。
所以可以先直接先给每个组k个，剩下n-m*k个随便分组，这里一个组内可以不分，所以方案数就是C(n-k*m+m-1,m-1)。
如何判断它奇偶性呢？
对于一个组合数，它可以用阶乘的乘除表示出来，所以问题转化成一个数的阶乘中2的个数。
对于一个数x，x/2表示从1到x的数中为2倍数的个数，再除二表示为4倍数的个数。。。。。。
所以x/2+x/4+x/8......加到为0为止就好了，有点类似于叠加。
代码
#include<cstdio>
int T,n,m,k;
int cal(int x)
{int ans=0;while(x)ans+=x/2,x/=2;return ans;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&n,&m,&k);n--;m--;int a=n-k*m+m-1,b=m-1;if(cal(a)>cal(b)+cal(a-b))puts("No");else puts("Yes");}
} 泳池（skylines）
题目背景
小A是个爱玩的女孩子。暑假终于到了，小A决定请她的朋友们来游泳，她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险，有些地方水太深，有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。
题目描述
小A的城市里有n座工厂，编号分别为1∼n。工厂间连有n−1条.双.向管道，形成一个无向连通图，其中每条管道都有一定的长度，连接在两座不同的工厂间。每座工厂都装有废水处理设施，工厂i的蓄水量记为ci。由于工厂规模有限，工厂产生的废水必须经由管道输送到.另一座工厂进行处理。工厂u将废水输送到工厂v处理时，所需的运输成本等于无向图中u,v间最短路径的长度，并且会产生cu−cv的额外成本（可能为负）。总成本等于运输成本与额外成本的和。为了降低污染，在接下来的q天内，每一天只有一座工厂会产生废水。你需要确定这座工厂将废水输送到哪一座工厂进行处理，可使得总成本最小。由于选择可能不唯一，你只需输出最小的总成本。
输入格式
从文件skylines.in中读入数据。第一行一个正整数n。第二行n个正整数ci。下接n−1行，每行三个正整数u,v,w，表示一条双向管道两端工厂的编号及长度。第n+2行一个正整数q。下接q行，每行一个正整数x，表示这一天进行生产的工厂的编号。
输出格式
输出到文件skylines.out中。输出q行，每行一个整数，表示这一天总成本的最小值。
样例1输入
5
7 7 6 9 9
2 5 5
2 3 1
4 1 1
1 2 2
4
2
5
3
4
样例1输出
1
7
0
3
样例1解释
第1天，工厂2输送到工厂4是一种最优方案，成本为3+(−2)=1。第2天，工厂5输送到工厂2是一种最优方案，成本为5+2=7。第3天，工厂3输送到工厂2是一种最优方案，成本为1+(−1)=0。第4天，工厂4输送到工厂1是一种最优方案，成本为1+2=3。
分析
对于将从u运输到v，则代价为c[u]-c[v]+dep[u]+dep[v]-2*dep[lca(u,v)]。
c[u]+dep[u]是固定的，所以我们要去求dep[v]-c[v]-2*dep[lca(u,v)]的最小值。
当v在u的子树中时,lca(u,v)=u，-2*dep[lca(u,v)]是固定的，我们只需要知道u子树最小的dep[v]-c[v]即可
当v不在u的子树中时，显然我们要去枚举lca(u,v)。
每个节点，我们考虑如何求dep[v]-c[v]-2*dep[lca(u,v)]的最小值
设s[u]表示dep[v]-c[v]-2*dep[lca(u,v)]的最小值,其中v不在u的子树内。
那么s[fa[u]]就表示不在fa[u]子树内的v的dep[v]-c[v]-2*dep[lca(u,v)]的最小值
那么就还有在fa[u]子树内却不在u子树内的节点没有被考虑到。
显然这些点与u的lca都是fa[u]，所以有时求fa[u]子树中dep[v]-c[v]的最小值，这个已经维护过了。
但是，之前维护的时候并没有保证点v不在u子树内。
还需要维护另一个dep[v]-c[v]的最小值，且v不在u子树内。
所以对于每个节点u，维护两个dep[v]-c[v]的最小值，且这两个取最小值的点不在同一个子树内
用s[fa[u]]更新s[u]时，先看fa[u]子树的dep[v]-c[v]的最小值的点是否在u子树内，
如果不是，则用s[fa[u]]和dep[v]-c[v]的最小值去更新s[u]，
反之，则用s[fa[u]]和另一个dep[v]-c[v]的最小值去更新s[u]。
另外，还有fa[u]也要去更新一下s[u]。
最后直接预处理就好了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int Q,d[maxn],son[maxn],ans[maxn];
int n,cnt,c[maxn],v[maxn<<1],w[maxn<<1],nx[maxn<<1],info[maxn],s[maxn][5];
void add(int u1,int v1,int w1){nx[++cnt]=info[u1];info[u1]=cnt;v[cnt]=v1;w[cnt]=w1;}
void dfs1(int x,int f)
{for(int i=info[x];i;i=nx[i])if(v[i]!=f){d[v[i]]=d[x]+w[i];dfs1(v[i],x);int tmp=min(d[v[i]]-c[v[i]],s[v[i]][0]);if(tmp<=s[x][0])s[x][1]=s[x][0],s[x][0]=tmp,son[x]=v[i];else if(tmp<=s[x][1])s[x][1]=tmp;}
}
void dfs2(int x,int f)
{for(int i=info[x];i;i=nx[i])if(v[i]!=f){if(v[i]==son[x])s[v[i]][2]=min(s[x][1]-2*d[x],min(s[x][2],-c[x]-d[x]));else s[v[i]][2]=min(s[x][0]-2*d[x],min(s[x][2],-c[x]-d[x]));dfs2(v[i],x);}
}
int main()
{scanf("%d",&n);memset(s,0x3f,sizeof s);for(int i=1;i<=n;i++)scanf("%d",&c[i]);for(int i=1,u1,v1,w1;i<n;i++)scanf("%d%d%d",&u1,&v1,&w1),add(u1,v1,w1),add(v1,u1,w1);dfs1(1,0);dfs2(1,0);scanf("%d",&Q);for(int i=1;i<=n;i++)ans[i]=d[i]+c[i]+min(s[i][0]-2*d[i],s[i][2]);for(int i=1,u;i<=Q;i++)scanf("%d",&u),printf("%d\n",ans[u]);
} 空之轨迹（kiseki）
冷鸟的《星之所在》是真的好听
题目背景
七曜历1150年前后，爱普斯泰恩博士发明了导力器，由此，一场席卷塞姆利亚大陆的能源革命——导力革命开始了，它使得大陆进入了空前的发展阶段。另一方面，很多国家为了开发拥有导力力量的兵器而展开激烈的争夺，拥有霸权成为很多国家的意图。在这个错综复杂的时代里，大陆陷入了混乱之中。这个时代，有一个生存于列强罅缝中的独立小国——利贝尔。以利贝尔为舞台的起点，主人公艾丝蒂尔和约修亚将在冒险旅途上遇到各色各样的人物，以成为正式游击士为目标的她，揭开了故事的序幕。以新的世界、新的角色来描述新的故事，这就是开拓时代的物语——空之轨迹。
题目描述
Iri近日沉迷游戏《英雄传说VI空之轨迹》。该游戏共有n个章节，第i章中有ai次战斗。当第i章通关后，游戏会自动存档，然后自动进入第i+1章，且不允许回到之前的章节（除非读档）。由于Iri的游戏设备年久失修，这天早上Iri进入游戏时，发现他的所有存档都消失了，只留下初始的一个序章存档（加载后会开始第1章）。不幸的是，游戏的章节切换系统也出现了Bug，在每一章结束的自动存档之后，游戏会从已有的所有存档（包括序章存档）中等概率随机选取一个加载。由于Iri的耐心与精力有限，加载序章存档后，他只会连续玩m个章节，然后更换新的设备。需要注意的是，游戏的存档系统没有损坏，即当第i章结束后的自动存档被加载后，一定会开始第i+1章。现在Iri想知道，这m章内能进行的战斗总次数的期望值。Iri觉得这个问题太简单了，所以就把它交给了你。由于Iri的游戏技术同样出神入化，你可以认为所有章节他都会一次通关。
输入格式
从文件kiseki.in中读入数据。第一行包含两个正整数n,m.第二行n个非负整数ai.
输出格式
输出到文件kiseki.out中。输出一行一个整数，表示Iri进行的战斗总次数的期望值在模998244353意义下的值。即设答案化为最简分式后的形式为ab，其中a和b互质，输出整数x使得bx≡a(mod 998244353)且0≤x<998244353。可以证明这样的整数x是唯一的。
样例1输入
3 2
1 2 1
样例1输出
499122179
样例1解释
答案是52。由于499122179×2 mod 998244353=5，所以你输出499122179。
样例2输入
3 3
5 5 1
样例2输出
332748132
样例3输入
15 10
2 8 6 3 2 6 3 5 9 2 3 4 5 1 6
样例3输出
653958763
分析
首先题目没表示，一个章节可以由多个存档。
看题目应该是个期望dp。
一开始想的是dp[i][j][k]，表示第i次，当前最高关卡数为j，这次抽到k的概率
然后发现中间那一维其实可以省去，因为根据dp本身的性质，超过最高关卡数的根本不会被更新，概率为零，不需要多一维来限制。
直接dp[i][j]表示第i次抽到关卡j的概率。
显然我们需要知道前i-1次抽到j-1关卡的期望次数，dp[i][j]=前i-1次抽到j-1关卡的期望次数/(i-1)（然后考场上我想再推一个函数，推了一个下午）
然后，猛然发现 前i-1次抽到j-1关卡的期望次数=dp[1~(i-1)][j-1]*1(原谅我不会用数学公式)
一边dp一边针对每个关卡算一下贡献就好了
说是可以前缀和优化？但我懒得写了
代码
#include<cstdio>
const int mod=998244353;
int n,m,ans,inv[30],a[100005],dp[25][25];
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);dp[1][0]=1;inv[1]=1;for(int i=2;i<=25;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;for(int i=2;i<=m+1;i++)for(int j=1;j<=m;j++){for(int k=1;k<i;k++)dp[i][j]=(dp[i][j]+1ll*dp[k][j-1]*inv[i-1])%mod;ans=(ans+1ll*dp[i][j]*a[j])%mod;}printf("%d\n",ans);
}
