[HDU6467] 简单数学题

前言

多写写数学题的题解，说不定就会了呢qwq

题目

HDU

讲解

就单纯推式子

首先我们要先证明一个性质：

[sum_{i=0}^n i*C_n^i=n*2^{n-1} ]

令

[S=sum_{i=0}^n i*C_n^i ]

则

[egin{aligned} 2S&=sum_{i=0}^n i*C_n^i+sum_{i=0}^n (n-i)*C_n^{n-i}\ &=sum_{i=0}^n i*C_n^i+sum_{i=0}^n (n-i)*C_n^i\ &=sum_{i=0}^n n*C_n^i\ &=n*sum_{i=0}^n C_n^i\ &=n*2^n end{aligned}]

所以

[S=n*2^{n-1} ]

然后我们就可以愉快地推式子啦

[egin{aligned} F(n)&=sum_{i=1}^n i*sum_{j=i}^n C_{j}^{i}\ &=sum_{i=1}^n sum_{j=1}^i j*C_i^j\ &=sum_{i=1}^n i*2^{i-1}\ &=sum_{i=0}^{n-1} (i+1)*2^{i} end{aligned}]

类似的，我们求出(2F(n))

[2F(n)=sum_{i=1}^n i*2^i ]

作差即可得到：

[egin{aligned} F(n)&=n*2^n-sum_{i=0}^{n-1}2^i\ &=n*2^n-(2^n-1)\ &=(n-1)*2^n+1 end{aligned}]

快速幂实现即可

代码

int qpow(LL x,LL y,int MOD)
{
	LL ret = 1;y %= (MOD-1);
	while(y){if(y & 1) ret = ret * x % MOD;x = x * x % MOD;y >>= 1;}
	return ret;
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(~scanf("%lld",&n)) Put(((n-1) % MOD * qpow(2,n,MOD) + 1) % MOD,'
');
	return 0;
}