【2021牛客寒假第六场】F-组合数问题 二项式定理

传送门：https://ac.nowcoder.com/acm/contest/9986/F 这一题其实很难的，不过过了那么多人就离谱，估计大部分都是OEIS的吧。

题意

$$输出C_n^0+C_n^4+C_n^8+…+C_n^n\;\;(4｜n)$$

思路

$我们知道$ $(1+1)^n=C_n^0+C_n^1+…+C_n^n=2^n$ $(1-1)^n=C_n^0-C_n^1+…+C_n^n=0$

$两式相加除2得：$ $2^{n-1}=C_n^0+C_n^2+…+C_n^n$

$这是2的倍数，但是题目要求的是4的倍数，那该怎么办呢？$ $我们可不可以通过上面的方法凑出来呢？答案是可以的，考虑虚数i。$

$把其中一个1换成i之后，我们在二项式展开看看：$ $(1+i)^n=C_n^0+iC_{n}^1-C_n^2-…+C_n^n$ $(1-i)^n=C_n^0-iC_n^1-C_n^2-….+C_n^n$

$两式相加除2得$ $(1+i)^n+(1-i)^n=C_n^0-C_n^2+C_n^4-…+C_n^n$

$而虚数我们知道，在次幂的情况下都是有循环节的，比如这里就是4个一循环.$

$所以(1+i)^4=(1-i)^4=-4$ $所以(1+i)^{4n}=(-4)^{n}$

$即(-4)^{\frac{n}{4}}=C_n^0-C_n^2+C_n^4-…+C_n^n$

$结合两式相加除2即可得：$

$2^{n-2}+\frac{1}{2}(-4)^{\frac{n}{4}}=C_n^0+C_n^4+C_n^8+…+C_n^n$

Code

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
##include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;

##define endl "\n"
##define eb emplace_back
##define mem(a, b) memset(a , b , sizeof(a))

const ll INF = 0x3f3f3f3f;
const ll mod = 998244353;
// const ll mod = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
const double R = 0.57721566490153286060651209;

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;
}

const int N = 1e5 + 10;

void solve() {
    ll n; cin >> n;
    cout << (((quick_pow(2, n - 2) % mod + quick_pow(-4, n / 4) * quick_pow(2, mod - 2) % mod) % mod + mod) % mod) << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/24/2021-nowcoder-hanjia-6-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！