BZOJ 2751: [HAOI2012]容易题(easy)
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2751
题解
把所有式子画一画，我们会发现最后的答案是这样一个公式(\prod_{i=1}^m \sum_{j=1}^n j[Available_{i,j}])
所以我们只需要统计每一位可以使用的数字和，然后累乘即可。
代码
|
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 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn=1e5; const LL MOD=1000000007; int n,m,k; struct BanNode{ int pos,val; }; BanNode b[Maxn+5]; inline bool cmpBNode(BanNode a,BanNode b){ if (a.pos!=b.pos) return a.pos<b.pos; return a.val<b.val; } inline long long powX(LL x,int t){ LL ret=1; while(t){ if (t&1) ret=ret*x%MOD; x=x*x%MOD; t/=2; } return ret; } int main(){ scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=k;i++) scanf("%d%d",&b[i].pos,&b[i].val); sort(b+1,b+k+1,cmpBNode); int cnt=m; LL Ans=1; LL sum=(n*(n+1LL)/2LL)%MOD; LL rateSum=1; for (int i=1;i<=k;i++){ if (i==1 || (b[i].pos!=b[i-1].pos)){ Ans=Ans*rateSum%MOD; rateSum=sum; cnt--; } if (i==1 || (b[i].pos!=b[i-1].pos) || (b[i].pos==b[i-1].pos && b[i].val!=b[i-1].val)) rateSum=(rateSum-b[i].val+MOD)%MOD; } Ans=Ans*rateSum%MOD; printf("%lld\n",Ans*powX(sum,cnt)%MOD); return 0; } |
原文链接：BZOJ 2751: [HAOI2012]容易题(easy)
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!