10.10

我本来以为打模拟赛有两种苦难

一种是豪挂不止——『愤怒』
一种是完全不会——『绝望』

然后今天发现了被忽视的第三种——『哀伤』

\(A\) 不到一个小时想出来咋写，从思路到细节总之代码的整个流程跟题解都一模一样，但是写不出来。
虽然不知道这个容斥的名字，但是我能清楚的记得刚上初三集训的时候那场提高组模拟赛的那道蚂蚁走网格但是有两条河 C_liar 场切的那道题。
我还记得题解说来回翻递归下去容斥就好了。
但是我忘了怎么写了。
对整个题的记忆非常深刻但是就只有一个点只记了个大概，还挺悲伤的。
好不容易思维想到了，但是算法没跟上也挺难受的。
距离 \(100\) 仅差一个能返回两个直线间合法路径数的函数，然后写了三个半小时豪取弱化版 \(30pts\) 遗憾退场。
赛后发现 \(B\) 纯唐题，\(D\) 不怎么纯的唐题。
所以这种题为什么放 \(A\) 啊。。。
不过体育课真开心！

A.宝石

[ZJOI2008] 生日聚会

于是这道抽象题就诞生了。
\(n,m\le10^7,k\le10^9\)

若一种为 \(+1\) ，一种为 \(-1\) ，则我们需要满足前缀 \(\max\) 与前缀 \(\min\) 的差值 \(\le k\)。
这种东西直接 \(dp\) 很麻烦，所以考虑放到二维平面上。

于是将操作转化为横坐标 \(+1\) 或 纵坐标 \(+1\) ，同时结合上前面的 \(+1/-1\) ，于是我们问题转化为 \((0,0)\) 到 \((n,m)\) 路径经过节点 \(\max\{y-x\}-\min\{y-x\}\le k\) ，容易发现 \(y-x\) 相同的为一条直线，即 \(y=x+b\) 。我们现在知道两条直线的间距 \(k\) ，枚举其中一条直线的间距，另一条直线就确定了，然后要解决不能穿过这两条直线的到 \((n,m)\) 的合法路径数。
这个东西可以用这个式子求。
\(ans=\sum_{k\in \mathbb{Z}}\binom{n+m}{n-k(r-l)}-\binom{n+m}{n-k(r-l)+r}\)
最后有一个问题就是我们有的区间会被算重。
考虑一条很长的线段，同时用一条长为 \(k\) 的线段从左往右移动，同时计算区间内所有子区间的和，那么一个长为 \(l\) 的区间会被统计 \(k-l+1\) 次，但是我们想让每个区间都被统计一次。
所以用长度为 \(k-1\) 的线段再扫一遍即可，这时长度为 \(l\) 的区间被统计了 \(k-l\) 次，用长度为 \(k\) 的线段求出的和减去 \(k-1\) 的就好。
下面是反射容斥的代码：

inline LL W(int mx,int mn)
{
	LL res = 0;int len = mx-mn;
	for (int d = (n+mx)/len;n-d*len <= n+m;d--)
		res = mod(res+mod(C(n+m,n-d*len)-C(n+m,n-d*len+mx)));
	return res;
}

事实证明我没写过一个东西赛时就真的写不出来，这个两行的循环控了我将近 \(3\) 个小时。

B.促销

\(n\le100,k\le10^9\)
唐题，值域很小，矩阵快速幂优化 \(dp\)，复杂度 \(O(n^3\log k)\) 。

D.如何度过双十一

不怎么纯的唐题，对每个区间 \([l,r]\) 增加两维 \(l',r'\) 分别表示移除左边界挡板和右边界挡板之后的活动范围 \((l',r)\) 为 \((l,r')\) 。这个可以扫描线 \(set\) 维护暴力求。两个区间 \((l_1,r_1,l_1',r_1'),(l_2,r_2,l_2',r_2')\) 能同时坐人当且仅当 \(l_2\ge r_1'\) 且 \(l_2'\ge r_1\) ，然后扫一遍同时维护前缀最大值转移即可。