【第36题】重要：阅读神犇的代码是种享受之 [NOIP2011 提高组] 计算系数

发布于

碎碎念

  • 2分钟根据二次项定理推出了公式，然后花1个小时写代码…………………………o(╥﹏╥)o
  • 作业：学习逆元

题目：[NOIP2011 提高组] 计算系数

题目原文请移步下面的链接

  • https://www.luogu.com.cn/problem/P1313
    • 参考题解：https://www.luogu.com.cn/problem/solution/P1313
  • 标签：OI、 NOIP、数学
  • 难度：普及/提高-

30分

思路
  • 利用组合数的定义式,但是因为有取余, 所以要用逆元，而由于本人并不了解逆元，所以精度应该是被卡爆后华丽丽的WA了. 推导公式如下。
C_n^m

=

\frac {n! mod 10007} {m!(n-m)! mod 10007}

=

n!×[m!(n−m)!]^{−1}

mod

10007
代码
代码语言：javascript
复制
#include <bits/stdc++.h>
using namespace std;
#define endl '\n';

const int mod = 10007;


void best_coder() {

int a, b, k, n, m;

cin >> a >> b >> k >> n >> m;

int t = min(n, m);

long long ans = 1;

for (int i = 0; i < t; ++i) {

ans *= k - i;

ans /= i + 1;

ans %= mod;

}

for (int i = 0; i < n; ++i) {

ans *= a;

ans %= mod;

}

for (int i = 0; i < m; ++i) {

ans *= b;

ans %= mod;

}

cout << ans;

}


void happy_coder() {


}


int main() {

// 提升cin、cout效率

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);


// 小码匠
best_coder();

// 最优解
// happy_coder();

// 返回
return 0;



}

30分

思路
  • 扫了遍题解，猛然想起组合式有个递推公式可以算组合数，然而由于递归耗费了大量时间，所以不开快速幂是铁定过不了的，当然k最大为1000，所以索引数组下标开小后就RE了，并且最后答案还少了次取模，因此在出题人良心大发下拿了30分
C_n^m=C_{n−1}^m+C_{n−1}^{m−1}
代码
代码语言：javascript
复制
#include <bits/stdc++.h>

using namespace std;

#define endl '\n';


const int mod = 10007;

int c[1000][1000];


int number (int k, int t) {

if (t == 0 || k == t) {

c[k][t] = 1;

return c[k][t];

}

if (t == 1) {

c[k][t] = k;

return c[k][t];

}

c[k][t] = number(k - 1, t) % mod + number(k - 1, t - 1) % mod;

return c[k][t];

}


void best_coder() {

int a, b, k, n, m;

cin >> a >> b >> k >> n >> m;

int t = min(n, m);

long long ans;

ans = number(k, t);

for (int i = 0; i < n; ++i) {

ans *= a;

ans %= mod;

}

for (int i = 0; i < m; ++i) {

ans *= b;

ans %= mod;

}

cout << ans;

}


void happy_coder() {


}


int main() {

// 提升cin、cout效率

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);


// 小码匠
best_coder();

// 最优解
// happy_coder();

// 返回
return 0;



}

100分

思路

较上一版代码更正了错误，这里有个点需要注意，a和b的初始值可能大于mod所以要先取余（不过有没有影响本人也没测试过，反正取余了铁定没问题就是了）

代码
代码语言：javascript
复制
#include <bits/stdc++.h>


using namespace std;

#define endl '\n';


const int mod = 10007;

int c[1010][1010];


int quick_pow(int x, int y) {

int ans = 1, t = x;

while (y) {

t %= mod;

if (y % 2 == 1) {

ans *= t % mod;

ans %= mod;

}

t = (t * t) % mod;

y >>= 1;

}

return ans % mod;

}


int number(int k, int t) {

if (t == 0 || k == t) {

c[k][t] = 1;

return c[k][t];

}

if (t == 1) {

c[k][t] = k;

return c[k][t];

}

if (c[k][t] != 0) {

return c[k][t];

}

c[k][t] = (number(k - 1, t) + number(k - 1, t - 1)) % mod;

return c[k][t];

}


void best_coder() {

int a, b, k, n, m;

cin >> a >> b >> k >> n >> m;

int t = min(n, m);

long long ans = 1;

c[1][0] = 1;

c[1][1] = 1;

a %= mod;

b %= mod;

ans *= quick_pow(a, n) % mod;

ans *= quick_pow(b, m) % mod;

ans *= number(k, t);

cout << ans % mod;

}


void happy_coder() {


}


int main() {

// 提升cin、cout效率

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);


// 小码匠
best_coder();

// 最优解
// happy_coder();

// 返回
return 0;



}

100分

思路
  • 这是别的神犇的代码，在本蒟蒻心（非）平（常）气（抓）和（狂）的研究了这份代码后简单说下
    • 这位神犇他是干脆将a和b直接揉到了系数的计算过程中，同时用了（大概可能应该）dp思想???用上述提到的公式推了系数出来
代码
代码语言：javascript
复制
#include <bits/stdc++.h>


using namespace std;

#define endl '\n';


const int mod = 10007;

int c[1010][1010];


void happy_coder() {

long long a, b, k, n, m;

cin >> a >> b >> k >> n >> m;

c[1][1] = 1;

for (int i = 2; i <= k + 1; i++) {

for (int j = 1; j <= i; j++) {

c[i][j] = (c[i - 1][j - 1] * b + c[i - 1][j] * a) % 10007;

}

}

cout << c[k + 1][m + 1];

}


int main() {

// 提升cin、cout效率

ios::sync_with_stdio(false);

cin.tie(nullptr);

cout.tie(nullptr);


// 小码匠
//best_coder();

// 最优解
happy_coder();

// 返回
return 0;



}

END

#cin#cout#int#return#效率