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

2019-03-03 09:47:07


欢迎到Blog食用

题意

题目背景讲太多了吧。。。一句话题意:

有 $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。

代码:

#include<bits/stdc++.h>
#define mod 19260817
#define int long long
using namespace std;
inline int read(){
    char ch=getchar();int res=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
int a[2010][2010];
int C(int n,int m){//递归求组合数
    if(a[n][m]!=0){
        return a[n][m];
    }
    if(n<m){
        return 0;
    }
    if(n==m||m==0){
        return a[n][m]=1;
    }
    if(m==1){
        a[n][m]=n%mod;
        return n%mod;
    }else{
        a[n][m]=C(n-1,m-1)%mod+C(n-1,m)%mod;//C(n,m)=C(n-1,m)+C(n-1,m-1)
        a[n][m]%=mod;
        return a[n][m];
    }
}
int q,n,m,ans;
signed main(){
    q=read();
    while(q--){
        n=read();m=read();ans=0;//ANS清零
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                ans+=C(i,j);
                ans%=mod;
            }
        }
        write(ans);putchar('\n');
    }
    return 0;
}

对于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

#include<bits/stdc++.h>
#define mod 19260817
#define int long long
using namespace std;
inline int read(){//读入优化
    char ch=getchar();int res=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
inline void write(int x){//输出优化
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else{
        write(x/10);
        putchar(x%10+'0');
    }
}
int a[2010][2010],pw[1010];//分别记录组合数、2的次幂
int C(int n,int m){//递归记忆化求组合数
    if(a[n][m]!=0){
        return a[n][m];
    }
    if(n<m){
        return 0;
    }
    if(n==m||m==0){
        return a[n][m]=1;
    }
    if(m==1){
        a[n][m]=n%mod;
        return n%mod;
    }else{
        a[n][m]=C(n-1,m-1)%mod+C(n-1,m)%mod;
        a[n][m]%=mod;
        return a[n][m];
    }
}
int q,n,m,ans;
signed main(){
    q=read();pw[0]=1;
    for(int i=1;i<=1005;i++){//预处理2^k
        pw[i]=pw[i-1]*2;pw[i]%=mod;
    }
    while(q--){
        n=read();m=read();
        ans=pw[m+1];ans-=2;ans-=m;ans+=mod;ans%=mod;//子问题1
        for(int j=n+1;j<=m;j++){//子问题2
            ans--;
            for(int i=j+1;i<=m;i++) ans-=C(i,j),ans+=mod,ans%=mod;
        }
        write(ans);putchar('\n');
    }
    return 0;
}