math

优化方法暑假的时候zhx讲过，我居然还记得好感动。 Mobius反演加些奇异的东西。（不会用公式编辑器是不是已经落伍了） 两个优化-> sqrt(n)^2 == n。 跑得飞慢 。而且中间那坨又长又丑。 久了不写都快忘了。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int maxn = 10000009; const int mod = 20101009; int pn[maxn], mu[maxn], smu[maxn], tp; bool pr[maxn]; void pre(int maxn) { memset(pr, 0, sizeof(pr)); tp = 0; mu[1] = 1; for (int i = 2; i <= maxn; ++ i) { if (!pr[i]) { pn[tp ++] = i; mu[i] = -1; } for (int j = 0; j < tp && i * pn[j] <= maxn; ++ j) {...

题意：求n!在b进制下的位数（n<=2^31）。 好像要高精！？好像会TLE！？根本不会做！ 然后想到answer=∑log(k,i) 然后积分？∫ln(x) dx = xln(x) - x 小数据直接跑，过之。试个极限数据，差了3！？ 仔细一想，对数函数是凹的，这样算答案当然会偏小。 百度了一下，发现有个公式：n!≈√(2*π*n)*(n/e)^n。 拆开之后发现就是比原来的积分多了个ln(2*π*n) #include <cstdio> #include <cmath> const double pi = asin(1) * 2.0; double calc(double n, double k) { double ans = 0; if (n < 100000) { for (int i = 1; i <= n; ++ i) ans += log(i); ans /= log(k); } else { ans = (0.5 * log(pi * n * 2) + log(n) * n - n) / log(k); } return ans + 0.5; }...

好像数学都退化了。 其实一直没有用过中国剩余定理。虽然好像也不是太麻烦，不过要记住。 然后这题也比较裸吧。把C(n,m)中的阶乘分解成t*p^k的样子就好了。ORZ JASON_YU #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long qw; #define _l (qw) const int mod = 999911659; const int pn[4] = {2, 3, 4679, 35617}; const int maxb = 50009; int n, g, fac[maxb], tf, s[4]; int t[maxb]; int modPow(int a, int x, int mod) { int s = 1; for (a %= mod; x; x >>= 1, a = _l a * a % mod)...

写完Kdtree感觉整个人都要离散了。 这题比较神，之前连题都没看懂。每个位置的方案数就是上下左右的数量的组合数的乘积。把x离散之后维护区间中左×右的和，上下y相同的扫一遍搞定。（感觉说了像没说） #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct point { int x, y; }; const int maxn = 100009; const int maxk = 13; inline bool cmpP(int* a, int* b) { return *a < *b; } inline bool cmpy(const point& a, const point& b) { return (a. y < b. y) || (a. y == b. y && a. x < b. x); } point a[maxn]; int n, m, c[maxn][maxk], cx[maxn], tx[maxn], t[maxn], maxx, ans;...

BZOJ里的第二道noip题，今年防ak题，OTZ。 最初直接用大素数取模的方法要TLE，虽然本机不会。 用几个小质数pni，算出在模pni的同余系里0~pni-1的答案。如果x为原方程的解的话x%pni在模pni意义下也应该为0。 然后还是会TLE，最后发现小质数乘的时候不用取模了。bzoj上这题纯粹是丧心病狂卡常数啊。 ORZMHY #define PROC "equation" #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef unsigned long long uqw; typedef long long qw; const int maxn = 109; const int maxl = 10009; const int maxm = 1000009; const int cp = 5; //const int pn[cp] = {111119, 23333, 11113, 23251, 33329}; const int pn[] = {22861, 22871, 22877, 22901, 22907, 22921}; const int p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};...

居然写了一半手贱就把所有东西都弄没了。严重地不开心。 既然这样那么简单说吧。 长度≤10^5这个条件在bzoj上没说。 用fft求出长度和为leni的组数。 枚举第三根火柴，可行的是（它作为最长的总组合数 - （长度≤它的组合数））那么多组。 fft必需常数够小。不写蝴蝶会tle。 #include <cstdio> #include <cmath> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } struct cplx { double r, i; inline cplx() { r = 0, i = 0; } inline cplx(double r0, double i0) { r = r0, i = i0;...

比较神奇的数学题。 重要的结论是<n且与n素质的数的和是phi(n)*n/2。 所以就枚举一下gcd就好了。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 1000009; qw ans[maxn]; int tp, pn[maxn], phi[maxn]; bool pr[maxn]; void pre() { memset(pr, 0, sizeof(pr));...

感觉几百年没有刷bzoj了？虽然昨天才写了题，下午也还交了题的。 还是挺水的一道矩阵题。看到数列想得到矩阵，不知道没看到数列能不能想到矩阵。 关键是求和比较不好想。其实新加一行把和记下来就行了。重点就是构造对吧。 然后矩阵快速幂啥的还好。主要是要记得快速乘。（想起了zhx的babysit） #include <iostream> #ifndef ONLINE_JUDGE #include <fstream> #define cin _cin_ std :: ifstream cin("in.txt"); #endif #include <algorithm> using namespace std; typedef long long qw; const int maxn = 19; qw n, b[maxn], c[maxn], x, y, mod; qw modMul(qw a, qw b) { qw s = 0; for (; b; b >>= 1, a = (a << 1) % mod) if (b & 1) s = (s + a) % mod; return s; } class matrix {...

居然继续沦落到写CV的题解的地步了。 这又是一道坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑坑题。 思路很简单。就是记a的列前缀和和b的行前缀和，每次询问的时候O(n)的扫一遍乘积累和。 但是，极限数据本地要跑3.2s。虽然我笔记本是慢，但是也不能这样玩我啊。交了好久都在tle。 最后想到一个常数优化的办法。因为每次是把一行或者一列的数都访问一遍，所以用一个指针把数组的那一行记下来。这样寻址会快一些。事实证明快了不只一些。 坑，哈哈。 #include <cstdio> #include <cctype> #include <memory.h> #include <algorithm> using namespace std; typedef long long qw; #ifdef WIN32 #define lld "%I64d" #else #define lld "%lld" #endif #define _l (qw) #define readInt(_s_) {\ int _d_;\ _s_ = 0;\ while (!isdigit(_d_ = getchar()));\ while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\ } const int maxn = 2001; int a[maxn][maxn], b[maxn][maxn], n, m; int main() { readInt(n);...

沦落到写tyvj的题解了。不过看在这题之前只有7人过的份上就写一下好了。 式子是容斥，比较好想。answer = sigma((-1)^i * m^(n-i) * C(m, i)) (0 <= i <= m) m^(n-i)这一块用快速幂就好了。 然后对于前一题因为m很小所以用m^2把组合数弄出来就行了。但是这里m^2就T到明天去了。 观察 C(m, i) = m!/(i! * (m-i)!)  => C(m, i - 1) = m! / ((i-1)! * (m-i+1)!)  => C(m, i) = C(m, i - 1) / i * (m - i + 1) 这样递推用逆元来做就是O(m * lgm)的时间了。 然后这题就这样了。代码很短。 #include <iostream> #include <memory.h> using namespace std; #define _l (long long int) typedef long long qw; const int maxm = 1000009; const int mod = 1e9 + 7; int cm[maxm];...