NC14618. 多项式求值
描述
输入描述
多组读入。
每组的第一行，表示多项式f(x)
接下来是一个整数n，接着一行有n个整数x，你需要求值f(x) mod 1000000007
组数不超过100，x在int表示的范围内，f(x)所有项的系数和指数都在int表示的范围内(指数保证非负)。
输出描述
对于每一个，在单独的一行中输出一个整数。
示例1
输入:
3x^2+6x+10-3x 4 0 1 2 3
输出:
10 16 28 46
C++14(g++5.4) 解法, 执行用时: 400ms, 内存消耗: 1516K, 提交时间: 2020-06-16 15:22:47
#include<cstring>
#include<cstdio>
const int mod=1e9+7;
int T,Q,n,A[10005],B[10005];
char s[1000000];
inline int power(int a,int b)
{
int re=1;
for(;b;b>>=1,a=(long long)a*a%mod)
if(b&1)
re=(long long)re*a%mod;
return re;
}
inline void Init()
{
n=0;
int f=1,t=0,x[2]={0,0},y[2]={0,0},len=strlen(s);
s[len++]='+';
for(int i=0;i<len;i++)
{
if(s[i]=='-'||s[i]=='+')
{
if(t==1&&!y[0])
x[0]=1;
if(t==1&&!y[1])
x[1]=1;
A[++n]=(f*x[0]%mod+mod)%mod;
B[n]=x[1];
f=s[i]=='+'?1:-1;
t=x[0]=x[1]=y[0]=y[1]=0;
}
else if(s[i]=='x')
t=1;
else if(s[i]>='0'&&s[i]<='9')
x[t]=x[t]*10+s[i]-'0',y[t]=1;
}
}
int main()
{
while(scanf("%s",s)!=EOF)
{
Init();
for(scanf("%d",&Q);Q;Q--)
{
int ans=0,x;
scanf("%d",&x);
x=(x%mod+mod)%mod;
for(int i=1;i<=n;i++)
ans=((long long)A[i]*power(x,B[i])%mod+ans)%mod;
printf("%d\n",ans);
}
}
}
C++11(clang++ 3.9) 解法, 执行用时: 514ms, 内存消耗: 1372K, 提交时间: 2019-02-01 18:32:51
#include<iostream>
#include<cstdio>
char S[500000],*_;
int n,x;
const int P=1000000007;
int fast_pow(int a,int b){
int ret=1;
for (b<<=1;b>>=1;a=a*static_cast<long long>(a)%P) if (b&1) ret=ret*static_cast<long long>(a)%P;
return ret;
}
int eatint(){
if (*_!='+'&&*_!='-'&&!isdigit(*_)) return 1;
int flag=1,ret=0;
if (*_=='+') flag=1,_++;
else if (*_=='-') flag=-1,_++;
if (!isdigit(*_)) ret=1;
else while (isdigit(*_)) ret=(ret<<1)+(ret<<3)+(*_++&15);
return flag*ret;
}
int eatnxt(){
if (*_!='x') return 0;
_++;
if (*_!='^') return 1;
_++;
return eatint();
}
int ans;
int main(){
while (~scanf("%s",S)){
scanf("%d",&n);
while (n--){
scanf("%d",&x);
_=S;
ans=0;
while (*_){
int A=eatint();
int B=eatnxt();
ans=(ans+A*static_cast<long long>(fast_pow(x,B))%P+P)%P;
}
printf("%d\n",ans);
}
}
}