首页 > 代码库 > BZOJ 2751 HAOI 2012 容易题(easy) 数学
BZOJ 2751 HAOI 2012 容易题(easy) 数学
题目大意:给出一个序列中哪个位置不能出现哪一种数字,求可以组成的数列的积的和。
思路:如果我们让第一个位置确定,那么这个问题就可以转化成一个子问题。也就是第一位的数字乘上后面的积的和。推下去的话不难发现,其实求得就是每一位和的积。观察一下mn都很大,之后k不大,于是就用个map啥的随便记录一下,然后写个快速幂,再写个快速乘,没了。。
CODE:
#include <map> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define MO 1000000007 using namespace std; map<int,long long> G; int range,cnt,k; long long base; struct Complex{ int pos,ban; bool operator <(const Complex &a)const { if(pos == a.pos) return ban < a.ban; return pos < a.pos; } void Read() { scanf("%d%d",&pos,&ban); } }src[MAX]; inline long long Plus(long long x,long long y) { long long re = 0; while(y) { if(y&1) re = (re + x) % MO; x = (x << 1) % MO; y >>= 1; } return re; } inline long long Quick(long long x,long long y) { long long re = 1; while(y) { if(y&1) re = Plus(re,x) % MO; x = Plus(x,x) % MO; y >>= 1; } return re; } int main() { cin >> range >> cnt >> k; for(int i = 1; i <= k; ++i) src[i].Read(); sort(src + 1,src + k + 1); for(int i = 1; i <= k; ++i) if(src[i].ban != src[i - 1].ban || src[i].pos != src[i - 1].pos) G[src[i].pos] += src[i].ban; if(range&1) base = Plus((range + 1) / 2,range) % MO; else base = Plus(range / 2,range + 1) % MO; long long ans = 1; int total = 0; for(map<int,long long>::iterator it = G.begin(); it != G.end(); ++it,++total) { long long temp = base - it->second; while(temp < 0) temp += MO; temp %= MO; ans = Plus(ans,temp) % MO; } ans = Plus(ans,Quick(base,cnt - total)) % MO; printf("%lld\n",ans); return 0; }
BZOJ 2751 HAOI 2012 容易题(easy) 数学
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。