【ybt金牌导航8-3-4】【luogu CF622F】K次方求和 / The Sum of the k-th Powers(拉格朗日插值)
K次方求和 / The Sum of the k-th Powers
题目链接:ybt金牌导航8-3-4 / luogu CF622F
题目大意
给你 n,k,要你求 i=1~n 每个 i^k 的和。
思路
首先重新给式子:
∑
i
=
1
n
i
k
\sum\limits_{i=1}^ni^k
i=1∑nik
然后这个东西你设成 f ( n ) f(n) f(n),它其实是一个 k + 1 k+1 k+1 次的多项式。
这里简单的证明一下:
你可以通过差分它得到
i
k
i^k
ik,然后接着每次差分就依次变成:
i
k
−
1
,
i
k
−
2
,
.
.
.
i^{k-1},i^{k-2},...
ik−1,ik−2,...
最后会变成
i
0
=
1
i^0=1
i0=1,即全部都是
1
1
1 的数组。(这个是
0
0
0 次的)
所以反过来就是前缀和,每次次数加一,加到
i
k
i^k
ik 是
k
k
k 次,再前缀就是
k
+
1
k+1
k+1 次了。
然后你就直接用拉格朗日插值,你任意取值就直接取 1 ∼ k + 2 1\sim k+2 1∼k+2 的值,然后用连续的那种搞可以了。
代码
#include<cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
ll n, k, y[1000003], jc[1000003];
ll ans, now, pre[1000003], suf[1000003];
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = re * x % mo;
x = x * x % mo;
y >>= 1;
}
return re;
}
ll work(int k, int n) {
pre[0] = 1;
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] * (k - i + mo) % mo;
suf[n + 1] = 1;
for (int i = n; i >= 1; i--)
suf[i] = suf[i + 1] * (k - i + mo) % mo;
jc[0] = 1;
for (int i = 1; i <= n; i++) jc[i] = jc[i - 1] * i % mo;
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans + y[i] * pre[i - 1] % mo * suf[i + 1] % mo * ksm(jc[i - 1] * jc[n - i] % mo * (((n - i) & 1) ? mo - 1 : 1) % mo, mo - 2) % mo) % mo;
}
return ans;
}
int main() {
scanf("%lld %lld", &n, &k);
for (int i = 1; i <= k + 2; i++) {
now = (now + ksm(i, k)) % mo;
y[i] = now;
}
printf("%lld", work(n, k + 2));
return 0;
}
相关文章
- The Common Order Operations of Dis Operation System (DOSS)
- The Trip PC/UVa IDs: 110103/10137, Popularity: B, Success rate: average Level: 1
- CREATE ASSEMBLY for assembly 'Assembly Name' failed because the assembly is built for an unsupported version of the Common Language Runtime.
- setValue:forUndefinedKey:]: this class is not key value coding-compliant for the key name.
- [Android Studio] Kotlin - Drastically reduce the amount of boilerplate code 2
- [Android Studio] Kotlin - Drastically reduce the amount of boilerplate code
- [Tensorflow] Cookbook - The Tensorflow Way
- [Deep Learning] How deep is the Deep Learning - Revolution
- vscode remote 每次登录时提醒 select the platform of the remote host解决办法
- PHP: POST Content-Length of xxx bytes exceeds the limit of 8388608 bytes【转】
- moviepy音视频剪辑:使用fl_time报错OSError: MoviePy error: failed to read the first frame of video file
- A query was run and no Result Maps were found for the Mapped Statement 'user.insertUser!selectKey'. It's likely that neither a Result Type nor a Result Map was specified.
- 乌龙茶生产过程中挥发性成分吲哚的形成 | Formation of Volatile Tea Constituent Indole During the Oolong Tea Manufacturing Process
- has been blocked by CORS policy: The ‘Access-Control-Allow-Origin‘ header contains multiple values ‘
- 封神台 第六章:GET THE PASS!(进程中抓下管理员明文密码)
- get the text value of a selected option.
- Access restriction: The type JPEGImageEncoder is not accessible due to restriction
- 处理The content of the adapter has changed but ListView did not receive a notification异常
- lightdb异常There is a column named <xxx> in table <xxx>, but it cannot be referenced fromthis part of the query
- leetcode算法:Reshape the Matrix