A6381. 「CQOI2015」多项式
编程题
省选/NOI-
知识点
题目描述
在学习完二项式定理后，数学老师给出了一道题目：已知整数 $ n $、$ t $ 和 $ a_k $（$ 0 \leq k \leq n $），求 $ b_k $（$ 0 \leq k \leq n $）的表达式使得
$$ \sum\limits_{k = 0} ^ n a_k x ^ k = \sum\limits_{k = 0} ^ n b_k (x - t) ^ k $$
同学们很快算出了答案。见大家这么快就搞定了，老师便布置了一个更 BT 的作业：计算某个 $ b_m $ 的具体数值！接着便在黑板上写下了 $ n $、$ t $ 的数值，由于 $ a_k $ 实在太多，不能全写在黑板上，老师只给出了一个 $ a_k $ 的递推式，让学生自行计算 $ a_k $：
$$ a_k = \begin{cases} (1234 \cdot a_{k - 1} + 5678) \bmod 3389 & k > 0 \\ 1 & k = 0 \end{cases} $$
$$ \sum\limits_{k = 0} ^ n a_k x ^ k = \sum\limits_{k = 0} ^ n b_k (x - t) ^ k $$
同学们很快算出了答案。见大家这么快就搞定了，老师便布置了一个更 BT 的作业：计算某个 $ b_m $ 的具体数值！接着便在黑板上写下了 $ n $、$ t $ 的数值，由于 $ a_k $ 实在太多，不能全写在黑板上，老师只给出了一个 $ a_k $ 的递推式，让学生自行计算 $ a_k $：
$$ a_k = \begin{cases} (1234 \cdot a_{k - 1} + 5678) \bmod 3389 & k > 0 \\ 1 & k = 0 \end{cases} $$
输入格式
输入文件共三行，第一行为一个正整数 $ n $，第二行为一个非负整数 $t $，第三行为一个非负整数
$ m $。
$ m $。
输出格式
输出一行，为 $ b_m $ 的值。
输入输出样例
输入 #1
3 2 2
输出 #1
10536
说明/提示
对于 $ 100\% $ 的数据，$ 0 < n \leq 10 ^ {3000}, 0 \leq t \leq 10000, 0 \leq n - m \leq 5 $。