【题解】杨辉三角
题目
描述
杨辉三角形又称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)$的表达式为:
如何快速求出$\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 |
|