https://atcoder.jp/contests/abc299/tasks
6面骰子(1…6), 正整数R
每次投骰子, X=历史所有骰子的和, 如果 X-R是 1e9的倍数, 操作退出
求 退出时, Exp(次数C), mod 998244353
R [1,1e9)
2s
1024mb
p(t,k)= t次 和=1e9 k + R, 且 < k的时刻没有达到等于
$\displaystyle ans = \sum_{t=1}^{\infty} \sum_{k\in [\frac{t-R}{10^9},\frac{6t-R}{10^9}]} p(t,k)t$
或者能否 p[s] = 和达到s的概率
这样看起来似乎可以矩阵转移，快速幂 合并？
https://atcoder.jp/contests/abc298/tasks
H行W列
有s[i][j]个草莓
每次切割，把一个剩余块横向或纵向切成两块
t次切割后，让 一块最多草莓 - 一块最少草莓 尽量小
h,w [1,6]
s[i,j] [0,10^16]
6s
1024mb
dp[l,r,t,b,t] = set<pair<min,max> >
因为min越大 max可能也会增大，所以min max应该 成对
这样状态数比较大
注意到状态合并
左侧[min,max] =>
若右侧 l >= min, 取 min(max,右侧r)
若左侧 r <= max, 取 max(min,右侧l)
否则 l < min and max < r 则是 [l,r]
但这样也很大
https://atcoder.jp/contests/abc297/tasks
正整数序列，和为N, 没有相邻元素相等
求所有满足的序列的长度 的和 mod 998244353
n 2e5
~~2e5 打表啊 ~~
f(m,n) = 长度为m,和=n,满足没有相邻的方案数
ans(n) = sum m f(m,n)
g(m,n,v) = 长度为m, 和=n, 最后一个数为v, 满足没有相邻相同的方案数
f(m,n) = sum g(m,n,1…)
g(1,n,n) = 1
g(1,n,!=n)=0
g(m,n,v) = sum g(m-1,n-v, != v)
注意到转移和m无关, 所以相当于初始矩阵经过 m 次矩阵乘法以后得到的
1 | 初始(1行n^2列) |
然而直接的话，矩阵大小是((n^2)^2) 因为转移每次 都并不是行列对齐
n^2都不行，更别说n^4还要乘法了
而注意到最左和最右的两个行/列矩阵，非零元不超过n
能否靠这个简化
另一些思路，有容斥相邻位置，但是2^{位置}次方吗?
不要等于，换成 f(=n) = f(<=n) - f(<= n-1)
中间想拆成生成函数表示，但是没有拆成功
长度之和 就是每个位置贡献1, 能不能拆
虽然11不能相邻，但是12间隔还是长度能达到 2n/3
https://atcoder.jp/contests/abc296/tasks
N行,M列, 黑/白, 至少一个黑
最小数量 把白色染成黑色, 让所有黑色是一个连通块(4临)
N 100
M 7
2s
1024mb
这M这么小，一股插头dp/横断截面dp的味道
dp[i][横截面状态][已有不连接连通块个数:0/1] = 最小操作数
然后横截面状态, 需要保证横截面以上的内容合法， 然后状态就是最小表示法
但是这样转移太大了, 所以还是插头,
不压缩的情况 也只有$8^7=2097152$ 个状态, 而压缩后应该会很小，因为首先有从小到大性就已经$2\cdot 3\cdot 4 \cdot 5\cdot 6 \cdot 7\cdot 8=40320$, 而且相邻会属于同样的块，所以就更小的了,
O(nm state) 应该就没有了
https://atcoder.jp/contests/abc295/tasks
给长n数组a, $a[i]\in[0,M]$
对于每个$a[i]=0$,等概率修改$a[i]\in[1,M]$
所有修改完后, sort a
问 exp(A[k]) mod 998244353
N 2000
M 2000
4s
1024mb
$ans = \sum_{v=1\to m} v\cdot p(v)$
其中$p(v)$表示 $v$是排序后第$k$小的概率
有$z$个0,其中$z_1$个改为$< v$,$z_2$个改为$=v$,剩下$z-z_1-z_2$个改为$> v$
$p(v) \cdot z^m = \sum_{z_1,z_2} \binom{z}{z_1}\binom{z-z_1}{z_2} (v-1)^{z_1}1^{z_2}(m-v)^{z-z_1-z_2}$, 其中 $z_1 + count(<v) < k$且$z_1+z_2+count(\le v) \ge k$
看上去是$O(m n^2)$的