Google Kickstart Round C 2018 Problem C. Kickstart Alarm

Problem C. Kickstart Alarm

题目传送门：
https://code.google.com/codejam/contest/4384486/dashboard#s=p2

题目理解有点麻烦，经过一些思考可以得到：
ans[i] = a[i] * (n-i) * (1 ~ i+1的等比数列之和）， 0 <= i < n

其中ans[i]表示所有与a[i]有关的项的和。
举个栗子，
n=3，k=2，a={1,4,2}
现在来计算ans[1]，也就是’4’相关的项
含有’4’的子序列有：
[4] : 4∗11+4∗12 $4\ast 1^1+4\ast 1^2$
[4,2] : 4∗11+4∗12 $4\ast 1^1+4\ast 1^2$
[1,4] : 4∗21+4∗22 $4\ast 2^1+4\ast 2^2$
[1,4,2] : 4∗21+4∗22 $4\ast 2^1+4\ast 2^2$

我们可以看到[4]和[4,2]重复了，[1,4]和[1,4,2]也重复了，这就是之前式子中的(n-i)这一项。提取出公因子后，剩下的部分为：

11+12+...+1k+21+22+...+2k+...+(i+1)1+(i+1)2+...+(i+1)k $$1^1+1^2+...+1^k+2^1+2^2+...+2^k+...+(i+1{)}^1+(i+1{)}^2+...+(i+1{)}^k$$

，也就是之前式子中的“等比数列之和”那一项。

那么问题就转换为了如何快速求等比数列之和。

遗憾的是，因为要mod 1000000007，所以等比数列求和公式没办法使用，而一项一项计算又要O(N*K)的时间，会超时（我的电脑上跑大数据要四十分钟）。

需要用到类似快速幂的思想：
例如求 T=2^1+2^2+2^3+2^4+2^5+2^6+2^7 …….
共有n项
这时的公式就为
若n%2==0 T(n)=T(n/2)+T(n/2)*2^(n/2);
若n%2==1 T(n)=T(n/2)+T(n/2)*2^(n/2)+ 2^n;

其中2^(n/2) 和 2^n需要用快速幂来计算。

参考代码：

const int MOD=1000000007;
int powll(int base,int n){
    if (n==0) return 1;
    if (n==1) return base;
    long long tmp=powll(base,n/2);
    tmp=(tmp*tmp)%MOD;
    if (n%2==1) tmp=(tmp*base)%MOD;
    return int(tmp);
}
int geoSum(int base,int n){
    if (n==1) return base;
    long long tmp=geoSum(base,n/2);
    tmp=(tmp+tmp*powll(base,n/2))%MOD;
    if (n%2==1) tmp=(tmp+powll(base,n))%MOD;
    return int(tmp);
}

int main() {
    int no;
    cin>>no;
    for (int tt=1;tt<=no;tt++){
        long long n,k,x1,y1,c,d,e1,e2,f;
        cin>>n>>k;
        vector<long long> x(n),y(n);
        cin>>x[0]>>y[0]>>c>>d>>e1>>e2>>f;

        vector<long long> a(n);
        a[0]=(x[0]+y[0])%f;
        for (int i=1;i<n;i++) {
            x[i] = (c * x[i - 1] + d * y[i - 1] + e1) % f;
            y[i] = (d * x[i - 1] + c * y[i - 1] + e2) % f;
            a[i]=(x[i]+y[i])%f;
        }

        vector<long long> sum(n);
        sum[0]=geoSum(1,k);
        for (int i=1;i<n;i++) {
            sum[i]=(sum[i-1]+geoSum(i+1,k))%MOD;
        }

        long long ans=0;
        for (int i=0;i<n;i++){
            ans=(ans+(((n-i)*a[i])%MOD)*sum[i])%MOD;
        }

        cout<<"Case #"<<tt<<": "<<ans<<endl;
    }

    return 0;
}