CF 300C - Beautiful Numbers [组合数求模]

本文主要是介绍CF 300C - Beautiful Numbers [组合数求模]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数学是硬伤。

分析题目后知道就是求sigma(C[i,n]%mod)

1 ≤ n ≤ 10⁶

下面有两种方法，

一、预处理出阶乘，直接根据组合数公式 C[i,n] = n!/( i!*(n-i)! )，由于涉及到除法取模，所以要求下逆元。

62ms.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
inline int Rint() { int x; scanf("%d", &x); return x; }
inline int max(int x, int y) { return (x>y)? x: y; }
inline int min(int x, int y) { return (x<y)? x: y; }
#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(x) for(int i=0; i<(x); i++)
typedef long long int64;
#define INF (1<<30)
const double eps = 1e-8;
#define bug(s) cout<<#s<<"="<<s<<" "// a,b,n
// 1 ≤ a < b ≤ 9, 1 ≤ n ≤ 10^6
#define MAXN 1000000
#define MOD 1000000007int a, b;
int64 fact[MAXN+2];int isgood(int x) {for(; x; x/=10) {if(x%10 != a && x%10 != b) {return 0;}}return 1;
}
void calc_fact() {fact[0] = 1;FOR(i, 1, MAXN) {fact[i] = fact[i-1]*i%MOD;}
}void ext_gcd(int64 a, int64 b, int64& d, int64& x, int64& y)
{if(!b) { d = a; x = 1; y = 0; }else { ext_gcd(b, a%b, d, y, x); y-=x*(a/b); }
}int64 inv_mod(int64 a)	// ix=1(mod n)
{int64 x, y, d;ext_gcd(a, MOD, d, x, y);while(x<0) { x+=MOD; }return x;
}int64 C(int k, int n) {return fact[n]*inv_mod(fact[k]*fact[n-k])%MOD;
}int main() {a = Rint();b = Rint();int n = Rint();calc_fact();int64 ans = 0;FOR(i, 0, n) {if(isgood(a*i+b*(n-i))) {ans = (ans + C(i,n))%MOD;}}printf("%lld\n", ans);
}

二、根据递推公式 c[i]=c[i-1]*(n-i+1)/i ，先递推出所有C[n, i]，因为这题n不会变，所以可以这样。同样要为 i 求逆元。

531ms

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
inline int Rint() { int x; scanf("%d", &x); return x; }
inline int max(int x, int y) { return (x>y)? x: y; }
inline int min(int x, int y) { return (x<y)? x: y; }
#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(x) for(int i=0; i<(x); i++)
typedef long long int64;
#define INF (1<<30)
const double eps = 1e-8;
#define bug(s) cout<<#s<<"="<<s<<" "// a,b,n
// 1 ≤ a < b ≤ 9, 1 ≤ n ≤ 10^6
#define MAXN 1000000
#define MOD 1000000007int a, b;int isgood(int x) {for(; x; x/=10) {if(x%10 != a && x%10 != b) {return 0;}}return 1;
}void ext_gcd(int64 a, int64 b, int64& d, int64& x, int64& y)
{if(!b) { d = a; x = 1; y = 0; }else { ext_gcd(b, a%b, d, y, x); y-=x*(a/b); }
}int64 inv_mod(int64 a)	// ix=1(mod n)
{int64 x, y, d;ext_gcd(a, MOD, d, x, y);while(x<0) { x+=MOD; }return x;
}// int64 C(int k, int n) {
// 	return fact[n]*inv_mod(fact[k]*fact[n-k])%MOD;
// }// #define MAXN 10000002
int64 c[MAXN+2];int64 C(int64 n, int64 k)		//C n k			
{c[0] = 1;for(int64 i=1; i<=k; i++){c[i] = c[i-1]*(n-i+1)%MOD*inv_mod(i) % MOD;}return c[k];
}int main() {a = Rint();b = Rint();int n = Rint();// calc_fact();C(n, n);int64 ans = 0;FOR(i, 0, n) {if(isgood(a*i+b*(n-i))) {ans = (ans + c[i])%MOD;}}printf("%lld\n", ans);
}

另，感觉我的求逆元的代码是不是挫了点，好像以前写组合数学的题跑的时间都比别人久。。

数学推理现在完全记不起来了。。还有什么Lucas也不会。。T-T

这篇关于CF 300C - Beautiful Numbers [组合数求模]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---