A simple Blog for wyx I've been down the bottle hoping.
51nod 傻逼数学题泛做
发表于: | 分类: Oi | 评论:0 | 阅读:245

人傻数学差 然后就找了 51nod 的傻逼数学题水水

有的太水了也有神的,过神的直接弃疗了qwq,做的主要是莫比乌斯和 FFT ,当然也有奇葩数学题

有几个系列题我就直接按系列来了,虽然可能一个系列的没啥联系

序列求和系列

1228 序列求和

题目描述

​ 给定$n,k$, 求 $\sum_{i=1}^n i^k$

题解

伯努利数模板题

$$\sum_{i=0}^k C_{k+1}^i B_i = 0,B_0 = 1$$

​把 $B_k$ 单独作为一项拿出来放到等号那边就有$n^2$的递推式了

​求出伯努利数之后

​$$\sum_{i=1}^n i^k = \frac{1}{k+1} \sum_{i=1}^{k+1} C_{k+1}^i B_{k+1-i}(n+1)^i$$

​然后就没了

 #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2000+10;
const int mod = 1e9+7;
const int Max = 2000+5;
int B[N], fac[N], ifac[N], inv[N];

inline int pow(LL a,LL b) {
    a %= mod;
    LL res = 1;
    for(;b;b>>=1,a=(LL)a*a%mod)
        if(b&1)
            res = res * a % mod;
    return res;
}

inline int C(int n,int m) {
    return (LL)fac[n] * ifac[m] % mod * ifac[n-m]%mod;
}

inline void init() {
    B[0] = 1;
    fac[0] = 1;
    for(int i=1;i<=Max;++i) fac[i] = (LL)fac[i-1] * i % mod;
    inv[1] = 1;
    for(int i=2;i<=Max;++i) inv[i] = mod - (LL)mod/i * inv[mod%i] % mod;
    ifac[Max] = pow(fac[Max],mod-2);
    for(int i=Max-1;~i;--i) ifac[i] = (LL)ifac[i+1] * (i+1) % mod;
    for(int k=1;k<=Max;++k) {
        LL ans = 0;
        for(int i=0;i<=k-1;++i) 
            (ans += (LL)C(k+1,i) * B[i] % mod) %= mod;
        ans = ans * inv[k+1] % mod;
        ans = (ans * (-1) + mod) % mod;
        B[k] = ans;
    }
}

inline void calc(LL n,int k) {
    LL ans = 0;
    int tt = pow(k+1,mod-2);
    for(int i=1;i<=k+1;++i) 
        (ans += (LL)C(k+1,i)*B[k+1-i]%mod*pow((n+1)%mod,i)%mod) %= mod;
    ans = ans * tt % mod;
    cout << ans << endl;
}

LL s[N];

int main() {
    init();
    int T; 
    cin >> T;
    while(T--) {
        LL n, K, r;
        cin >> n >> K;
            n %= mod;
            calc(n,K);
            continue;
    }
}

1229 序列求和 V2

给定$n,k,r$求$\sum_{i=1}^n i^k r^i$

使用扰动法,首先令$S(k) = \sum_{i=1}^n i^k r^i$

$(r-1)S(k) = rS(k) - S(k)$

$ = \sum_{i=1}^{n+1} (i-1)^k r^i - \sum_{i=1}^n i^k r^i$

$ = n^k + r^i + \sum_{i=1}^{n}{r^i(i-1)^k} - \sum_{i=1}^n{r^i i^k}$

$(i-1)^k$二项式定理展开,然后你会惊喜的发现有一项就是$1*i^k$

然后剩下的项恰好是$S(j)$

对于这个范围的话直接$k^2$就好了,如果k再一些存在$k\log^2(k),k\log(k),k$的做法,分别是分治FFT,多项式求逆和线性差值qwq(线性插值我也不会)

    #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2000+10;
const int mod = 1e9+7;
const int Max = 2000+5;
int B[N], fac[N], ifac[N], inv[N];

inline int pow(LL a,LL b) {
    a %= mod;
    LL res = 1;
    for(;b;b>>=1,a=(LL)a*a%mod)
        if(b&1)
            res = res * a % mod;
    return res;
}

inline int C(int n,int m) {
    return (LL)fac[n] * ifac[m] % mod * ifac[n-m]%mod;
}

inline void init() {
    B[0] = 1;
    fac[0] = 1;
    for(int i=1;i<=Max;++i) fac[i] = (LL)fac[i-1] * i % mod;
    inv[1] = 1;
    for(int i=2;i<=Max;++i) inv[i] = mod - (LL)mod/i * inv[mod%i] % mod;
    ifac[Max] = pow(fac[Max],mod-2);
    for(int i=Max-1;~i;--i) ifac[i] = (LL)ifac[i+1] * (i+1) % mod;
    for(int k=1;k<=Max;++k) {
        LL ans = 0;
        for(int i=0;i<=k-1;++i) 
            (ans += (LL)C(k+1,i) * B[i] % mod) %= mod;
        ans = ans * inv[k+1] % mod;
        ans = (ans * (-1) + mod) % mod;
        B[k] = ans;
    }
}

inline void calc(LL n,int k) {
    LL ans = 0;
    int tt = pow(k+1,mod-2);
    for(int i=1;i<=k+1;++i) 
        (ans += (LL)C(k+1,i)*B[k+1-i]%mod*pow((n+1)%mod,i)%mod) %= mod;
    ans = ans * tt % mod;
    cout << ans << endl;
}

LL s[N];

int main() {
    init();
    int T; 
    cin >> T;
    while(T--) {
        LL n, K, r;
        cin >> n >> K >> r;
        if(r == 1) {
            n %= mod;
            calc(n,K);
            continue;
        }
        int tt = pow(r-1,mod-2);
        s[0] = (LL) tt * (pow(r, n+1) - r + mod) % mod;
        for(int k=1;k<=Max;++k) {
            LL ans = 0;
            for(int j=0;j<=k-1;++j) {
                if((k-j)&1) ans = (ans - (LL)s[j] * C(k,j) % mod + mod) % mod;
                else ans = (ans + (LL)s[j] * C(k,j) % mod + mod) % mod;
            }
            ans += (LL)pow(n,k)*pow(r,n+1)%mod;
            ans = ans * tt % mod;
            s[k] = ans;
        }
        cout << s[K] << endl;
    }
}

1236 序列求和 V3

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP