P8558 Darkness

Solution :

一共有3个维度,可以钦点走了多少步x,然后A,B,C三个维度选一些出来使得\sum=x,容易知道这玩意是多项式系数;算的时候是按照走到墙边算的,但是答案要求是走到墙边并且撞到墙上的期望,这就非常妙了:如果仅仅是走到墙边,那对于任意两个墙的交界线和三个墙的墙角(0,0,0)会被重复计数,但是算上撞墙的话重复计数恰好能加上对应的概率,省去了容斥操作,言外之意就是没有重复了~~,orz出题人,太妙了;

Subtask 1

暴力上式子,强制让其中一个维度坐标是0,然后枚举其他两个维度的步数即可,假设钦点C维度坐标为0,设这个答案是f(A,B,C),容易知道

\begin{aligned} f(A,B,C)&=\frac{1}{3}\sum_{i=0}^A\sum_{j=0}^B\frac{(A+B-i-j)^k}{3^{C+i+j}} \binom{C+i+j}{C,i,j}\\ &=\frac{1}{3}\sum_{i=0}^A\sum_{j=0}^B\frac{(A+B-i-j)^k}{3^{C+i+j}}\frac{(C+i+j)!}{C!i!j!} \end{aligned}

答案就是f(A,B,C)+f(A,C,B)+f(B,C,A) 这么做是O(\max(a,b,c)^2)

Subtask 2,4

容易发现i+j有很大一部分是相同的,可以作为加法卷积处理,考虑枚举T=i+j,式子变成

\begin{aligned} f(A+B+C)&=\frac{1}{3}\sum_{T=0}^{A+B}\frac{(A+B-T)^k}{3^{C+T}}\sum_{j=\max(T-A,0)}^{\min(B,T)}\frac{(C+T)!}{C!(T-j)!j!} \end{aligned}

后边的式子脱敏一下,变成只和T,C相关

\begin{aligned} f(A+B+C)&=\frac{1}{3}\sum_{T=0}^{A+B}\frac{(A+B-T)^k}{3^{C+T}}\sum_{j=\max(T-A,0)}^{\min(B,T)}\frac{(C+T)!T!}{C!T!(T-j)!j!}\\ &=\frac{1}{3}\sum_{T=0}^{A+B}\frac{(A+B-T)^k}{3^{C+T}}\sum_{j=\max(T-A,0)}^{\min(B,T)}\binom{C+T}{T}\binom{T}{j}\\ &=\frac{1}{3}\sum_{T=0}^{A+B}\frac{(A+B-T)^k}{3^{C+T}}\binom{C+T}{T}\sum_{j=\max(T-A,0)}^{\min(B,T)}\binom{T}{j} \end{aligned}

后面的关于T的量还是不好处理,但是对于\binom{T}{j}=\frac{T!}{(T-j)!j!}可以把分子作为卷积处理

g1_i=\frac{1}{i!},\forall i,i\leq A\\ g2_i=\frac{1}{i!},\forall i,i\leq B\\ g=g1 \times g2

直接\rm NTT即可,最多应该能做到1e5数据(要做好几次),除了这个以外和式里其他的都可以O(1)

这样总复杂度就是O(n\log n)

Subtask 5

唯一棘手的地方就是后面的和式,我们尝试观察他是怎么变化的

假设T>\max(A,B),对于T+1,对应上下界都+1,但是长度不变;也就是说在对一个左侧是直角边的杨辉三角的两个斜线之间的一行数求和乘上对应的系数;考虑组合数最朴素的递推式,假设第n行在限制内的和为S_n,显然:

\begin{aligned} S_n&=\sum_{i=L}^R\binom{n}{i}\\ &=\sum_{i=L}^R\binom{n-1}{i-1}+\binom{n-1}{i}\\ &=2\times S_{n-1}-\binom{n-1}{n-A-1}-\binom{n-1}{n-B-1} \end{aligned}

因此可以线性递推维护后面的和式。

对于T\leq A的情况,组合数能跑满,对应2^T

如果落在[A,B]内,就不需要带B的那一个二项式系数(此时斜线内后缀为0,所以那个二项式系数对应是0)。

ps:

对于x^k,x\leq n,因为是积性函数,因此可以线性筛。

ps2:

对于后面的T如果是定值,就可以变成前缀和维护,只需要钦点过程量维护就可以了,对于这个过程,有另外一题,同样是加法卷积处理。

------------------分界线-----------------

问题等价于矩形内的点走k部之后停在(n,m)的方案数

也就是问以(0,0)为起点停留在矩形内任意一点(a,b)的方案数

设向上下左右分别走了u,d,l,r步,那么u+d+l+r=k,并且r-l=b,u-d=a

解得r+u=\frac{k+a+b}{2},l+d=\frac{k-(a+b)}{2},那么由组合意义得到答案是

\sum_{a=0}^n\sum_{b= 0}^m[(a+b) \equiv k\pmod 2]\binom{k}{\frac{k+a+b}{2}}\sum_{c=b}^{\frac{k+b-a}{2}}\binom{\frac{k+a+b}{2}}{c}\binom{\frac{k-(a+b)}{2}}{c-b}

其中

\begin{aligned} &\sum_{c=b}^{\frac{k+b-a}{2}}\binom{\frac{k+a+b}{2}}{c}\binom{\frac{k-(a+b)}{2}}{c-b}\\ =&\sum_{c=0}^{\frac{k-(a+b)}{2}}\binom{\frac{k+a+b}{2}}{c+b}\binom{\frac{k-(a+b)}{2}}{c}\\ =&\sum_{c=0}^{\frac{k-(a+b)}{2}}\binom{\frac{k-(a+b)}{2}+a+b}{c+b}\binom{\frac{k-(a+b)}{2}}{c}\\ =&\sum_{c=0}^{\frac{k-(a+b)}{2}}\binom{\frac{k-(a+b)}{2}+a+b}{\frac{k-(a+b)}{2}+a-c}\binom{\frac{k-(a+b)}{2}}{c}\\ =&\binom{k}{\frac{k+(a-b)}{2}} \end{aligned}

倒数(2)式中显然c为后方二项式系数的枚举上下限,且两个二项式系数下式和恒定,因此可以由范德蒙德卷积导出为倒数(1)

答案即为

\sum_{a=0}^n\sum_{b= 0}^m[(a+b)\equiv k\pmod 2]\binom{k}{\frac{k+a+b}{2}}\binom{k}{\frac{k+(a-b)}{2}}

类似狄利克雷卷积中的提取操作,考虑令T=(a+b),则化为

\sum_{T=a+b=0}^{n+m}[T\equiv k\pmod 2]\binom{k}{\frac{k+T}{2}}\sum_{b=0}^{\min(m,T)}\binom{k}{\frac{k+T}{2}-b}

则后方和式可设为f(T)

因为a\leq n,b\leq m,a+b=T,对于某个T,设求和下限为L,上限为R,解得

1.对于T\leq \min(n,m)L=\frac{k-\min(m,T)}{2},R=\frac{k+\min(T,n)}{2}

2.对于T>\min(n,m)L=\frac{k+T-2\times \min(m,T)}{2},R=\frac{k+2\times \min(n,T)-T}{2}

f(T)=\sum_{L\leq u\leq R}\binom{k}{u}

前缀和维护即可。

容斥 前缀和 组合计数 多项式 NTT 线性递推

2022.10.3补
上一篇 «
2022.9.26补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors