【nowcoder_挑战赛31】克洛涅的多项式
https://ac.nowcoder.com/acm/contest/880#question
克洛涅的多项式
题目
链接：https://ac.nowcoder.com/acm/contest/880/B
来源：牛客网
克洛涅修女来到了这所孤儿院。Sister 很快就和大家打成一片，开始了捉迷藏的游戏。 Sister 今天藏起来了一个 n 次的多项式
F(x)。同时，作为线索，她给出了一个 m 次的多项式 G(x) 。这里 m < n 。她又给出了一个有恰好 n 个不同元素的集合 S
。Sister 说，她藏起来的多项式满足两个性质：
- 最高次项系数为 1 。
- 对于所有 S 中的元素 x ，都有 F(x) = G(x) 。即， ∀x∈S,F(x)=G(x) 。 有了这些线索和条件， Sister 藏起来的多项式就可以被唯一确定了。诺曼心中已有了答案。那么，你能不能找得比诺曼更快呢？ 为了方便，你只需要回答将 x=k 代入
Sister 的多项式后的值除以 998244353 后的余数即可。也就是 F(k)mod998244353 的值。
思路
好吧，太菜，不会，直接比赛完后看官方解析了。。
快速读取，官方给了板子：
链接：https://ac.nowcoder.com/acm/contest/880/B
来源：牛客网
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;
【关于c++的快速读取，看到一篇文章可以了解一下 https://www.byvoid.com/zhs/blog/fast-readfile 】
【关于取模优化，可以了解一下 https://blog.csdn.net/gogdizzy/article/details/9014803 】
代码
#include #define MOD 998244353namespace 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;int main() {int m, n, k;read(n);read(m);read(k);// ans = gx+sigamalong long int ans = 0, sigama = 1, gx = 0, x_ = 1;int tmp; for (int i = 0; i < n; i++) {read(tmp);sigama = (sigama*(k-tmp)) % MOD;}for (int i = 1; i <= m+1; i++) {read(tmp);gx = ((x_ * tmp) % MOD + gx) % MOD;x_ = (x_ * k) % MOD;}ans = (gx + sigama) % MOD;if (ans < 0) ans += MOD;printf("%lld\n",ans);
}
运行发现存在偶然性，有时会超时
题目
题目
思路
看了别人解答之后的代码
题目
描述
思路
代码
题目
描述
思路
代码
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！