bzoj 1008
逆向思维。一共有m^n种状态
我们考虑不越狱的情况
第一个人有m种选择，后面的所有人均是m-1种选择
那么方案数就是 m^n - m * (m - 1) ^ (n - 1) 快速幂就好
其实不难，自己不要怕，心理不要有障碍
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MOD = 100003;ll cal(ll a, ll b)
{ll res = 1;while(b){if(b & 1) res = (res * a) % MOD;a = a * a % MOD;b >>= 1;}return res;
}int main()
{ll m, n;scanf("%lld%lld", &m, &n);printf("%lld\n", (cal(m, n) - (m * cal(m - 1, n - 1) % MOD) + MOD) % MOD);return 0;
}「NOIP2011」计算系数(二项式定理)
裸题。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int mod = 10007;
const int MAXN = 1e3 + 10;
int c[MAXN][MAXN];void init()
{REP(i, 0, MAXN){c[i][0] = c[i][i] = 1;REP(j, 1, i)c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;}
}int power(int a, int b)
{int res = 1 % mod; a %= mod;for(; b; b >>= 1){if(b & 1) res = res * a % mod;a = a * a % mod;}return res;
}int main()
{init();int a, b, k, m, n;scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);printf("%d\n", c[k][n] * power(a, n) % mod * power(b, k - n) % mod);return 0;
}2^k 进制数
首先看到r的每一位严格小于它右边相邻的那一位，就可以想到组合了，因为这相当于排除了排列。
这道题的正解非常巧妙，把每一位拆成k位
比如是2^3进制，用0表示一位，那么就是0 0 0 | 0 0 0 | 0 0 0……
那么我们分两部分来考虑
（1）不包括首位，也就是每一位都是“满的”
那么显然每一个位有2^k-1种可能，可以选2个（即2位数）， 3个（三位数）……
一直到最多的位数，即w/k
那么用组合数加一下就好了。
（2）包括首位
那么首位可以取1到2^(w % k) - 1， w%k表示首位的位数
那么假设首位的数是i，那么后面的数就有2^k-1 - i种可能，选w/k个，同样用组合数计算即可
最后把两部分的值加起来就是答案。
然后这道题的空间按照极限数据是开不下的，但是数据貌似没有这么强，开小一些一样可以AC
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 200 + 10;
const int MAXM = 600;
int k, w, len, p, ma;struct bignum
{int c[MAXN], len;bignum() { len = 0; memset(c, 0, sizeof(c)); }void init() { len = 1; c[1] = 1; }bignum operator + (const bignum& a){bignum res;res.len = max(len, a.len);_for(i, 1, res.len){res.c[i] += c[i] + a.c[i];if(res.c[i] >= 10){res.c[i + 1]++;res.c[i] %= 10;}}if(res.c[res.len + 1] > 0) res.len++;return res;}bignum operator += (const bignum& a) { *this = *this + a; }void print(){for(int i = len; i >= 1; i--) printf("%d", c[i]);puts(""); } }C[MAXM][MAXM]; void get_C()
{_for(i, 0, max(ma, len)){C[i][0].init(); C[i][i].init();REP(j, 1, i) C[i][j] = C[i-1][j] + C[i-1][j-1];}
}int main()
{scanf("%d%d", &k, &w);len = w / k, p = w % k, ma = (1 << k) - 1;get_C();bignum ans;_for(i, 2, len) ans += C[ma][i];REP(i, 1, 1 << p) ans += C[ma - i][len]; ans.print();return 0;
}Lucas定理模板
知道一个公式就好了
c(n, m) % p = c(n % p, m % p) * c(n / p, m / p)
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll p;ll power(ll a, ll b)
{ll res = 1 % p; a %= p;for(; b; b >>= 1){if(b & 1) res = res * a % p;a = a * a % p;}return res;
}inline ll inv(ll a) { return power(a, p - 2); }ll C(ll n, ll m)
{if(m > n) return 0;ll a = 1, b = 1;_for(i, n - m + 1, n) a = a * i % p;_for(i, 1, m) b = b * i % p;return a * inv(b) % p;
}ll Lucas(ll n, ll m)
{if(!m) return 1;return C(n % p, m % p) * Lucas(n / p, m / p) % p;
}int main()
{int T, n, m; scanf("%d", &T);while(T--){scanf("%d%d%lld", &n, &m, &p);printf("%lld\n", Lucas(n, m));}return 0;
}[Sdoi2010]古代猪文
考的知识点很广。
首先求得含有幂，所以可以用欧拉定理。
但是这里要特判一下
然后把999911658分解质因数，对每一个质因数求一遍值，最后用中国剩余定理合并。
求组合数用lucas定理，其中阶乘可以预处理
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll p = 999911658;
ll a[] = {2, 3, 4679, 35617}, b[5];
ll fac[5][36000];ll pow(ll a, ll b, ll mod)
{ll res = 1 % mod; a %= mod;for(; b; b >>= 1){if(b & 1) res = res * a % mod;a = a * a % mod;}return res;
}inline ll inv(ll a, ll mod) { return pow(a, mod - 2, mod); }inline ll C(ll n, ll m, ll x)
{ll mod = a[x];if(m > n) return 0;return fac[x][n] * inv(fac[x][m], mod) % mod * inv(fac[x][n - m], mod) % mod;
}ll Lucas(ll n, ll m, ll x)
{ll mod = a[x];if(!m) return 1;return C(n % mod, m % mod, x) * Lucas(n / mod, m / mod, x) % mod;
}void exgcd(ll a, ll b, ll& d, ll& x, ll& y)
{if(!b) { d = a; x = 1; y = 0; return; }else { exgcd(b, a % b, d, y, x); y -= x * (a / b); }
}int main()
{ll n, g;scanf("%lld%lld", &n, &g);g %= (p + 1);if(!g) { puts("0"); return 0; }REP(i, 0, 4){fac[i][0] = 1;_for(j, 1, a[i])fac[i][j] = fac[i][j-1] * j % a[i];;}for(int i = 1; (ll)i *i <= n; i++)if(n % i == 0){REP(j, 0, 4) {b[j] = (b[j] + Lucas(n, i, j)) % a[j];if(i != n / i) b[j] = (b[j] + Lucas(n, n / i, j)) % a[j];}}ll ans = 0, d, x, y;REP(i, 0, 4){ll mi = p / a[i]; exgcd(mi, a[i], d, x, y);ans = (ans + x * b[i] % p * mi) % p;} ans = (ans % p + p) % p;ans = pow(g, ans, p + 1);printf("%lld\n", ans);return 0;
}
bzoj 3898
其实这道题用dp做非常简单，可以用前缀和优化一下。
#include<bits/stdc++.h>
#define add(a, b) a = (a + b) % mod
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int mod = 5000011;
const int MAXN = 1e5 + 10;
int dp[MAXN], sum[MAXN], n, k;int main()
{scanf("%d%d", &n, &k);dp[0] = sum[0] = 1;_for(i, 1, n){if(i - k - 1 >= 0)add(dp[i], sum[i - k - 1]); else dp[i] = 1;add(sum[i], dp[i] + sum[i-1]);}printf("%d\n", sum[n]);return 0;
}但是我想的时候在想组合。
我想的是枚举公的数量，然后每一只公的和几个母的看作一块来排。
但是具体怎么弄还是没想到。
其实这离正解很近的。
正解就是直接把那几个母的去掉，然后做组合就好了。
我就差了这一步……
#include<bits/stdc++.h>
#define add(a, b) a = (a + b) % mod
#define mul(a, b) a = (a * b) % mod
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 5000011;
const int MAXN = 1e5 + 10;
int n, k;ll power(ll a, ll b)
{ll res = 1 % mod; a %= mod;for(; b; b >>= 1){if(b & 1) mul(res, a);mul(a, a);}return res;
}inline ll inv(ll a) { return power(a, mod - 2); }ll C(int n, int m)
{ll a = 1, b = 1;_for(i, n - m + 1, n) mul(a, i);_for(i, 1, m) mul(b, i);return a * inv(b) % mod;
}int main()
{ll ans = 0;scanf("%d%d", &n, &k);_for(i, 0, n){int t = n - (i - 1) * k;if(t < i) break;add(ans, C(t, i));}printf("%lld\n", ans);return 0;
}「一本通 6.6 练习 2」方程的解
这种方程解的组数的题可以转化为插板法
答案为C（g-1, k-1）
然后就是要用高精度了
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e4;
const int p = 1e3;struct bign
{int len, c[MAXN];bign() { len = 0; memset(c, 0, sizeof(c)); }bign operator * (int b){bign a = *this, res;res.len = a.len;_for(i, 1, len) {res.c[i] += a.c[i] * b;res.c[i + 1] += res.c[i] / 10;res.c[i] %= 10;}while(res.c[res.len + 1] > 0){res.len++;res.c[res.len + 1] += res.c[res.len] / 10;res.c[res.len] %= 10;}return res;}bign operator / (int b){bign a = *this, res;res.len = a.len;int x = 0;for(int i = len; i >= 1; i--){int now = x * 10 + a.c[i];res.c[i] = now / b;x = now % b;}while(!res.c[res.len]) res.len--;return res;}void print(){for(int i = len; i >= 1; i--) printf("%d", c[i]);puts("");}
};int power(int a, int b)
{int res = 1 % p; a %= p;for(; b; b >>= 1){if(b & 1) res = res * a % p;a = a * a % p;}return res;
}int main()
{int k, x, t, g; scanf("%d%d", &k, &x); g = power(x, x);bign ans; g--; k--;ans.len = 1; ans.c[1] = 1;_for(i, 1, k) ans = ans * g / i, g--;ans.print();return 0;
}bzoj 2982
刷刷水题压压惊。Lucas定理模板题
阶乘和逆元可以预处理，快了很多
0的逆元看作1
#include<bits/stdc++.h>
#define mul(a, b) a = (a * b) % mod
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int mod = 10007;ll fac[mod + 10], facinv[mod + 10];ll power(ll a, ll b)
{ll res = 1 % mod; a %= mod;for(; b; b >>= 1){if(b & 1) mul(res, a);mul(a, a);}return res;
}void init()
{fac[0] = facinv[0] = 1;_for(i, 1, mod) {fac[i] = fac[i - 1] * i % mod;facinv[i] = power(fac[i], mod - 2);}
}inline ll C(ll n, ll m)
{if(m > n) return 0;return fac[n] * facinv[m] % mod * facinv[n - m] % mod;
}ll Lucas(ll n, ll m)
{if(!m) return 1;return Lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}int main()
{init();int T; scanf("%d", &T);while(T--){ll n, m;scanf("%lld%lld", &n, &m);printf("%lld\n", Lucas(n, m));}return 0;
}