almost 4 years ago

很想来写点这个方面的东西。

的值 ,n,m ,p

怎么求呢

首先来考虑 p 是质数的情况。 组合

对于分母,求出其关于p的逆元,则 等价于

再来考虑不是质数的情况。
由中国剩余定理,

所以我们可以分若干个式子来求得:

所以我们只要考虑关于 的问题了
根据定理,首先我们把分式上下关于的因子提出来

上下都有的因子,如果 显然模就是,否则

上下又带了一个阶乘,我们可以递归的处理。于是可以求出得到的当前式子的答案。

最后用中国剩余定理合并。

贴个代码吧,题目是HNOI2014省队集训的一个裸题(其实就是n取m模p)。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 100010
using namespace std;

long long mo,n,m;
long long prime[N],p[N],cnt,x,y,t,ex[N],ans,tot,pp[N];
bool vis[N];
inline void prepare() 
{
   for (int i = 2;i <= mo;i++) 
       {
            if (!vis[i]) prime[++tot] = i;
            for (int j = 1;j <= tot && i * prime[j] <= mo;j++)
                  {
                       vis[i * prime[j]] = 1;
                       if (i % prime[j] == 0) break;
                  }
      }
}

inline long long pow(long long t,long long y,long long z)
{
    long long r = 1;
    for ( ; y; y >>= 1 , t = t * t % z) 
        if (y & 1) r = r * t % z;
    return r;
}

inline void ex_gcd(long long a, long long b, long long &x, long long &y) {
    if (!b) {x = 1, y = 0; return; }
    else { ex_gcd(b, a % b, y, x), y -= (a / b) * x; }
}

inline long long Inv(long long x, long long y) {
    long long rx, ry;  ex_gcd(x, y, rx, ry);
    return rx = (rx + y) % y;
}

inline long long calc(long long A, long long B, long long C, long long x, long long y) {
    if (!B && !C) return 1;
    long long res = pow(x, A / x - B / x - C / x, y);
    res = res * calc(A / x, B / x, C / x, x, y) % y;
    long long cA = pow(ex[y], A / y, y) * ex[A % y] % y;
    res = res * cA % y;
    long long cB = pow(ex[y], B / y, y) * ex[B % y] % y, cC = pow(ex[y], C / y, y) * ex[C % y] % y;
    cB = Inv(cB, y), cC = Inv(cC, y);
    return res * cB * cC % y;
}

inline long long ex_Lucas() {
    long long x = mo, cnt = 0;
    for (int i = 1;i <= tot;i++) if (x % prime[i] == 0) {
        p[i] = 1, pp[++cnt] = i;
        for ( ; x % prime[i] == 0; x /= prime[i]) p[i] *= prime[i];
    }

    for (int o = 1;o <= cnt;o++) {
        long long t = pp[o];
        ex[0] = 1;
        for (int i = 1;i <= p[t];i++) ex[i] = i % prime[t] ? ex[i - 1] * i % p[t] : ex[i - 1];
        long long ansx = calc(n, n - m, m, prime[t], p[t]);
        ans = (ans + ansx * Inv(mo / p[t], p[t]) % mo * (mo / p[t]) % mo) % mo;
    }
    return ans;
}

int main() {

    scanf("%I64d%I64d%I64d", &n, &m, &mo);
    prepare();
    printf("%I64d",ex_Lucas());

    return 0;
}

此算法全权是琛琛教我的

← CF #257 .Div 1 SGU 280 →
 
comments powered by Disqus