洛谷 P2220 [HAOI2012]容易题 数论
洛谷 P2220 [HAOI2012]容易题
题目描述
为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下:
有一个数列A已知对于所有的A[i]都是1~n的自然数,并且知道对于一些A[i]不能取哪些值,我们定义一个数列的积为该数列所有元素的乘积,要求你求出所有可能的数列的积的和 mod 1000000007的值,是不是很简单呢?呵呵!
输入格式
第一行三个整数n,m,k分别表示数列元素的取值范围,数列元素个数,以及已知的限制条数。
接下来k行,每行两个正整数x,y表示A[x]的值不能是y。
输出格式
一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有,答案输出0。
输入输出样例
输入 #1
3 4 5
1 1
1 1
2 2
2 3
4 3
输出 #1
90
说明/提示
样例解释
A[1]不能取1
A[2]不能去2、3
A[4]不能取3
所以可能的数列有以下12种
数列 积
2 1 1 1 2
2 1 1 2 4
2 1 2 1 4
2 1 2 2 8
2 1 3 1 6
2 1 3 2 12
3 1 1 1 3
3 1 1 2 6
3 1 2 1 6
3 1 2 2 12
3 1 3 1 9
3 1 3 2 18
30%的数据n<=4,m<=10,k<=10
另有20%的数据k=0
70%的数据n<=1000,m<=1000,k<=1000
100%的数据 n<=10\(^9\),m<=10\(^9\),k<=10\(^5\),1<=y<=n,1<=x<=m
分析
我们先去考虑没有限制的情况,那么最终的答案就是
\(( 1+2+3+……+n)^{m}=(\frac{n\times(n-1)}{2})^{m}\)
为什么是这样呢?其实我们可以把数列的每一个元素看成一个集合
每一次我们可以从每个集合中任意取出\(n\)个元素
这\(n\)个元素的值分别为\(1 - n\)
根据乘法原理最终的结果就是
\((1+2+3+……+n)\times(1+2+3+……+n)\times……\)
一共要乘\(m\)次
如果还不理解的话,你可以随便举一个例子,按照上面的式子把它展开
但是,题目中有些元素是取不到的
我们可以记录一下每一个元素取不到的值的和\(tot\)
我们只要把该元素贡献的价值改为\(\frac{n\times(n-1)}{2}-tot\)就可以了
因为题目中的限制条件最多只有\(10^{5}\)个
所以我们记录下有限制条件的元素的个数\(cnt\),对其单独处理
对于其余的元素,我们用快速幂的思想求出\((\frac{n\times(n-1)}{2})^{m-cnt}\)
最后再把所有的结果累乘就可以了
要注意两个问题:
1、因为结果很大,能取模的地方就取模
2、要注意判重,样例已经给出重复的情况了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
const long long mod=1e9+7;
typedef long long ll;
map<pair<ll,ll>,ll> ma1;
map<ll,ll> ma2;
ll jl[maxn];
ll cf(ll now,ll zs){
ll jl=now%mod,ans=1;
while(zs){
if(zs&1) ans*=(jl%mod),ans%=mod;
jl*=(jl%mod),jl%=mod;
zs>>=1;
}
return ans;
}
int main(){
ll n,m,k,js=0;
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=k;i++){
ll aa,bb;
scanf("%lld%lld",&aa,&bb);
if(!ma2[aa]) jl[++js]=aa;
if(ma1[make_pair(aa,bb)]) continue;
ma1[make_pair(aa,bb)]=1;
ma2[aa]+=bb;
}
ll ans=1,cj=(n+1)*n/2;
for(ll i=1;i<=js;i++){
ans*=(cj-ma2[jl[i]])%mod;
ans%=mod;
}
printf("%lld\n",ans%mod*cf(cj,m-js)%mod%mod);
return 0;
}
最新文章
- OpenSNS开发笔记(1)
- 9.SpringMVC和json结合传递参数
- 待实验:Android 增量升级
- golang的验证码相关的库
- MVVM解决方案的一般结构
- JAVA时钟
- C++学习笔记3—对话框
- [SHOI2007]善意的投票
- Nginx 中利用 Lua 脚本做访问控制
- Goland2019.1破解
- 监控redis
- CMDB资产管理系统开发【day25】:表结构设计2
- Linux Django项目测试
- java web 下载本地文件并弹出下载框
- Flutter &; Dart 安装在window系统
- 基于HTML5 Canvas的工控SCADA模拟飞机飞行
- 任务02——安装 Intellj IDEA,编写一个简易四则运算小程序,并将代码提交到 GitHub
- 20162314 Experiment 2 - Tree
- linux用户权限 ->; ACL访问控制
- Python isspace() 方法
热门文章
- 记一次discuz修改首页图片路径问题
- 彻底搞懂 etcd 系列文章(三):etcd 集群运维部署
- 运行ABP(asp.net core 3.X+Vue)提示&#39;OFFSET&#39; 附近有语法错误。 在 FETCH 语句中选项 NEXT 的用法无效。
- JNI_day02
- 内存管理,goto的使用,内存的申请和释放,mmap,ioremap
- Photoshop 使用过程中遇到的问题
- 使用iText生成pdf文件
- UIPopoverPresentationController的使用
- C# Winform界面不能适配高DPI的解决方法
- [每日一题2020.06.10]Codeforces Round #644 (Div. 3) ABCDEFG