[Solution][MathTheory]BZOJ2142 礼物

【题目】

戳这里

【题意】

自行脑补。

【做法】

实在不想多说。。。见若干神犇blog.

http://phoebus.logdown.com/posts/192444-solution-bzoj2142-gift

http://hi.baidu.com/aekdycoin/item/e051d6616ce60294c5d249d7

【代码】

/**************************************************************
    Problem: 2142
    User: wyfcyx
    Language: C++
    Result: Accepted
    Time:212 ms
    Memory:824 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstring>
typedef long long LL;
LL d , x , y;
void exgcd(LL a , LL b , LL &d , LL &x , LL &y)
{
    if (!b)
    {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        exgcd(b , a % b , d , y , x);
        y -= x * (a / b);
    }
}
LL inv(LL a , LL n)
{
    exgcd(a , n , d , x , y);
    return (x % n + n) % n;
}
LL ksm(LL A , LL B , LL p)
{
    LL ans = 1;
    while(B)
    {
        if (B & 1)
            ans = (ans * A) % p;
        A = (A * A )% p;
        B >>= 1;
    }
    return ans;
}
LL P;
int ind;
LL save[100];
LL num[100];
LL mi[100];
LL mod[100];
void pre()
{
    LL limit = LL(sqrt(P));
    LL tmp = P;
    register LL i;
    for(i = 2 ; i <= limit ; ++i)
    {
        if (tmp % i == 0 && tmp >= i)
            save[++ind] = i , mi[ind] = 1;
        while(tmp % i == 0)
        {
            mi[ind] *= i;
            tmp /= i;
        }
    }
    if (tmp != 1)
        save[++ind] = tmp , mi[ind] = tmp;
    for(i = 1 ; i <= ind ; ++i)
        mod[i] = 1;
}
LL add;
LL get(LL n , LL A , LL B , LL sign) //get n! % B (B = A ^ ???)
{
    register LL i;
    LL res = 1;
    if (n <= A)
    {
        for(i = 2 ; i <= n ; ++i)
            res = (res * i) % B;
        return res;
    }
    LL k = n / A;
    add += sign * k;
    for(i = n / B * B + 1 ; i <= n ; ++i)
        if (i % A)
            res = (res * i) % B;
    if (n > B)
    {
        LL tmp = 1;
        for(i = 1 ; i <= B ; ++i)
            if (i % A)
                tmp = (tmp * i) % B;
        res = res * ksm(tmp , n / B , B) % B;
    }              
    return res * get(k , A , B , sign) % B;
}
void getans(LL n , LL x)
{
    for(register int i = 1 ; i <= ind ; ++i)
    {
        add = 0;
        mod[i] = mod[i] * get(n , save[i] , mi[i] , 1) % mi[i];
        mod[i] = mod[i] * inv(get(x , save[i] , mi[i] , -1) , mi[i]) % mi[i];
        mod[i] = mod[i] * inv(get(n - x , save[i] , mi[i] , -1) , mi[i]) % mi[i];
        mod[i] = mod[i] * ksm(save[i] , add , mi[i]) % mi[i];
    }
}
int main()
{
    scanf("%lld" , &P);
    pre();
    LL n , m;
    scanf("%lld%lld" , &n , &m);
    LL tmp , ans = 0;
    while(m--)
    {
        scanf("%lld" , &tmp);
        if (n < tmp)
        {
            puts("Impossible");
            return 0;
        }
        getans(n , tmp);
        n -= tmp;
    }
    for(register int i = 1 ; i <= ind ; ++i)
        ans = (ans + ((P / mi[i]) * inv(P/mi[i] , mi[i])) % P * mod[i]) % P;
    printf("%lld" , ans);
    return 0;
}
comments powered by Disqus