簡單數學（組合數+求數列通項公式）

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=6467

看到這題，簡單數學？？？對不起我給數學老師丟臉了！

這裡解釋一下第二步到第三步：假設n=3，第二步{1*C（1，1）+1*C（1，2）+1*C（1，3）+2*C（2，2）+2*C（2，3）+3*C（3，3）}，第三步{1*C(1,1)+1*C(1,2)+2*C(2,2)+1*C(1,3)+2*C(2,3)+3*C(3,3)}。可以發現是相等的

之後最後一步就是組合數求和公式2^n。

之後便可以得到遞推公式。但是直接用遞推公式寫還是會超時的，所以要進一步化簡成通項公式。

n*(2^(n-1))=2(n-1)*(2^(n-1))-(n-2)*(2^(n-1))

之後根據這個將其分配

F(n)-(n-1)*2^n=F(n-1)-(n-2)*(2^(n-1))

很明顯就有等比數列：(F(n)-(n-1)*2^n)/(F(n-1)-(n-2)*(2^(n-1)))=1

並且這個等比數列的公比就是1

而F(1)=1,所以第一項值為1

所以很明顯這個等比數列恆為1

所以F(n)-(n-1)*2^n=1 --->F(n)=(n-1)*(2^n)+1

既然有了通項公式，AC什麼的都太簡單了。

#include <bits/stdc++.h>
using namespace std;
#define re register
#define ll long long
const ll mod=1e9+7;
void read(int &a)
{
    a=0;
    int d=1;
    char ch;
    while(ch=getchar(),ch<'0'||ch>'9')
        if(ch=='-')
            d=-1;
    a=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')
        a=a*10+ch-'0';
    a*=d;
}
void write(int x)
{
    if(x<0)
        putchar(45),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}
ll quickmod(ll x,ll y)
{
    ll res=1;
    ll base=x;
    while(y)
    {
        if(y&1)
            res=res*base%mod;
        base=base*base%mod;
        y>>=1;
    }
    return res;
}
int main()
{
    ll n;
    while(~scanf("%lld",&n))
    {
        ll ans=((((n-1)%mod*quickmod(2,n))%mod)+1)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}