首页 > 其他 > 详细

SP19997 MOON2 - Moon Safari (Hard) 【数论,多项式】

时间:2019-11-01 20:43:50      阅读:99      评论:0      收藏:0      [点我收藏+]

题目描述:求
\[ \sum_{i=1}^ni^kr^i \]
对某个质数取模。\(T\)组数据。

数据范围:\(n,r\le 10^{18},\sum k\le 2.56\times 10^6\)


数论神题。。。

我们设\(S_k(n)=\sum_{i=1}^{n-1}i^kr^i\),通过推通项公式,你会发现这个结论:
\[ S_k(n)=r^nF_k(n)-F_k(0) \]
其中\(F_k(n)\)是一个关于\(n\)且次数不高于\(k\)的多项式。

如何证明呢?首先你可以通过错位相减法得到一个递推公式,然后就可以数学归纳法了。

然后我们就是要求出\(F_k(0),F_k(1),F_k(2),\ldots,F_k(k+1)\),这样就可以通过拉格朗日插值求出\(F_k(n)\)

我们注意到\(S_k(n)-S_{k-1}(n)=r^nF_k(n)-r^{n-1}F_k(n-1)=r^{n-1}(n-1)^k\),所以\(F_k(n)=\dfrac{F_k(n-1)+(n-1)^k}{r}\)

然后我们知道,\(k\)次多项式的\(k+1\)阶差分为\(0\),即
\[ \sum_{i=0}^{k+1}(-1)^i\binom{k+1}{i}F_k(k+1-i)=0 \]
于是可以设\(F_k(0)=x\),然后不停代入,然后用这个式子解方程。具体实现可以写一个二项式binom来做。

注意特判一些特殊情况。时间复杂度\(O(k)\)

code

#include<bits/stdc++.h>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = 1000012, mod = 1e9 + 7;
inline int kasumi(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = (LL) res * a % mod;
        a = (LL) a * a % mod; b >>= 1;
    }
    return res;
}
inline void upd(int &a, int b){a += b; if(a >= mod) a -= mod;}
inline int add(int a, int b){return (a + b >= mod) ? (a + b - mod) : (a + b);}
inline int sub(int a, int b){return (a < b) ? (a + mod - b) : (a - b);}
int T, k, fac[N], inv[N];
LL n, r;
struct binom {
    int a, b;
    inline binom(int _a = 0, int _b = 0): a(_a), b(_b){}
    inline binom operator + (const binom &o) const {return binom(add(a, o.a), add(b, o.b));}
    inline binom operator - (const binom &o) const {return binom(sub(a, o.a), sub(b, o.b));}
    inline binom operator * (int v) const {return binom((LL) a * v % mod, (LL) b * v % mod);}
} S[N];
inline int lagrange(int *A, int k, LL n){
    static int pre[N], suf[N];
    pre[0] = suf[k + 1] = 1;
    for(Rint i = 1;i <= k;i ++) pre[i] = (n - i + 1) % mod * pre[i - 1] % mod;
    for(Rint i = k;i;i --) suf[i] = (n - i) % mod * suf[i + 1] % mod;
    int ans = 0;
    for(Rint i = 0;i <= k;i ++){
        int tmp = (LL) inv[i] * inv[k - i] % mod * pre[i] % mod * suf[i + 1] % mod;
        if((k - i) & 1) tmp = mod - tmp;
        upd(ans, (LL) A[i] * tmp % mod);
    }
    return ans;
}
int pri[N], tot, po[N], minp[N];
bool notp[N];
inline void init(int n){
    notp[0] = notp[1] = 1;
    for(Rint i = 2;i <= n;i ++){
        if(!notp[i]) pri[++ tot] = i;
        for(Rint j = 1;j <= tot && i * pri[j] <= n;j ++){
            notp[i * pri[j]] = 1; minp[i * pri[j]] = pri[j];
            if(!(i % pri[j])) break;
        }
    }
    fac[0] = 1;
    for(Rint i = 1;i <= n;i ++) fac[i] = (LL) fac[i - 1] * i % mod;
    inv[n] = kasumi(fac[n], mod - 2);
    for(Rint i = n;i;i --) inv[i - 1] = (LL) inv[i] * i % mod;
}
inline void calc(int k){
    po[0] = 0; po[1] = 1;
    for(Rint i = 2;i <= k + 1;i ++)
        if(notp[i]) po[i] = (LL) po[minp[i]] * po[i / minp[i]] % mod;
        else po[i] = kasumi(i, k); 
}
inline int C(int n, int m){if(n < 0 || m < 0 || n < m) return 0; return (LL) fac[n] * inv[m] % mod * inv[n - m] % mod;}
inline int solve(LL n, int k, int r){
    static int F[N];
    int invr = kasumi(r, mod - 2);
    if(!r) return 0;
    memset(F, 0, (k + 2) << 2);
    calc(k);
    if(r == 1){
        for(Rint i = 1;i <= k + 1;i ++) F[i] = add(F[i - 1], po[i]);
        return n <= k + 1 ? F[n] : lagrange(F, k + 1, n);
    }
    if(!n) return 0;
    if(!k) return (LL) sub(kasumi(r, n + 1), r) * kasumi(r - 1, mod - 2) % mod;
    S[0] = binom(1, 0);
    for(Rint i = 1;i <= k + 1;i ++)
        S[i] = (S[i - 1] + binom(0, po[i - 1])) * invr;
    binom qwq;
    for(Rint i = 0;i <= k + 1;i ++)
        if(i & 1) qwq = qwq + S[k + 1 - i] * C(k + 1, i);
        else qwq = qwq - S[k + 1 - i] * C(k + 1, i);
    F[0] = (LL) (mod - qwq.b) * kasumi(qwq.a, mod - 2) % mod;
    for(Rint i = 1;i <= k + 1;i ++) F[i] = (LL) add(F[i - 1], po[i - 1]) * invr % mod;
    int ans = lagrange(F, k + 1, n + 1);
    return (LL) sub((LL) ans * kasumi(r, (n + 1) % (mod - 1)) % mod, F[0]);
}
int main(){
    scanf("%d", &T); init(1000010);
    while(T --){
        scanf("%lld%lld%d", &n, &r, &k);
        printf("%d\n", solve(n, k, r % mod));
    }
}

SP19997 MOON2 - Moon Safari (Hard) 【数论,多项式】

原文:https://www.cnblogs.com/AThousandMoons/p/11779232.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!