bzoj 2751 [HAOI2012]容易题(easy)（数学）

【题目链接】

http://www.lydsy.com/JudgeOnline/problem.php?id=2751

【题意】

m个位置，已知每个位置的可能取值，问所有可能情况的每个位置的乘积的和。

【思路】

答案即为∏ΣAij，Aij为第i个位置的第j种取值。

前K中情况减去不可能的取值单独算sigma，后面的取值统一算为(((n+1)n)/2)^(m-K)。

【代码】

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int N =2e5+;

 const int mod = 1e9+;

 ll read() {

     char c=getchar();

     ll f=,x=;

     while(!isdigit(c)) {

         if(c=='-') f=-; c=getchar();

     }

     while(isdigit(c))

         x=x*+c-'',c=getchar();

     return x*f;

 }

 struct Node {

     int pos,val;

     bool operator < (const Node& rhs) const{

         return pos<rhs.pos||(pos==rhs.pos&&val<rhs.val);

     }

 }a[N];

 int n,m,K;

 ll pow(ll a,ll p,ll mod)

 {

     ll ans=;

     while(p)

     {

         if(p&) ans=(ans*a)%mod;

         a=(a*a)%mod; p>>=;

     }

     return ans;

 }

 int main()

 {

     n=read(),m=read(),K=read();

     for(int i=;i<=K;i++)

     {

         a[i].pos=read(),

         a[i].val=read();

     }

     sort(a+,a+K+);

     ll ans=,sum=(ll)n*(n+)/%mod,tmp=,cnt=;

     for(int i=;i<=K+;i++)

     {

         if(i>&&a[i].pos!=a[i-].pos)

         {

             ans=ans*(sum-tmp+mod)%mod;

             tmp=; cnt++;

         }

         if(a[i].pos==a[i-].pos&&a[i].val==a[i-].val) continue;

         tmp=(tmp+a[i].val)%mod;

     }

     ans=(ll)ans*pow(sum,m-cnt,mod)%mod;

     printf("%lld\n",ans);

     return ;

 }