[Solution][乱搞]BZOJ2751

【题目】

戳这里

【思路】

我都1A的大水题。

首先注意到只要把每一个数的所有可能情况相加,再依次相乘即可得出答案。

比较暴力地开若干个map存一下就行了。。。

注意乘法要用快速加,否则爆longlong...

【代码】

#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
map<int , int> hash;
int top;
map<int , int> ext[100000];
int save[100010];
const LL mod = 1000000007;
LL mul(LL a , LL b)
{
    LL res = 0 , tmp = a;
    while(b)
    {
        if (b & 1)
            res = (res + tmp) % mod;
        tmp = (tmp + tmp) % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    LL limit , n;
    int forbid;
    scanf("%lld%lld%d" , &limit , &n , &forbid);
    register int i , j;
    int ins , num;
    for(i = 1 ; i <= forbid ; ++i)
    {
        scanf("%d%d" , &ins , &num);
        if (hash.find(ins) == hash.end())
            hash[ins] = top++;
        ins = hash[ins];
        if (ext[ins].find(num) == ext[ins].end())
        {
            ext[ins][num] = 1;
            save[ins] += num;
        }
    }
    LL add = (limit + 1) * limit / 2;
    LL ans = 1;
    for(i = 0 ; i < top ; ++i)
        ans = mul(ans , add - save[i]);
    LL t = n - top;
    while(t)
    {
        if (t & 1)
            ans = mul(ans , add);
        add = mul(add , add);
        t >>= 1;
    }
    printf("%lld" , ans);
    return 0;
}
comments powered by Disqus