【nowcoder_挑战赛31】克洛涅的多项式（构造）

链接：https://ac.nowcoder.com/acm/contest/880/B
来源：牛客网
 

题目描述 

克洛涅修女来到了这所孤儿院。Sister 很快就和大家打成一片，开始了捉迷藏的游戏。

Sister 今天藏起来了一个 n 次的多项式 F(x)。同时，作为线索，她给出了一个 m 次的多项式 G(x) 。这里 m < n 。她又给出了一个有恰好 n 个不同元素的集合 S 。Sister 说，她藏起来的多项式满足两个性质：

 1. 最高次项系数为 1 。

 2. 对于所有 S 中的元素 x ，都有 F(x) = G(x) 。即，∀x∈S,F(x)=G(x)∀x∈S,F(x)=G(x) 。

有了这些线索和条件， Sister 藏起来的多项式就可以被唯一确定了。诺曼心中已有了答案。那么，你能不能找得比诺曼更快呢？

为了方便，你只需要回答将 x=k 代入 Sister 的多项式后的值除以 998244353 后的余数即可。也就是 F(k)mod998244353F(k)mod998244353 的值。

由于读入文件较大，请使用较快的读入方式。

这里给出一个 C++ 的快速读入板子：

namespace io {
    const int SIZE = 1e7 + 10;
    char inbuff[SIZE];
    char *l, *r;
    inline void init() {
        l = inbuff;
        r = inbuff + fread(inbuff, 1, SIZE, stdin);
    }
    inline char gc() {
        if (l == r) init();
        return (l != r) ? *(l++) : EOF;
    }
    void read(int &x) {
        x = 0; char ch = gc();
        while(!isdigit(ch)) ch = gc();
        while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
    }
} using io::read;

在主程序中 read(x); 即可。

输入描述:

输入的第一行包含三个整数 n, m, k ，意义如题面所述。
第二行包含 n 个整数，表示所给出集合中的元素。保证集合中元素互不相同。
第三行包含 m+1 个整数，表示所给多项式 G(x) 的各项系数。这一行中第 i(1≤i≤m+1)i(1≤i≤m+1) 个数字表示 G(x) 中 xi−1xi−1 次项的系数。

输出描述:

输出仅一行，一个整数表示 F(k) 的值在模 998244353 意义下的结果。

示例1

输入

复制

3 2 3
0 1 2
1 1 1

输出

复制

19

说明

Sister 给出的多项式 G(x) 为 x2+x+1x2+x+1 。集合 S 为 {0, 1, 2} ，故 F(0) = G(0) = 1, F(1) = G(1) = 3, F(2) = G(2) = 7 。所以 F(x) 为 x3−2x2+3x+1x3−2x2+3x+1 。答案为F(3) = 19 。

备注:

0

0≤k<9982443530≤k<998244353

0≤0≤ 多项式系数、S 中元素 <998244353

思路：

不想多说。。。不看题解死活不会，看了又秒懂，我真是佛了。。。多做题、多练吧。

#include 
#define maxn 5000010
#define ll long long
#define mod 998244353
using namespace std;namespace io {const ll SIZE = 1e7 + 10;char inbuff[SIZE];char *l, *r;inline void init() {l = inbuff;r = inbuff + fread(inbuff, 1, SIZE, stdin);}inline char gc() {if (l == r) init();return (l != r) ? *(l++) : EOF;}void read(ll &x) {x = 0; char ch = gc();while(!isdigit(ch)) ch = gc();while(isdigit(ch)) x = x * 10 + ch - '0', ch = gc();}
} using io::read;ll s[maxn],a[maxn];
int main(){ll n,m,k;read(n);read(m);read(k);//cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！