首页 > 代码库 > [HAOI2012] 容易题
[HAOI2012] 容易题
有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 mod 1000000007的值；
--by洛谷；
http://daniu.luogu.org/problem/show?pid=2220
《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《《
简单题？呵呵
首先，她有个公式
我们先假设k=0;
ai为a位的可能;bi为b位的可能;ci为c位的可能...
则：
a1*b1*c1+a1*b1*c2+a1*b2*c1+a1*b2*c2+a2*b1*c1+a2*b1*c2+a2*b2*c1+a2*b2*c2;
你提公因式嘛；
a1*(b1*c1+b1*c2+b2*c1+b2*c2)+a2*(b1*c1+b1*c2+b2*c1+b2*c2);
再提
a1*[b1*(c1+c2)+b2*(c1+c2)]+a2*[b1*(c1+c2)+b2*(c1+c2)];
a1*(b1+b2)*(c1+c2)+a2*(b1+b2)*(c1+c2);
(a1+a2)*(b1+b2)*(c1+c2);
再通过k的存在，对每位的可能减zi;
(a1+a2-z1)*(b1+b2-z2)*(c1+c2-z3);
然后每一位在k=0一样，即a1+a2=b1+b2=c1+c2=sum（n）;
(sum（n）-z1)*(sum（n）-z2)*(sum（n）-z3);
所以，这叫简单题？
就想预处理sum(n)然后O(n)乘，每次记得减z;
然而O(n)也过不了----n=1e9。。。
所以，这叫简单题？
但是我们发现，k比较小，1e5；
所以有限制的位置，小于等于1e5；
我们可以先算她们，然后剩下的写一个快速幂；
时间效率O(klogk+k+log(n-k))；
（因为有个sort）;
代码如下：
#include<cstdio>#include<algorithm>#define mod 1000000007using namespace std;struct ss{ int x,y;}a[100001];long long b[100001];bool cmp(ss a,ss b){ if(a.x==b.x) return a.y<b.y; return a.x<b.x;}long long sqr(long long ,int );int main(){ int n,m,k; long long sz1=0; long long ans=1; int i,j,l; scanf("%d%d%d",&n,&m,&k); sz1=(long long)n*(n+1)/2%mod; for(i=1;i<=k;i++) scanf("%d%d",&a[i].x,&a[i].y); sort(a+1,a+k+1,cmp); j=0; for(i=1;i<=k;i++) { if(a[i].x!=a[i-1].x) b[++j]=a[i].y; else if(a[i].y!=a[i-1].y) b[j]=(b[j]+a[i].y)%mod; } for(i=1;i<=j;i++) ans=(ans*(sz1-b[i]+mod))%mod; m=m-j; ans=(ans*sqr(sz1,m))%mod; printf("%lld",ans); return 0;}long long sqr(long long sz,int m){ long long ans=1; while(m) { if(m&1) ans=(ans*sz)%mod; sz=(sz*sz)%mod; m=m>>1; } return ans;}
祝AC哟；
[HAOI2012] 容易题