【bzoj2751】[HAOI2012]容易題(easy)

先考慮k=0的情況

那么第一個(gè)元素可能為[1,n] 如果序列長(zhǎng)度為m-1時(shí)的答案是ans[m-1]

那么合并得

然后同理答案就是

k很小 而且順序可以隨便交換

排序暴力減去就好了

1 /* http://www.cnblogs.com/karl07/ */ 2 #include <cstdlib> 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 9 const int P=1000000007; 10 int n,m,k,cnt=0,sum,ans=1; 11 struct data{int x,y;}d[100005]; 12 int Q_pow(int x,int y){ 13 int ans=1; 14 while (y){ 15 if (y&1) ans=1ll*ans*x%P; 16 x=1ll*x*x%P; 17 y=(y>>1); 18 } 19 return ans; 20 } 21 bool oper(data a,data b) {return ((a.x<b.x) || (a.x==b.x && a.y<b.y));} 22 23 int main(){ 24 scanf("%d%d%d",&n,&m,&k); 25 sum=1ll*n*(n+1)/2%P; 26 for (int i=1;i<=k;i++){ 27 scanf("%d%d",&d[i].x,&d[i].y); 28 } 29 sort(d+1,d+k+1,oper); 30 d[k+1].x=-1; 31 d[k+1].y=0; 32 for (int i=2,s=1ll*(sum-d[1].y+P)%P;i<=k+1;i++){ 33 if (d[i].x!=d[i-1].x) {ans=1ll*ans*s%P; s=sum; cnt++; } 34 if (d[i].y!=d[i-1].y || d[i].x!=d[i-1].x) s=(s-d[i].y+P)%P; 35 } 36 printf("%lld\n",1ll*ans*Q_pow(sum,m-cnt)%P); 37 return 0; 38 } View Code

這么水的題想了半天。。沒有調(diào)整負(fù)數(shù)WA了幾發(fā)。。藥丸。。

轉(zhuǎn)載于:https://www.cnblogs.com/karl07/p/6596183.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj2751】[HAOI2012]容易题(easy) 数论-快速幂的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。