竞赛讨论区 > 【题解】wannafly挑战赛11
头像
牛客网小运营
编辑于 2018-12-27 14:46
+ 关注

【题解】wannafly挑战赛11

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)
T1 白兔的分身术
显然取p=n,k=1最优

T2 白兔的式子
可以发现f[n][m]=a^{n-m}b^{m-1}C(n-1,m-1)。

T3 白兔的棋盘
状压DP,f[i][j][s]表示从(1,1)DP到了(i,j),轮廓线上每个格子是否是空格的状态为s的方案数。放一个xy的矩形时直接转移到f[i][j+y]。

T4 白兔的字符串
枚举T的所有表示法存入哈希表
然后每个S直接查询
长度有10^6级别,所以哈希的姿势要足够优秀,必然很容易冲突
标算是ex_kmp。用R[i]表示S[i..len]和T的最长公共前缀,L[i]表示S[1..i]和T的最长公共后缀,当L[i]+R[i+1]>=|T|时,可以给一段区间打上标记。如果T的一个表示法在某个位置出现则至少会被一个标记覆盖。然后就变成了区间加法,求有多少个正数。用差分+前缀和即可。

T5 白兔的刁难
题目要求的实际上就是,对于任意t,把展开后,x的指数模k为t的所有项的系数之和。那么我们可以利用,带入。那么x的指数模相同的项就会自动合并。
把进行长度为k的DFT,然后每个数求n次幂,再IDFT回来就是答案。
复杂度klogmin(n,998244352)+klogk。既然是求n次幂,那么n可以直接对998244352取模,那个10^{10^6}是吓唬人的。

T6 白兔的游戏
先来求获胜概率,可以发现,如果每堆石子都只有1个,那么获胜概率不是0就是1;否则,获胜概率就是1/2。
如果先手获胜,那么说明游戏是奇数回合结束的,就是说只需要关心结束时的回合数。
一个大小为m的堆,i次操作完的方案数是C(m-1,i-1)。
直接dp,f[i][j]表示前i堆j次操作完的方案数,f[i][j]+=f[i-1][j-k]C(a[i]-1,k-1)*C(j,k) (1<=k<=a[i])。
分治NTT优化。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐