密码

## 题目大意 给出一个正整数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; } ```