DLYMOI模拟赛 T1 数列求和题解

shanjb0221 · 2018-10-19 14:01:16 · 题解

算法 1

测试点 1,2 ： N = 10 ^ 6

快速幂即可

算法 2

测试点 3,4 ： k = 0,1

简单数列求和，推出结论即可

算法 3

测试点 5,6 ： k = 2

复杂数列求和，推出结论即可

算法 4

测试点 7,8,9,10 ： k ≤ 2,000

开始推式子：

T_n(k) = b_1 + b_2 + b_3 + \cdots + b_n

即 T_n(k) = 1^ka^1 + 2^ka^2 + 3^ka^3 + \cdots + n^ka^n

又 aT_n(k) = 1^ka^2 + 2^ka^3 + \cdots + (n-1)^ka^n + n^ka^{n+1}

\therefore (a-1)T_n(k) = n^ka^{n+1} - a + \sum_{i=2}^{n} \left( (i-1)^k-i^k \right) a^i

\because (i-1)^k = \sum_{j=0}^{k} \textrm{C}_ {k}^{j} \cdot i^j \cdot (-1)^{k-j}

\therefore (i-1)^k-i^k = \sum_{j=0}^{k-1} \textrm{C}_ {k}^{j} \cdot i^j \cdot (-1)^{k-j}

\therefore \sum_{i=2}^{n} \left( (i-1)^k-i^k \right) a^i = \sum_{i=2}^{n} \left( \sum_{j=0}^{k-1} \textrm{C}_ {k}^{j} \cdot i^j \cdot (-1)^{k-j} \right) a^i

= \sum_{j=0}^{k-1} \textrm{C}_ {k}^{j} \cdot (-1)^{k-j} \left( \sum_{i=2}^{n} i^j \cdot a^i \right)

\because \sum_{i=2}^{n} i^j \cdot a^i = \left( \sum_{i=1}^{n} i^j \cdot a^i \right) -a = T_n(j)-a

\therefore (a-1)T_n(k) = n^ka^{n+1} - a + \sum_{j=0}^{k-1} \textrm{C}_ {k}^{j} \cdot (-1)^{k-j} \left( T_n(j)-a \right)

\therefore T_n(k) = \frac{n^ka^{n+1} - a + \sum_{j=0}^{k-1} \textrm{C}_ {k}^{j} \cdot (-1)^{k-j} \left( T_n(j)-a \right)}{a-1}

注意到 j < k 可以 O(N^2) 递推

特殊地， T_n(0) = a^1 + a^2 + a^3 + \cdots + a^n = \frac{a \left( a^n - 1 \right)}{a-1}

算法 4 代码(std)：

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int M=1e9+7,N=3010;
ll n,a,k,iva,T[N];
ll ans,fac[N],inv[N],inf[N];
inline ll pow(ll a,ll t) {
    ll r=1;
    a%=M;
    while(t) {
        if(t&1)r=r*a%M;
        a=a*a%M,t>>=1;
    }
    return r;
}
inline ll C(int n,int m) {
    return fac[n]*inf[m]%M*inf[n-m]%M;
}
int main() {
    cin>>n>>a>>k;
    fac[0]=inv[1]=inf[0]=1;
    for(int i=2; i<=k; ++i)inv[i]=inv[M%i]*(M-M/i)%M;
    iva=pow(a-1,M-2);
    T[0]=iva*a%M*(pow(a,n)-1)%M;
    for(int i=1; i<=k; ++i) {
        fac[i]=fac[i-1]*i%M,inf[i]=inf[i-1]*inv[i]%M;
        T[i]=pow(n,i)*pow(a,n+1)%M-a;
        for(int j=i-1,_=1; j>=0; --j,_=-_)
            T[i]=(T[i]-C(i,j)*_*(T[j]-a))%M;
        T[i]=(T[i]+M)%M*iva%M;
    }
    cout<<T[k]<<endl;
}

UPD：18.10.27

原来的 std 死了！

注意到当 a=1 时 iva=0 ？！！

虽然现在数据中没有这种情况（可能将来会有？）

应该加个特判：

if(a==1){
    T[0]=n;
    for(int i=1; i<=k; ++i) {
        T[i]=pow(n,i+1)%M;
        for(int j=i-1,_=1; j>=0; --j,_=-_)
        T[i]=(T[i]+C(i+1,j)*_*T[j])%M;
        T[i]=(T[i]+M)%M*inv[i+1]%M;
    }
}

在这里就不再推式子了

新的 std:

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int M=1e9+7,N=3010;
ll n,a,k,iva,T[N];
ll ans,fac[N],inv[N],inf[N];
inline ll pow(ll a,ll t) {
    ll r=1;
    a%=M;
    while(t) {
        if(t&1)r=r*a%M;
        a=a*a%M,t>>=1;
    }
    return r;
}
inline ll C(int n,int m) {
    return fac[n]*inf[m]%M*inf[n-m]%M;
}
int main() {
    cin>>n>>a>>k;
    fac[0]=inv[1]=inf[0]=1;
    for(int i=2; i<=k+1; ++i)inv[i]=inv[M%i]*(M-M/i)%M;
    for(int i=1; i<=k+1; ++i)fac[i]=fac[i-1]*i%M,inf[i]=inf[i-1]*inv[i]%M;
    if(a!=1) {
        iva=pow(a-1,M-2);
        T[0]=iva*a%M*(pow(a,n)-1)%M;
        for(int i=1; i<=k; ++i) {
            T[i]=pow(n,i)*pow(a,n+1)%M-a;
            for(int j=i-1,_=1; j>=0; --j,_=-_)
                T[i]=(T[i]-C(i,j)*_*(T[j]-a))%M;
            T[i]=(T[i]+M)%M*iva%M;
        }
    } else {
        T[0]=n;
        for(int i=1; i<=k; ++i) {
            T[i]=pow(n,i+1)%M;
            for(int j=i-1,_=1; j>=0; --j,_=-_)
                T[i]=(T[i]+C(i+1,j)*_*T[j])%M;
            T[i]=(T[i]+M)%M*inv[i+1]%M;
        }
    }
    cout<<T[k]<<endl;
}

DLYMOI模拟赛 T1 数列求和 题解