51nod 1258序列求和

简介: 51nod 1258序列求和

T(n) = n^k,S(n) = T(1) + T(2) + … T(n)。给出n和k,求S(n)。

例如k = 2,n = 5,S(n) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 = 55。

由于结果很大,输出S(n) Mod 1000000007的结果即可。


拉格朗日插值:4.png

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 50000 + 10;
const int N = maxn;
ll fac[maxn], pl[maxn], pr[maxn];
ll qpow(ll a, ll b) {
  ll ans = 1;
  while (b) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans % mod;
}
int main() {
   fac[0] = 1;
  for (int i = 1; i <= N; i++) {
    fac[i] = fac[i - 1] * i % mod;
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    ll n, k, y=0, ans = 0;
    scanf("%lld%lld", &n, &k);
    pl[0] = pr[k + 3] = 1;
    for (int i = 1; i <= k + 2; i++) {
      pl[i] = pl[i - 1] * (n % mod - i + mod) % mod;
    }
    for (int i = k + 2; i >= 1; i--) {
      pr[i] = pr[i + 1] * (n % mod - i + mod) % mod;
    }
    for (int i = 1; i <= k + 2; i++) {
      y = (y + qpow(i, k)) % mod;
      ll a = pl[i - 1] * pr[i + 1] % mod;
      ll b = fac[i - 1] * ((k + 2 - i) & 1 ? -1 : 1) * fac[k + 2 - i];
      b = (b % mod + mod) % mod;
      ans = (ans + y * a % mod * qpow(b, mod - 2) % mod)  % mod;
    }
    printf("%lld\n", ans);
  }
  return 0;
}


4.png

相关文章
|
6月前
|
Python
PTA-第4章-8 求分数序列前N项和
编写程序计算序列 2/1+3/2+5/3+8/5+... 的前N项和,其中每项分子是前一项分子与分母之和,分母是前一项分子。输入一个正整数N,输出部分和,精确到小数点后两位。给定N=20,输出为32.66。以下是代码实现: ```python n = int(input()) sum = 0 a = 2 b = 1 for i in range(1, n + 1): sum += a / b c = a a = a + b b = c print(f&quot;{sum:.2f}&quot;) ```
125 3
|
6月前
PTA-求平方与倒数序列的部分和
求平方与倒数序列的部分和
51 1
|
6月前
|
C++
【PTA】​ L1-009 N个数求和​ (C++)
【PTA】​ L1-009 N个数求和​ (C++)
222 0
【PTA】​ L1-009 N个数求和​ (C++)
|
6月前
PTA-求奇数分之一序列前N项和
求奇数分之一序列前N项和
90 0
|
6月前
【每日一题Day277】LC2569更新数组后处理求和查询 | 线段树
【每日一题Day277】LC2569更新数组后处理求和查询 | 线段树
30 0
51nod 1189 阶乘分数(数论)
51nod 1189 阶乘分数(数论)
57 0
|
人工智能 算法
51nod 1202 子序列个数 (不重复子序列个数)
51nod 1202 子序列个数 (不重复子序列个数)
90 0
51nod 1292 字符串中的最大值 V2 (后缀数组)
51nod 1292 字符串中的最大值 V2 (后缀数组)
57 0
|
机器学习/深度学习 Windows
1228 序列求和 (伯努利数)
1228 序列求和 (伯努利数)
90 0
51nod 1255 字典序最小的子序列 (贪心 + stack)
51nod 1255 字典序最小的子序列 (贪心 + stack)
94 0