CF2025B Binomial Coefficients, Kind Of 题解

· · 题解

CF2025B Binomial Coefficients, Kind Of 题解

题目传送门

思路

考虑打表找规律：

n/k 0 1 2 3 4
0 1
1 1 1
2 1 2 1
3 1 2 4 1
4 1 2 4 8 1

容易发现，当 n = k 或 k = 0 时，C_{n,k} = 1。否则 C_{n,k} = 2^k。再观察数据范围，1 \le k_i < n，就不需要考虑前面的情况了。

可以用数学归纳法证明。读者自证不难。

已知 C_{0,0} 到 C_{i,j-1} 的每一项都符合上面的规律，要证 C_{i,j} 也符合上面的规律。

  1. 当 j = 0 或 j = i 时，由 C[n][0] = 1;C[n][n] = 1; 可得命题成立。
  2. 否则由 C[n][k] = C[n][k - 1] + C[n - 1][k - 1]; 可以得出，C_{i,j} = C_{i-1,j-1} + C_{i,j-1} = 2^{j-1} + 2^{j-1} = 2^j，即命题对 C_{i,j} 成立。

所以命题成立。

Code：

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int T,k;
long long Pow[100005];
void init()
{
    Pow[0] = 1;
    for(int i = 1;i < 100000;i++) Pow[i] = (Pow[i-1] << 1)%mod;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    init();
    for(int i = 1;i <= T;i++) cin >> k;
    for(int i = 1;i <= T;i++)
    {
        cin >> k;
        cout << Pow[k] << "\n";
    }
    return 0;
}