列表

详情

NC25113. 181045 / 克洛涅的多项式

描述

克洛涅修女来到了这所孤儿院。Sister 很快就和大家打成一片，开始了捉迷藏的游戏。
Sister 今天藏起来了一个 n 次的多项式 F(x)。同时，作为线索，她给出了一个 m 次的多项式 G(x) 。这里 m < n 。她又给出了一个有恰好 n 个不同元素的集合 S 。Sister 说，她藏起来的多项式满足两个性质：
 1. 最高次项系数为 1 。
 2. 对于所有 S 中的元素 x ，都有 F(x) = G(x) 。即， 。
有了这些线索和条件， Sister 藏起来的多项式就可以被唯一确定了。诺曼心中已有了答案。那么，你能不能找得比诺曼更快呢？
为了方便，你只需要回答将 x=k 代入 Sister 的多项式后的值除以 998244353 后的余数即可。也就是 的值。

由于读入文件较大，请使用较快的读入方式。
这里给出一个 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) 的各项系数。这一行中第  个数字表示 G(x) 中  次项的系数。

输出描述

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

示例1

输入: 

3 2 3
0 1 2
1 1 1

输出: 

19

说明:

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

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 255ms, 内存消耗: 13944K, 提交时间: 2019-05-23 19:45:31 

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE=1e7+10;
const int mod=998244353;
int n,m,k,t;
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;
}
int gi(){
	int x=0,w=1;char ch=gc();
	while((ch<'0'||ch>'9')&&ch!='-')ch=gc();
	if(ch=='-')w=0,ch=gc();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc();
	return w?x:-x;
}
int main(){
	n=gi();m=gi();k=gi();
	int ans=1,x=1;
	for(int i=1;i<=n;++i)
		t=gi(),ans=1ll*ans*(k-t+mod)%mod;
	for(int i=0;i<=m;++i,x=1ll*x*k%mod)
		t=gi(),ans=(ans+1ll*x*t)%mod;
	cout<<ans<<endl;return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 173ms, 内存消耗: 10192K, 提交时间: 2023-07-29 09:45:45 

#include"bits/stdc++.h"
using namespace std;
const int SIZE=1e7+10;
const int mod=998244353;
int n,m,k,t;
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;
}
int gi(){
	int x=0,w=1;char ch=gc();
	while((ch<'0'||ch>'9')&&ch!='-')ch=gc();
	if(ch=='-')w=0,ch=gc();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=gc();
	return w?x:-x;
}
int main(){
	n=gi();m=gi();k=gi();
	int ans=1,x=1;
	for(int i=1;i<=n;++i)
		t=gi(),ans=1ll*ans*(k-t+mod)%mod;
	for(int i=0;i<=m;++i,x=1ll*x*k%mod)
		t=gi(),ans=(ans+1ll*x*t)%mod;
	cout<<ans<<endl;
}

上一题

© 2024 nowcoder.com