【题解】杨辉三角
题目
描述
杨辉三角形又称Pascal三角形，它的第\(i+1\) 行是\((a+b)^i\)的展开式的系数。
它的构造方式是：将三角形每一行两边的元素置为\(1\)，其它元素为这个元素“肩”上两元素之和。
下面给出了杨辉三角形的前5行：
1 | 1 |
请你输出杨辉三角第\(t\)行的第\(l\)个数 到 第\(r\)个数 中，每个数除以\(2\)的余数。
输入
输入数据只有一行\(3\)个数\(t,l,r\)表示杨辉三角第\(t\)行的第\(l\)个数到第\(r\)个数。
输出
输出一行，一个\(0101\)串，第\(i\)位表示第\(t\)行的第\(l+i-1\)列的数对\(2\)取模的余数。
样例
输入样例
1 | 5 1 5 |
输出样例
1 | 10001 |
提示
对于\(20\%\)的数据，\(t\le 10^4\)
对于\(60\%\)的数据，\(t\le 10^8\)
对于\(100\%\)的数据，\(t\le 10^{18},1\le l\le r\le t,r-l\le 10^4\)
其中\(20\%\)的数据满足\(l=1\)或\(r=t\)
分析
从定义可以很容易得到杨辉三角的递推通项：\(f(i,j)=f(i-1,j-1)+f(i-1,j)\)
于是易得\(O(n^2)\)的递推做法。
因为杨辉三角可以转化为组合数：\(f(i,j)=C^{i-1}_{j-1}\)，因为题目要求输出\(01\)串，想到位运算。实用上文方法找打表规律，分别输出\(i-1,j-1,(i-1)\&(j-1),f(i,j) \mod 2\)
1 | 2 0 0 1 |
不难发现，所有\((i-1)\&(j-1)=j-1\)的项都等于1。
下面给出严格的证明：
众所周知，根据组合数的定义，\(C^m_n=\frac{n!}{m!(n-m)!}\)
设\(n!,m!,(n-m)!\)的\(2\)的因子个数为\(x,y,z\)，显然当且仅当\(x=y+z\)时，组合数为奇数。
对于一个质数\(p\)，它在\(n!\)中的因子个数为：
\(\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\lfloor\frac{n}{p^3}\rfloor+\lfloor\frac{n}{p^4}\rfloor+...\)
设对于\(n!\)来说它的\(2\)的因子个数是\(f(n)\)，则
\(f(n)=\)\(\lfloor\frac{n}{2}\rfloor+\lfloor\frac{n}{2^2}\rfloor+\lfloor\frac{n}{2^3}\rfloor+\lfloor\frac{n}{2^4}\rfloor+...\)
又因为\(n=(a_0\times2^0)+(a_1\times 2^1)+(a_2\times 2^2)+...+(a_k\times 2^k)\)
因此可以化简\(f(n)\)的表达式为：
\[f(n)=\sum_{i=0}^{k}\lfloor \frac{(a_0\times2^0)+(a_1\times 2^1)+(a_2\times 2^2)+...+(a_k\times 2^k)}{2^i}\rfloor\]
\[=\sum_{i=0}^{k}\lfloor \frac{(a_i\times2^i)+...+(a_k\times 2^k)}{2^i}\rfloor\]
\[=\sum_{i=0}^k \sum_{j=i+1}^k \frac{a_j \times 2^j} {2^i} \]
\[=\sum_{i=0}^ka_i\sum^{i-2}_{j=0}2^j\]
\[=\sum^k_{i=0}a_i \times(2^i-1)\]
\[=\sum_{i=0}^{k}a_i\times 2^i-\sum_{i=0}^k a_i\]
\[=n-\sum_{i=0}^k a_i\]
如何快速求出\(\sum_{i=0}^k a_i\)？显然它等于\(n\)在2进制下1的个数。
所以，\(f(n)=n-n\)在二进制下\(1\)的个数。
回到题目，设\(n!,m!,(n-m)!\)在二进制下\(1\)的个数分别为\(A,B,C\)。为因为组合数为奇数当且仅当\(a=b+c\)，即\(n-A=m-B+(n-m)-C\)，即\(A=B+C\)。
显然，要满足上述条件，当且仅当\(n\&m=m\)。
于是可得本题\(O(r-l)\)做法。
代码
1 |
|