Luogu 2019三月月赛 P5239 回忆京都 题解
Luogu 2019三月月赛 P5239 回忆京都 题解
题意
个询问，每个询问求出：
对于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==mm==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
这怎么证明呢？
根据二项式定理，可得：
令x=1，可得：
证毕。
什么？你不会二项式定理？百度百科
好了，再回归题目：
于是求解这道题就变成了求解两个子问题：
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
我们可以得出：
那么C(0,m)=?
答案是1。
所以
然后再把最外层的化开：
根据：2^0+2^1+2^2+…+2^n=2^{n+1}-1
2.求解$\sum_{i=n+1}^m \sum_{j=1}^m C_j^i$
又因为题目：其中当i>jC^i_j=0
并且：C(n,n)=1
所以：
于是对于每一个询问，只需要求出\sum_{i=n+1}^m \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==mm==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;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019-03-03
，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
