Views

好玩的数论题。想想发现可以像快速幂一样跑。然后就是思考如何转移优化。 发现模数比较奇怪。居然是fnt的模数ovo那就要用fft喽？可是这里是乘啊。木有关系喽，因为m是素数，所以它一定有原根。于是可以取原根的幂次，就变成加辣。 这种东西我自己当然想不出来ovo 同余系下的东西真有趣ovo

好无语的一天ovo 上午讲的东西还是非常能听的，虽然出现了不少原题ovo然后发现自己还是好年轻啊，很多东西想得都不够透彻。 下午考试证明了正确投资的重要性。 第一题就是状态压缩dp，不过显然我写得太，丑，了。又wa又t一时爽yeah。 第二题全场基本都把题意理解错了ovo我还有什么好说的呢。不过目测没有别人写这种题意的正解。我来mark一下。 首先左右端点还是满足单调的。然后就是加点删点判断最小无向子树。以1为根，分两种情况讨论。一种是本来就是一棵子树，那么随便选一个点二分就可以找到这棵子树的最小大小。另一种是除了某个点为根的子树的另一部分。那么可以为根的点就是子树里没有已选点的点。那么用树链剖分来维护哪些点可选就可以辣。非常好写好调ovo 然后出题人理解的题意是做过的ovo 第三题各种无语水。 然后晚上题完全没有思路弃疗ing. 所以我还是太年轻了。积累一个经验就是如果题意感觉会有歧义的话一定要问清楚。

#include #include #include using namespace std; struct edge { int t; edge *next; }; const int maxn = 109; const int inf = 0x3f3f3f3f; edge *head[maxn], ebuf_arr[maxn « 1], ebuf; int n, f[maxn][2][2]; / f[node][if u is light][if u is chosen] */ inline void addEdge(int u, int v) { ebuf-> t = v; ebuf-> next = head[u]; head[u] = ebuf ++; } #define protect(x) { if (x > inf) x = inf; }...

之前听说是异或高消？好神的感觉。 然后可以树形dp嘛！为啥网上题解这么误导ovo 就是f[u][i][j]表示u这个点有没有亮，有没有被按开关。完了嘛。 无语了辣。

省上奇怪的集训的day1. 早上讲的东西还是比较能听的.然后我自己非常的naive嘛.听说讲课的就是省选的出题人?然后看着这些可以"把握我的命运"的人,有种奇怪的感觉. 下午随便考了一发试. 第一题想到了dp,但是一直在想平方和存不下啊怎么办啊.然后最后才知道平方都要乘n次干嘛要存下来. 第二题水水的树形dp. 第三题还行的算几.反正就对称一下就好了.中途把线线交写丑了晕. 晚上居然还有题. 第一题第二题看了看不想做,因为感觉第三题比较有趣.可是最后还是只想到O(n)的做法不开心ovo 所以我还是太弱了.马上都要省选了啊怎么办.

比较神奇的数学题.首先你得听说过一个东西叫Mertens函数.于是你可以找到一篇论文.然后你发现它是英文的.试图理解了很久没有成功. 然后终于有人良心贴出了一个blog.这回懂辣开心ovo 其实就是那一个公式:F(n) = ∑一堆约数 + ∑k=2nF([n/k]) 然后发现mu和phi的左边一堆都是可以O(1)算的辣.右边强行记搜可以做到O(n2/3)的辣. 然后手写个hash啥的就能跑得飞快的辣.

#include #include #include using namespace std; typedef long long dint; #ifdef WIN32 #define lld “%I64d” #else #define lld “%lld” #endif #define _l (long long int) struct node { int v; dint phi, mu; node *next; }; const int maxv = 3000009; const int hmod = 4432457; int n, tp, pn[maxv], phi[maxv], mu[maxv]; dint sp[maxv], smu[maxv]; bool pr[maxv]; node *head[hmod]; void pre() { memset(pr, 0, sizeof(pr)); memset(head, 0, sizeof(head)); tp = 0; phi[1] = mu[1] = 1; for (int i = 2; i < maxv; ++ i) { if (!...

#include #include #include using namespace std; #define _l (long long int) const int maxn = 2000009; const int mod = (1 « 23) * 7 * 17 + 1; int n, a[maxn], b[maxn], c[maxn]; int readInt(int* a) { static char g[maxn]; scanf("%s", g); int l(strlen(g)); for (int i = 0; i < l; ++ i) a[l - i - 1] = g[i] - 48; return l; } int modPow(int a, int x) { int s(1); for (; x; x »= 1, a = _l a * a % mod) if (x & 1) s = _l s * a % mod; return s; }...

水水的fft啦.主要是来mark一下数论版fft. 有一个奇妙的东西叫原根.这个玩意要乘(p-1)次才能乘回自己.然后如果(p-1)含有很多很多个2的话,就可以拿来做fft辣.其实就是解决了fft的单位根,不用complex.剩下的照搬好辣. 水ovo.在这个前不着村后不着店的四星酒店里好无语ovo

不打算再刷题了.省选的时候就让它保持700这个数字吧.突然闲下来感觉好奇怪. 还有一个星期就省选了呢.时间过得好快.至今后悔没有去参加2012年的省选,然后现在是2015年. 想起2013年的时候各种奇怪,叛逆?然后也只是去观摩一下.唉.然后2014年因为数组开小而抱憾. 然后我就高二了.然后就不会再有然后了. 很郁闷为什么总是要最后一次才是正位.为什么年轻的我就必需去中考,去学文化课?好羡慕初中就能来参加训练的学弟.毕竟初中的我是不会线段树的. 不管如何,六年的路走到了将要分叉的地方了.看到高三某逃课君,抛开他使得全教室环境变差不说,其实也蛮那啥的.如果真的退役了,嘴上很倔强,心里真的放得下?真的能狠下那条心去当飞行员? 我不服.唯一的出路是战斗. 来吧,scoi.