牛客网OJ题解--20210218
组合数问题
https://ac.nowcoder.com/acm/problem/16429
本系列记录翀翀😐痛苦的刷题日志，所有题目均来自于牛客网OJ题目，坚持刷题谈起来容易做起来难，希望我可以坚持下去，这里仍然分享一段励志文案：每个人都有梦想，然而有些人把梦想变成了现实，有些人的梦想依旧是梦想，只因为他们为梦想付出的努力程度不一样，他们坚持的时间不一样，最终才有这样的结果。
NC16429-组合数问题
题目链接
https://ac.nowcoder.com/acm/problem/16429
题目描述
组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子，从 (1, 2, 3) 三个物品中选择两个物品可以有 (1, 2)，(1, 3)，(2, 3) 这三种选择方法。
根据组合数的定义，我们可以给出计算组合数的一般公式：
小葱想知道如果给定 n，m 和 k，对于所有的 0 ≤ i ≤ n， 0 ≤ j ≤ min(i,m) 有多少对 (i, j) 满足Cij是 k 的倍数。第一行有两个整数 t，k，其中 t 代表该测试点总共有多少组测试数据，k 的意义见 「题目描述」。接下来 t 行每行两个整数 n，m，其中 n，m 的意义见「题目描述」。输出是k行，每一行对应着不同的情况中k的倍数的个数。
测试样例
样例1
输入
1 2 3 3
输出
1
样例2
输入
2 5 4 5 6 7
输出
0 7
解题思路
首先我们使用打表分别计算每一个Cij的情况是否能够整除k，使用如下递推式：
然后使用S[i][j]来表示统计的i,j情况下的所有整除k的个数。我们也可以通过上面的递推式来统计。一定要注意Cij是为了计算对于i=i,j=j时是否整除k,而Sij是为了统计i<=i,j<=j的所有情况中整除k的个数。最终给出任意的n,m我们直接查表即可。
解题代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
//c[i][j]表示的是Cij取余K的余数
int c[N][N];
//s[i][j]表示的是Cij中是k整数倍的个数
int s[N][N];
int main()
{
int t, k;
cin >> t >> k;
//对每种情况的c[i][j]进行预处理检验其模k的余数
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= i; j++)
{
//如果j是0，那么c[i][j]一定是1
if (!j)
c[i][j] = 1 % k;
else
{
//否则按照递推式由前两项的和推得的结果c[i][j]模k记录余数
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
}
//如果刚好c[i][j]是0，那么也就是说此时的Cij情况是k的整数倍
if (!c[i][j])
//那么就增加一种整除k的情况
s[i][j] = 1;
}
}
//整理对于不同的i,j能够整除k的情况个数
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i)
s[i][j] += s[i - 1][j];
if (j)
s[i][j] += s[i][j - 1];
//这里要注意如果i,j都是非零，那么前面的两次累加，多加了一次s[i-1][j-1]，要减去一次
if (i && j)
s[i][j] -= s[i - 1][j - 1];
}
}
while (t--)
{
int n, m;
cin >> n >> m;
//直接输出事先打表出的不同i,j对应的整除k的情况数量即可
cout << s[n][m] << endl;
}
system("pause");
return 0;
} NC16596-计算系数
题目链接
https://ac.nowcoder.com/acm/problem/16596
题目描述
给定一个多项式(ax+by)^k，请求出多项式展开后x^ny^m项的系数。共一行，包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。这个系数可能很大，输出对10007取模后的结果。
测试样例
输入
1 1 3 1 2
输出
3
解题思路
我们首先需要知道二项式定理，可知系数的计算公式为：
所以接下来我们只要计算这个式即可了，并且还要模10007，因为系数会很大。a^n和b^m我们都使用快速幂的方法计算然后模10007，而对于Ckn我们计算完以后在取模10007不现实，因为会很大已经超过了long long int的范围，只能对于每一次的中间结果取模，又因为是相除的形式，不能直接分子分母分别取模再相除，需要对于其进行逆元变形。具体的细节如下：
问题一：快速幂的计算原理
我们假设计算2^5，那么我们常规思路是计算5次2累成即可，但是这太复杂，因此就有了快速幂，使用二进制位权的计算方法：
次数5在计算机中默认就是使用的二进制数101表示的，所以我们只需每一次都取次数的最低位，如果是0就跳过累成，如果是1，那么就累乘位权代码如下：
int qmi(int a, int k)
{
a %= mod;
//ans是结果值
int ans = 1;
//采用的是二进制的计算方法
while (k)
{
//这里k在机器中是二进制表示，与1相与，只有k的最后一位是1才能使得if条件成立
if (k & 1)
//此时ans就乘以一个基数a
ans = ans * a % mod;
//每一次a都要扩大一倍表示下一位的位权
a = a * a % mod;
//k右移一位取最低位
k >>= 1;
}
return ans;
} 其中我们可以通过k&1检验k的最低位是否为1。并且每一次基数a都要扩大一倍来表示下一位的位权，而k每一次也要右移一位。
问题二：为什么要引入逆元？
我们知道对于加减乘除都是可以使用这个取模的定理的：
可以自己验证，但是唯独除法是不允许这样使用的，因为结果会错误，比如
所以我们需要进行一定的转换才可以进行上面分子分母取模再相除。我们先来学习一下逆元，假如(b*c)%k==1，那么c就是b的逆元。所以我们转换一下
并且我们根据费马小定理可以知道对于k如果是质数，且a是正整数，那么a的逆元就是a^(k-2)。所以上式中的c就可以根据已知b求解出来是b^(k-2)。
问题三：求解Ckn取模10007的值
我们根据公式可以知道
我们转换一下上式,将n!每一项转化为逆元：
也就是
所以刚好需要for循环n次即可，所以计算代码如下：
for (int i = 1, j = k; i <= n; i++, j--)
//一共分子和分母只需要计算n次
{
//这里用来计算Ckn
ans = ans * j % mod;
//这里是求n!的逆元，以便能够取模
ans = ans * qmi(i, mod - 2) % mod;
} 这样我们就可以计算出答案了。
解题代码
#include <bits/stdc++.h>
using namespace std;
//好巧，mod还真是素数，可以使用费马定理
#define mod 10007
//快速幂计算a^k
int qmi(int a, int k)
{
a %= mod;
//ans是结果值
int ans = 1;
//采用的是二进制的计算方法
while (k)
{
//这里k在机器中是二进制表示，与1相与，只有k的最后一位是1才能使得if条件成立
if (k & 1)
//此时ans就乘以一个基数a
ans = ans * a % mod;
//每一次a都要扩大一倍表示下一位的位权
a = a * a % mod;
//k右移一位取最低位
k >>= 1;
}
return ans;
}
int main()
{
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
//快速幂计算a^n和b^m
int ans = qmi(a, n) * qmi(b, m) % mod;
for (int i = 1, j = k; i <= n; i++, j--)
//一共分子和分母只需要计算n次
{
//这里用来计算Ckn
ans = ans * j % mod;
//这里是求n!的逆元，以便能够取模
ans = ans * qmi(i, mod - 2) % mod;
}
cout << ans << endl;
system("pause");
return 0;
}