HDU 6467 简单数学题 广东工业大学第十四届程序设计竞赛

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=6467

题意

$$求F(n)=\sum_{i=1}^n(i*\sum_{j=i}^nC_j^i)\;\;mod \;\;(1e9+7)$$

思路

先将F(n)展开： $$F(n)=1*\sum_{j=1}^nC_j^1+2*\sum_{j=2}^nC_j^2+…+(n-1)\sum_{j=n-1}^nC_j^{n-1}+n\sum_{j=n}^nC_j^n$$ 将F(n-1)展开： $$F(n)=1*\sum_{j=1}^{n-1}C_j^1+2*\sum_{j=2}^{n-1}C_j^2+…+(n-1)\sum_{j=n-1}^{n-1}C_j^{n-1}$$

上式减下式得：

$F(n)-F(n-1)=$ $$C_n^1+2*C_n^2+…+(n-1)C_{n}^{n-1}+nC_{n}^n$$

$$n*C_{n-1}^0+n*C_{n-1}^1+…+n*C_{n-1}^{n-1}$$

这里可能有点看不清楚，比如$rC_n^r=r*\frac{n!}{r!*(n-r)!}$，拿出一个n，消去一个r得$n*\frac{(n-1)!}{(r-1)!(n-r)!}=n*C_{n-1}^{r-1}$。

由二项式定理得：

$$F(n)-F(n-1)=n*2^{n-1}$$

即得到如下式子：

$$ F(n) = 1 \; (n = 1) \; \; \; F(n) = F(n - 1) + n * 2^{n-1} \; (n > 1) $$

上式明显是一个递推公式，所以F(n)是一个差比数列的前n项和，错位相减法即可。

有一个差比数列的公式，高中还记得，现在就不记得。。。

对于数列$(An+B)q^{n-1}，(1-q)S_n=(A+B)+(\frac{A}{1-q})q-(An+B+\frac{A}{1-q})q^n$。

最后得出F(n)=(n-1)*2^{n}+1，快速幂处理一下即可。

Code（405MS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll quick_pow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) {
            ans = ans * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return ans % mod;
}

int main() {
    ll n;
    while(scanf("%lld",&n) != EOF) {
        printf("%lld\n",(1 + (n - 1) % mod * quick_pow(2, n) % mod + mod) % mod);
    }
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/10/15/hdu-6467/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！