Atcoder abc340
https://atcoder.jp/contests/abc340
G - Leaf Color
n点树,点有颜色,问又多少个 导出子图的“端点”都是同色 mod 998244353
n 2e5
2s
1024mb
我的思路
每个颜色单独考虑
那实际上是选择同色的点,要让任何三点不共线,没想到怎么统计
https://atcoder.jp/contests/abc340
n点树,点有颜色,问又多少个 导出子图的“端点”都是同色 mod 998244353
n 2e5
2s
1024mb
每个颜色单独考虑
那实际上是选择同色的点,要让任何三点不共线,没想到怎么统计
https://codeforces.com/contest/1930
a[i]=i
for k = 1..(n-1)/2:
输出 原序列 任意次操作(>=0) 后能得到的不同的序列的方案数 mod 998244353
每次操作选择2k+1个数(不需要连续),删掉被选中的里的左边k个和右边k个
n 1e6
2e3组测试
容易想到 操作w次,那么就要删除2kw个
而 w \in [0,n/k]
所以sum(w) = O(n log n)
所以如果对于给定的(k,w)能够 常数时间或均摊常数时间求出来就好了
先不考虑时间限制
考虑被删除的 [k-1]个随便选
,中间的[2kw-(2k-1)]个不能全部连续
,[k-1]个随便选
必要性: 显然每个实际方案最后一次删除一定保证了最左k和最右侧k之间有未被删除的
充分性: 倒着恢复,如果满足,则可以让最后一次删除的一侧恢复到所有删除中的中间部分,归纳得证
这样就是容斥了 binom(n,2kw)
- 固定中间连续的方案
for 连续的一坨的 起点是i
$\sum_{i=k}^{n-(2kw-(k-1))+1} \binom{i-1}{k-1}\binom{n-(i+(2kw-(2k-1))-1)}{k-1}$
令$a=k-1$ 会发现是$\sum \binom{a+t}{a}\binom{b-t}{a}$
的形式
$=[x^{n-2kw}] (\sum_{i=0}^{\infty} \binom{a+i}{i}x^i)^2$
或者
$=\frac{1}{(a!)^2}[x^{n-2kw}] (\sum_{i=0}^{\infty} \frac{(a+i)!}{i!}x^i)^2$
然后这个的话, 对于给定的a也就是给定的k来说
可以一次性计算,这样子不同的w只需要取值一下就好了
但 如果 for k {ntt, for w}
的话, ntt的部分的总代价还是 (n^2logn)
不知道 这样能变成 什么函数 从而快速求得系数
https://atcoder.jp/contests/abc339
n个数字a[n]
, 问有多少个有序对(i,j,k)满足
A[i]*A[j]=A[k]
n 1000
$a[i] \in [0,10^{10}]$
2s
1024mb
光是 枚举 (i,j) 那么也是 n^2了,那么乘法和对比就要足够快, 然而最快的就算ntt,也是 (长度 log(长度)) 会tle
一个想法 是 通过减少比较范围,但如果正好 一半长度 [len/2]
一半长度[len]
第二个想法是 选取一些 质数p,然后通过类似hash的想法来完成
a[i] * a[j] == a[k]
那么 (a[i] % p)*(a[j] % p) % p== a[k] %p
没有任何确定性算法
然后就是 十进制压8位,但这样也只是降低到 int[125] x int[125]
n的个数没有减少
https://atcoder.jp/contests/abc338
给定字符串S,由123456789+*
组成
最开始和最后的字符是数字,没有相邻的非数字
对于$(i\le j)$, 如果s[i],s[j]都是数字,则eval(i,j)为这一段字符串的表达式结果
否则 为0
求 $\displaystyle \sum_{i=1}^{|S|}\sum_{i=j}^{|S|} eval(i,j)\mod 998244353$
$|S| \le 10^6$
2s
1024mb
这里虽然没有括号,但是有乘法的优先运算
如果固定前面
1 | 1234123*234*345+3245*145+324*45*345 |
那我们得到的是 [base + prodbase * (cur=34)]
每次遇到数字就是cur*=10,cur+=int(s[i])
而进入新的乘法则是prodbase*=cur, cur = 0
而进入新的加法则是base+=prodbase*cur
,prodbase=1,cur=0
这个方法的问题在于 如果想用矩阵表示,那么在做prodbase * cur
的时候 无法做这个乘法
再增加prodres
东西
1 | 1234123*234*345+3245*145+324*45*345 |
ans = base + prodres
prodres = prodbase * cur
, 而新的转移 发现cur不需要了
那么 遇到数字时,
1 | sumall base prodres prodbase 1 |
那么 遇到+时,
1 | sumall base prodres prodbase 1 |
那么 遇到*
时,
1 | sumall base prodres prodbase 1 |
所以,后缀矩阵乘法就秒了
前置的是[0,0,0,1,1]