DDOSvoid's Blog

Loj 138. 类欧几里得算法

发表于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

简要题意：有 $T$ 组询问，每组询问给出 $n,a,b,c,k_1,k_2$，求 $\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^{k_1}i^{k_2}$​

$T=1000,n,a,b,c\le 10^9,k_1+k_2\le 10$

Solution

考虑万欧，定义三元组 $(x,y,ans[a][b])$​

容易得到转移 $res.ans[a][b]=\sum_{i=0}^a\sum_{j=0}^{b}\binom{a}{i}\binom{b}{j}(u.x)^i(u.y)^jv.ans[a-i][b-j]$，就是直接二项式展开

时间复杂度 $O(k^4\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#define maxn 11
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }

int C[maxn][maxn];
void init_C(int n) {
    for (int i = 0; i <= n; ++i) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}

int k1, k2;
struct node {
    int x, y, ans[11][11];

    node() { x = y = 0; fill(ans[0], ans[0] + 121, 0); }
    inline friend node operator * (const node &u, const node &v) {
        node w; w.x = add(u.x, v.x); w.y = add(u.y, v.y);
        for (int i = 0; i <= k1; ++i)
            for (int j = 0; j <= k2; ++j) w.ans[i][j] = u.ans[i][j];
        for (int i = 0; i <= k1; ++i)
            for (int j = 0; j <= k2; ++j)
                for (int s = 0, x = 1; s <= i; ++s, x = 1ll * x * u.x % p)
                    for (int t = 0, y = 1; t <= j; ++t, y = 1ll * y * u.y % p)
                        w.ans[i][j] = (w.ans[i][j] + 1ll * C[i][s] * C[j][t] % p * x % p * y % p * v.ans[i - s][j - t]) % p;
        return w; 
    }
    friend node pow(node x, int n) {
        node s;
        for (; n; n >>= 1, x = x * x)
            if (n & 1) s = s * x;
        return s;
    }
};
node calc(ll a, ll b, ll c, ll n, const node &A, const node &B) {
    ll m = (a * n + b) / c; 
    if (!m) return pow(B, n);
    if (a >= c) return calc(a % c, b, c, n, A, pow(A, a / c) * B);
    else return pow(B, (c - b - 1) / a) * A * calc(c, (c - b - 1) % a, a, m - 1, B, A) * pow(B, n - (m * c - b - 1) / a);
}

ll n, a, b, c;

void work() {
    cin >> n >> a >> b >> c >> k2 >> k1;
    node A, B, res; A.x = 1; B.y = 1; res.x = b / c;
    for (int i = 0; i <= k2; ++i) B.ans[0][i] = 1;
    for (int i = 0, mul = 1; i <= k1; ++i, mul = 1ll * mul * (b / c) % p) res.ans[i][0] = mul;
    cout << (res * calc(a, b % c, c, n, A, B)).ans[k1][k2] << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; init_C(10);
    while (T--) work(); 
    return 0; 
}