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}

也符合上面的规律。

当 $j = 0$ 或 $j = i$ 时，由 C[n][0] = 1;C[n][n] = 1; 可得命题成立。
否则由 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：

CPP

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

CF2025B Binomial Coefficients, Kind Of 题解

文章操作

CF2025B Binomial Coefficients, Kind Of 题解

思路

相关推荐

评论

CF2025B Binomial Coefficients, Kind Of 题解