【题解】杨辉三角

题目链接(有道OJ)

题目

描述

杨辉三角形又称Pascal三角形,它的第$i+1$ 行是$(a+b)^i$的展开式的系数。

它的构造方式是:将三角形每一行两边的元素置为$1$,其它元素为这个元素“肩”上两元素之和。

下面给出了杨辉三角形的前5行:

1
2
3
4
5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
2 0 0 1
2 1 0 0
2 2 2 1

3 0 0 1
3 1 1 1
3 2 2 1
3 3 3 1

4 0 0 1
4 1 0 0
4 2 0 0
4 3 0 0
4 4 4 1

5 0 0 1
5 1 1 1
5 2 0 0
5 3 1 0
5 4 4 1
5 5 5 1

6 0 0 1
6 1 0 0
6 2 2 1
6 3 2 0
6 4 4 1
6 5 4 0
6 6 6 1

7 0 0 1
7 1 1 1
7 2 2 1
7 3 3 1
7 4 4 1
7 5 5 1
7 6 6 1
7 7 7 1

8 0 0 1
8 1 0 0
8 2 0 0
8 3 0 0
8 4 0 0
8 5 0 0
8 6 0 0
8 7 0 0
8 8 8 1

9 0 0 1
9 1 1 1
9 2 0 0
9 3 1 0
9 4 0 0
9 5 1 0
9 6 0 0
9 7 1 0
9 8 8 1
9 9 9 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
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll t,l,r;
int main(){
cin>>t>>l>>r;
for(ll i=l;i<=r;i++){
if(((t-1)&(i-1))==i-1) cout<<1;
else cout<<0;
}
return 0;
}