上海计算机学会2023年8月月赛C++丙组T2下降幂多项式
发布时间
阅读量：
阅读量
题目描述
x 的 k 次下降幂定义为
x 的下降幂多项式是由 x 的一组下降幂及系数组成的算式：
给定下降幂多项式 f(x) 的系数 an,an−1,⋯,a0 与一个值 m，请计算f(m)mod1,000,000,007。
输入格式
- 第一行：两个整数 n 与 m
- 第二行：an,an−1,⋯,a1,a0
输出格式
- 单个整数：表示 f(m)mod1,000,000,007。
数据范围
- 30%30% 的数据，1≤n≤10
- 60%60% 的数据，1≤n≤5,000
- 100%100% 的数据，1≤n≤300,000
- −109≤m≤109
- −109≤ai≤109
样例数据
输入:
3 5
4 3 2 1
输出:
311
说明:
f(x) = 4(x)(x-1)(x-2)+3(x)(x-1)+2(x)+1
f(5) = 4(5)(4)(3)+3(5)(4)+2(5)+1=240+60+10+1
题解
本题关键点：用模拟法并逐步取模。代码如下。
#include <iostream>
using namespace std;
int main() {
int a[300010];
long long ans,p,result;
ans=0;
p=1;
int n,m;
cin>>n>>m;
for (int i=n;i>=0;i--){
cin>>a[i];
}
for (int i=0;i<=n;i++){
ans+=p*a[i];
p*=(m-i);
ans%=1000000007;
p%=1000000007;
}
result=(ans+1000000007)%1000000007;
cout<<result<<endl;
return 0;
}
全部评论 (0)
还没有任何评论哟~