密码

2019-02-24 15:21:01


题目大意

给出一个正整数n(n<=1e9),求$\sum^{n}_{i=1}i^2*2^i$,结果mod=1e9+7

解法

显然这道题O(n)是过不了的,那么显然需要推导结论

设$S_n=1*2+4*2^2+9*2^3+......+n^2*2^n$

则$2S_n=1*2^2+4*2^3+9*2^4+......+n^2*2^{n+1}$

相减整理可得到$S_n=n^2*2^{n+1}-(1*2+3*2^2+5*2^3+........(2n-1)*2^n)$

再设$T_n=(1*2+3*2^2+5*2^3+........(2n-1)*2^n)$

同理乘二再相减$T_n=(2n-3)*2^{n+1}+6$

回到原式得$S_n=(n^2-2n+3)*2^{n+1}-6$

快速幂处理即可

#include<cstdio>
#include<cstring>
#include<iostream> 
#include<algorithm>
#define int long long
using namespace std;
const int mod=1000000007;
int n;
int pow(int x,int k)
{
    int ans=1;
    while(k)
    {
        if(k&1) ans=ans*x%mod;
        x=x*x%mod;
        k/=2;
    }
    return ans%mod;
}
signed main()
{
//  freopen("password.in","r",stdin);
//  freopen("password.out","w",stdout);
    scanf("%lld",&n);
    printf("%lld",((pow(2,n+1)*(((n*n%mod-2*n%mod+3)+mod)%mod)-6)+mod)%mod);
    return 0;
}