ARC061 简要题解
A
直接暴力乱搞
或者算一个子串对答案的贡献也行
B
把每个点在矩形中的位置讨论一下, 把重复的情况去掉
一个都没有的就是总的减其他
C
并查集把联通的一块判完之后
建一个新图在上面跑最短路即可
新图就是把每一个点拆开, 分为入点和出点, 入点向出点连一条 1 的边, 联通块向入点连一条 0 的边, 出点向联通块连一条 0 的边
D
发现每一种让 a 胜利的方案都对应着一段仅由 A, B, C 组成的字符串, 第 (i) 个字符代表第 (i) 个回合打出的牌上写的字符
手玩之后发现最后一个字符必然是 A , 且字符串中 A 有 (n) 个, B 有 (< m) 个, C 有 $< k $ 个
不妨设该字符串中 B 有 (x) 个, C 有 (y) 个, 那么字符串中的字符总数就是 (n + x + y)
对应的字符串就会有
[inom{n+x+y-1}{n-1}inom{x+y}{x}3^{m+k-x-y}
]
个, 代表最后一位必须选 A , 其他的随便排, 然后 B 剩下的 (m - x) 张牌和 C 剩下的 (k - y) 张牌随便怎么选
不妨设 (x + y = t)
则有
[egin{aligned}
ans &= sum_{t=0}^{m+k}inom{n+t-1}{n-1}3^{m+k-t}sum_{x=t-k}^{m}inom{t}{x}
end{aligned}
]
设 (f[t] = sum_{x=t-k}^{m}inom{t}{x}), 则有
[egin{aligned}
f[t]&=sum_{x=t-k}^{m}inom{t}{x}
\&=sum_{x=t-k}^{m}inom{t-1}{x}+inom{t-1}{x-1}\
&=sum_{x=t-k}^{m}inom{t-1}{x}+sum_{y=(t-1-k)}^{m-1}inom{t-1}{y}\\
&=(sum_{x=(t-1)-k}^minom{t-1}{x}-inom{t-1}{t-1-k})+(sum_{y=(t-1-k)}^{m}inom{t-1}{y}-inom{t-1}{m})\
&=2f[t-1]-inom{t-1}{t-1-k}-inom{t-1}{m}
end{aligned}
]
递推之后求解即可