药丸(原题)
一个长为 \(n\) 的空序列，每个位置可以随便填
0/(/)之一，如果去除 0 后不存在失配的)，并且失配(的个数 \(\in[l,r]\)，则称其为一合法括号序列。问有多少种填法使得得到的序列合法。\(0\le l\le r\le n\le 10^5\)，模数 \(p\le 2\times 10^9\) 不保证是质数。
很显然的 dp 是设 f[i][j] 表示前缀 i 失配 j 个 ( 的方案数，有：（1）f[i][j]=f[i-1]j+1（2）f[i][j]=f[i-1][j-1]+f[i-1]j+1。根据常见套路，可以视作平面走动，方向是向右上或向右下，从 (0,0) 走到 (n,i) 的方案数就是 f[n][i]，那么就是 \(n\choose {n-i\over 2}\)。但是——我们发现不对劲！因为可能走到 x 轴以下，而这是被严禁的。我当时本来按照错误的思路写到了 \(\sum_{i=0}^n{n\choose i}\sum_{j=\lceil (i-r)/2\rceil}^{\lfloor (i-l)/2\rfloor}{i\choose j}\)，然后思路就被打断了，没有想到什么好的解决办法，发现时间不太够就去打暴力了。然而，这个思路其实已经非常接近正解了。
我们考虑多算了甚麽，明显是“触碰到”y=-1 的走法们。于是我们减掉即可。如何钦定一个走法必须触碰 y=-1，根据将军饮马原理不难得出是 (0,-2) 走到 (n,i) 的方案数（走法还是没有限制的右上和右下），即 \(n\choose {n-i-2\over 2}\)原因在于我们欲达到目标必须越过该直线。只需要在上面的式子上减去一下就好了：
\[\sum_{i=0}^n{n\choose i}\sum_{j=\lceil (i-r)/2\rceil}^{\lfloor (i-l)/2\rfloor}{i\choose j}-{i\choose j-1}\\ =\sum_{i=0}^n{n\choose i}{i\choose \lfloor (i-l)/2\rfloor}-{i\choose \lfloor (i-r-1)/2\rfloor} \]可以看到这个式子通常可以直接求了，只要会算组合数模 p 就可以了，但是 p 不是质数的情况怎么算呢？
不会的同学可以看 套路题条件反射 No.26 条。
代码：
标签：lfloor,le,10.31,NOIP%,10.8,sum,rfloor,choose,失配 From： https://www.cnblogs.com/impyl/p/16769425.html