https://atcoder.jp/contests/abc301/tasks
三维空间 n个人, 整点坐标(xi > 0,yi,zi), 两两坐标不同
需要选点p(x<0,y,z) , 在 x正向拍照
p,A,B共线，则后面的人不被拍到
想办法找点p 让被拍到的人的人尽量小， 求最小被拍到的人
n 50
x [1,1000]
y,z [-1000,1000]
4s
1024mb
二维空间几何都还不熟，这里来个3维的
但为什么看起来 逻辑很简单，只是实现不知道
既然N 只有50, 那么就是 暴力选4个点， 这样两条线找交点
这样再去枚举交点
一个特殊情况是有一条线上 有很多点，那么这条线上任意一个位置都可以
那么问题来了，如何找三维空间中的交点
感觉就是先抛弃 第3维，直接计算(x,y)的交点, 再验证z?
似乎卡着时间过了, 一次TLE一个点，一次AC
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