E 莫卡与一元多项式

题目描述

给定如下两个一元多项式：

∑i=0naixi=a0+a1x+a2x2+...+anxn\sum_{i=0}^n a_ix^i = a_0+a_1x+a_2x^2+...+a_nx^n

∑i=0mbixi=b0+b1x+b2x2+...+bmxm\sum_{i=0}^m b_ix^i = b_0+b_1x+b_2x^2+...+b_mx^m

定义如下的二元多项式：

f(x,y)=(∑i=0naixi)(∑i=0mbixi)f(x,y)=(\sum_{i=0}^n a_ix^i)(\sum_{i=0}^m b_ix^i)

你需要处理q次计算，第i次计算给定两个变量值XiX_i 和 YiY_i，你需要求解 f(Xi,Yi) mod 10007f(X_i,Y_i)\bmod10007

题目分析

根据​

ab mod c=(a mod c)(b mod c) mod cab\bmod c = (a\bmod c)(b\bmod c)\bmod c

求解f(Xi,Yi) mod 10007f(X_i,Y_i) \bmod10007时可先求Xi mod 10007X_i\bmod10007和Yi mod 10007Y_i\bmod10007，二者相乘后再对10007取模。

因为XiX_i的值很大，根据

(a+b) mod c=(a mod c+b mod c) mod c(a+b)\bmod c=(a\bmod c+b\bmod c)\bmod c

在求解Xi mod 10007X_i\bmod10007过程中，可对XiX_i每一项进行取模，同理每一项在求解时也需要进行取模，同时为了避免超时需要记录上一项中x乘方的结果，YiY_i同理

示例代码

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
72
#include <stdio.h>
int a[30010];
int b[30010];
int A(int x, int n);
int B(int x, int n);
int ChengFang(int a, int n, int last)
{
    if (n == 0)
    {
        return 1;
    }
    int ans = 1;
    ans = last * a % 10007;
    return ans % 10007;
}
int X[10010];
int Y[10010];
int main()
{
    int n, m;
    scanf("%d", &n);
    for (int i = 0; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    scanf("%d", &m);
    for (int i = 0; i <= m; i++)
    {
        scanf("%d", &b[i]);
    }
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", (A(x, n) * B(y, m)) % 10007);
    }
    return 0;
}
int A(int x, int n)
{
    if (X[x] != 0)
    {
        return X[x];
    }
    int ans = 0;
    int last = 1;
    for (int i = 0; i <= n; i++)
    {
        last = ChengFang(x, i, last);
        ans = ans + (a[i] % 10007 * last) % 10007;
    }
    X[x] = ans % 10007;
    return ans % 10007;
}
int B(int x, int n)
{
    if (Y[x] != 0)
    {
        return Y[x];
    }
    int ans = 0;
    int last = 1;
    for (int i = 0; i <= n; i++)
    {
        last = ChengFang(x, i, last);
        ans = ans + (b[i] % 10007 * last) % 10007;
    }
    Y[x] = ans % 10007;
    return ans % 10007;
}