https://atcoder.jp/contests/abc300/tasks
<= n 的，且所有质因子 <= p的数的个数
n 1e16
p 100
4s
1024mb
dfs(上限, 质数列表idx) = sum dfs(上限/ 质数[idx]^pwr, idx-1)
然后对于底部做cache
然而并不理想，有cache和没cache 1e15都需要 8~12s,
跟别说1e18
另一个角度是，既然题目都告诉了最大的范围的答案大约是2e10, 所以它大也不算大,
所以考虑meet-in-middle
似乎就过了
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) 应该就没有了