「BZOJ 3328」PYXFIB

给定 $n,k,p$ ,求 $\sum\limits_{i = 0}^n [k|i] C_n^i f_i \pmod p$,同时保证$p \equiv 1 \pmod k$。

这题一个比较核心的 idea 和之前 CSA 上一个题挺像的。

首先我们考虑,假设没有$[k|i]$的限制怎么处理,我们令斐波那契数列的转移矩阵为$A$,那么根据二项式定理,答案为$(A + I)^n$,利用矩乘快速求出结果。接着考虑怎么满足上面那个限制。

我们发现有一个看起来很关键的性质没有用到,保证 $p​$为质数而且 $p \equiv 1 \pmod k​$,那么也就是说 $k |(p - 1)​$,那么我们找到 $p​$ 的原根 $g​$ ,令 $w = g^{\frac{(p - 1)}{k}}​$,容易发现对于 $\sum\limits_{i = 0}^{k - 1} w^{ix}​$来说,当 $x \equiv 0 \pmod k​$时,其为 $k​$,否则为 $0​$。

有了这个技巧,我们考虑变换一下上面的式子:

$$\sum\limits_{x = 0}^{k = 1} \sum\limits_{i = 0}^{n - 1} C_n^i f_i w^{ix} = \sum\limits_{x = 0}^{k - 1} w^{nx} \sum\limits_{i = 0}^{n - 1} C_n^i f_iw^{-x(n - i)}$$

然后利用二项式定理即可。

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

int mod;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

int qpow(int a, int b){
    int c = 1;
    while (b) {
        if (b & 1) cmul(c, a);
        cmul(a, a); b >>= 1;
    }
    return c;
}

int T;

struct matrix {
    int m[3][3], n;
    matrix () {}
    matrix (int n, int o) : n(n) {
        memset(m, 0, sizeof(m));
        up (i, 1, n) m[i][i] = o;
    }
};

inline matrix operator * (const matrix & a, const matrix & b) {
    matrix c = matrix(a.n, 0);
    up (k, 1, c.n) up (i, 1, c.n) up (j, 1, c.n) cadd(c.m[i][j], mul(a.m[i][k], b.m[k][j]));
    return c;
}

int getroot(){
    up (g, 2, mod) {
        int p = mod - 1, x = mod - 1, m = sqrt(x);
        bool vaild = 1;
        up (i, 2, m) if (x % i == 0) {
            if (qpow(g, p / i) == 1) vaild = 0;
            while (x % i == 0) x /= i;
        }
        if (x > 1 && qpow(g, p / x) == 1) vaild = 0;
        if (vaild) return g;
    }
    return -1;
}

int main(){
    scanf("%d", &T);
    ll n; int k;
    while (T--) {
        scanf("%lld%d%d", &n, &k, &mod);
        int g = getroot(), w = qpow(g, (mod - 1) / k), ans = 0;
        int cur = 1, r = qpow(w, n % (mod - 1));
        up (i, 0, k - 1) {
            int sum = cur;
            matrix A = matrix(2, 0), B = matrix(2, 0);
            A.m[1][1] = 1; A.m[1][2] = 1; 
            B.m[2][1] = 1; B.m[1][2] = 1; B.m[2][2] = 1; 
            int x = qpow(w, i); x = qpow(x, mod - 2);
            up (o, 1, 2) cadd(B.m[o][o], x);
            ll m = n;
            while (m) {
                if (m & 1) A = A * B;
                B = B * B; m >>= 1;
            }
            cmul(sum, A.m[1][1]);
            cadd(ans, sum);
            cmul(cur, r);
        }
        cmul(ans, qpow(k, mod - 2));
        printf("%d\n", ans);
    }
    return 0;
}