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)~~：
```cpp
#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 $ ？！！
虽然现在数据中没有这种情况（可能将来会有？）
应该加个特判：
```cpp
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:
```cpp
#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;
}
```