C1-C

题目要求

给定两个一元多项式的系数，给出计算次数，每次计算给定两个多项式的变量的值，求出每次两个一元多项式的乘积mod 10007的结果。

核心算法和原理

• 处理一元多项式的算法：霍纳(Horner)规则：给定系数a0…an，定义f(i)：
则一元多项式的结果为F(n)
Psudocode:

ans = 0
for n down to 0
	ans = a[n] + ans * x

时间复杂度Θ(n)

• 数论知识：a ≡ a’(mod n), b ≡ b’(mod n)，则 a + b ≡ a’ + b’ (mod n), ab ≡ a’b’ (mod n)
这么做的意义是避免在计算多项式的过程中数据太大溢出去（毕竟最后也要取模）
则每一步都取模（有些不取也可以，反正都等价类）即可

代码

#include <bits/stdc++.h>
using namespace std;
unsigned long long arr1[30001];
unsigned long long arr2[30001];

int main(){
    int n, m, q;
    unsigned long long x, y;
    unsigned long long ans1 = 0;
	unsigned long long ans2 = 0;
    cin >> n;
    for(int i = 0; i <= n; i++){
        cin >> arr1[i];
    }

    cin >> m;
    for(int i = 0; i <= m; i++){
        cin >> arr2[i];
    }
	
	cin >> q;
    while(q--){
        ans1 = ans2 = 0ULL;
        cin >> x >> y;
        for(int i = n; i >= 0; i--){
            ans1 = arr1[i] + (x * ans1) % 10007ULL;
            //Horner method：f0 = an, fi = an-i + x * fi-1, ans = fn
						//arr1[i]不用取模：因为数据输入点保证系数小于10007
						//ans1每一步取一下模更保险，但是试验证明越不了界
        }
        ans1 %= 10007ULL;
        for(int i = m; i >= 0; i--){
            ans2 = arr2[i] + (y * ans2) % 10007ULL;
        }
        ans2 %= 10007ULL;
        printf("%llu\n", (ans1 * ans2) % 10007ULL);
    }
    return 0;
}