有毒。。。谁想得到要这样做。。。
题意
一个字符串只由0,1组成,且0有m个,1有n个,要求该字符串中任意的前缀中1的个数不能小于0的个数,问这样的字符串一共有多少个。结果对20100501取膜。
分析
首先总方案数是,考虑不合法方案数。
此处有一个很有意思的抽象(谁想得到啊),就是在平面直角坐标系中,从开始,在字符串中遇到0就向右走1,遇到1就向上走1,最后要走到。那么,合法的路径一定不会与直线即相交,不合法的路径就一定会与它相交。
但是这样还是没法求,因为起点和终点都在直线的同侧。我们可以找到关于的对称点,这样从出发到的所有路线(取一个对称就是原来的路径)就会与直线相交了,可以直接用排列组合的公式(相当于问从走到的路线数)求得不合法路径数为。
故最终答案是
膜质数意义下的组合数可用卢卡斯定理快速求出
可是20100501不是质数。展开上式得
有除法,不能用逆元。应该用唯一分解定理对上下约分再把素因子乘起来。
阶乘的质因数分解
对于n的阶乘中数x的次数,1到n中含有x的一次项的有共计个,以此类推,含有二次项的有个,含有三次项的有个……最终想的次数就是以上数列求和,可以递推解决。
1 2 3 4 5 6 7 8
| int count_fact(int n, int x) { int ret = 0; while (n > 0) { n /= x; ret += n; } return ret; }
|
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80
| #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std;
typedef long long int64;
const int MAXN = 1e6+10; const int MAXA = 2e6+10; const int64 MOD = 20100501; const int AMXA = 2e6;
int64 prime[MAXN]; bool isntp[MAXA]; int pcnt;
void make_prime() { pcnt = 0; memset(isntp, false, sizeof(isntp)); for (int i = 2; i < AMXA; ++i) { if (!isntp[i]) { prime[++pcnt] = i; } for (int j = 1; j <= pcnt; ++j) { if (i * prime[j] > AMXA) { break; } isntp[i * prime[j]] = true; if (i % prime[j] == 0) { break; } } } }
template <typename T> T pow_mod(T a, T b, T MOD) { T res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b /= 2; } return res; }
int64 count_fact(int64 n, int64 x) { int64 ret = 0; while (n > 0) { n /= x; ret += n; } return ret; }
int main(){ make_prime(); int tcnt; cin >> tcnt; for(int T = 1;T<=tcnt;T++){ int n,m; cin >> n >> m; int64 ans = 1; int64 res = n-m+1; for(int i = 1;i<=pcnt && prime[i] <= (m+n);i++){ int64 cnt = 0; while(res % prime[i] == 0){ cnt++; res /= prime[i]; } cnt += count_fact(n+m,prime[i]); cnt -= count_fact(m,prime[i]); cnt -= count_fact(n+1,prime[i]); ans *= pow_mod(prime[i],cnt,MOD); ans %= MOD; } cout << ans << endl; } }
|