Luogu 2019三月月赛 P5239 回忆京都 题解

题意

题目背景讲太多了吧。。。一句话题意: 有$Q$个询问,每个询问求出: $$\sum_{i=1}^n\sum_{j=1}^m C_j^i$$

对于$60$%的数据,$q \leq 10, n\leq100,m\leq100$。

对于$100$%的数据,$q \leq 1000,n\leq1000,m\leq1000$。

思路

对于60%的数据

直接暴力就好了。

预计得分:60分。

实际得分:70分。

O(∩_∩)O数据好水

直接用递归的方式记忆化求组合数。竟然可以拿70。

代码:

对于100%的数据

这里就有两种解法了:

1.利用前缀和

因为有许多题解都详细讲了,比如chen_zhe的题解,所以这里就不提了。

2.利用组合数的性质

这里先摆一条组合数的性质:$C(0,n)+C(1,n)+C(2,n)+…+C(n,n)=2^n$

这怎么证明呢?

根据二项式定理,可得:
$$(1+x)^n=C(0,n)+C(1,n)\times x +C(2,n)\times x^2+ … +C(n,n) \times x^n $$

令$x=1$,可得:

$$2^n=C(0,n)+C(1,n)+C(2,n)+(3,n)+…+C(n,n)$$

证毕。

什么?你不会二项式定理?百度百科

好了,再回归题目:

$$\sum_{i=1}^n\sum_{j=1}^m C_j^i$$

$$\sum_{i=1}^n\sum_{j=1}^m C_j^i=\sum_{i=1}^m\sum_{j=1}^m C_j^i-\sum_{i=n+1}^m \sum_{j=1}^m C_j^i$$

于是求解这道题就变成了求解两个子问题:

1.求解$\sum_{i=1}^m\sum_{j=1}^m C_j^i$
根据上面的组合数的性质:$C(0,n)+C(1,n)+C(2,n)+…+C(n,n)=2^n$

我们可以得出:

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=\sum_{i=1}^m [C(1,m)+C(2,m)+…+C(m,m)]$$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=\sum_{i=1}^m [C(0,m)+C(1,m)+C(2,m)+…+C(m,m)-C(0,m)]$$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=\sum_{i=1}^m [2^m-C(0,m)]$$

那么$C(0,m)=?$

答案是1。

所以
$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=\sum_{i=1}^m [2^m-1]$$

然后再把最外层的化开:

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=[2^1-1]+[2^2-1]+…+[2^m-1]$$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=2^1+2^2+…+2^m-1 \times m$$

根据:$2^0+2^1+2^2+…+2^n=2^{n+1}-1$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=2^{m+1}-1-2^0-1 \times m$$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=2^{m+1}-2-1 \times m$$

$$\sum_{i=1}^m\sum_{j=1}^m C_j^i=2^{m+1}-2-m$$

2.求解$\sum_{i=n+1}^m \sum_{j=1}^m C_j^i$
$$\sum_{i=n+1}^m \sum_{j=1}^m C_j^i=\sum_{i=n+1}^m \sum_{j=1}^i C_j^i+\sum_{i=n+1}^m \sum_{j=i+1}^m C_j^i$$

又因为题目:其中当$i>j$的时候,钦定$C^i_j=0$

并且:$C(n,n)=1$

所以:
$$\sum_{i=n+1}^m \sum_{j=1}^m C_j^i=\sum_{i=n+1}^m {(1+\sum_{j=i+1}^m C_j^i)}$$

于是对于每一个询问,只需要求出$\sum_{i=n+1}^m \sum_{j=i+1}^m C_j^i$即可。

汇总
好了,两个子问题都结束了。

那么对于每个询问:

$$\sum_{i=1}^n\sum_{j=1}^m C_j^i=2^{m+1}-2-m-\sum_{i=n+1}^m {(1+ \sum_{j=i+1}^m C_j^i)}$$

Code

暂无评论

发送评论


				
上一篇
下一篇