题意
对于$60$%的数据,$q \leq 10, n\leq100,m\leq100$。
对于$100$%的数据,$q \leq 1000,n\leq1000,m\leq1000$。
思路
对于60%的数据
直接暴力就好了。预计得分:60分。
实际得分:70分。
O(∩_∩)O
直接用递归的方式记忆化求组合数。竟然可以拿70。
代码:
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 |
#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
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 |
#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; } |