/category/algo/ /archives/271/ 2019-11-06T22:11:00+08:00 把 $$0$$~$$2^n-1$$ $$(n\ge 2)$$ 划分为若干组使得每组异或和为 0，最多分出多少组？ 显然组数的上界是 $$\lceil\frac{n}{3}\rceil$$。 可以递归构造： ```python def gen(n): if n==2: return [(0,),(1,2,3)] if n==3: return [(0,),(1,2,3),(4,5,6,7)] s=gen(n-2) res=[(0,),(1,2,3)] for i in s: if len(i)==3: key=[0,2,3,1] for j in range(4): res.append((i[0] /archives/265/ 2019-06-05T23:47:00+08:00 http://ljt12138.blog.uoj.ac/blog/5059 对于第二个问题，当 $$n\ge 8$$ 时，可以如下构造： 对于 $$1$$ 的个数为偶数和奇数的两种数，按 $$1$$ 的个数从小到大，其次大小从大到小排序。$$p$$ 个人在偶数堆中从前向后选，$$q$$ 个人在奇数堆中从后向前选。 显然只需要验证 $$p+q=\lfloor\frac{2^n}{3}\rfloor$$ 且 $$\max(p,q)\le 2^{n-2}$$ 的正确性。 用程序可以容易的证明 $$n$$ 较小情况的正确性（[https://paste.ubuntu.com/p/XndFcftKF9/](https://paste.ubuntu.com/p/XndFcftKF9/)）。 设 $$p$$ 个人中最后一个选择的数 $$x$$ 的 $$1$$ 的个数为 $$i$$，$$q$$ 个人中最后选择的数 $$y$$ 的 $$1$$ 的个数为 $$j$$，那么显然 $$j>i$$。 当 $$j>i+2$$ 时，显然不会有数相邻；而 $$j=i+1$$ 时，只要证明 $$x>y$$，那么 $$y$$ 去掉某个 $$1$$ 之后一定比 $$x$$ 小，也就证明了不可能有两个数相邻。 只要预处理组合数，就可以在 $$O(n)$$ 时间内知道某个 $$x$$ 对应的 $$y$$，然后再找到比这个 $$y$$ 小的最大的 $$x$$，这样不停迭代，最终就可以验证这个的正确性（[https://paste.ubuntu.com/p/gHmTyZbvGr/](https://paste.ubuntu.com/p/gHmTyZbvGr/)）。 /archives/236/ 2017-05-25T20:24:07+08:00 ###Description 给一棵树，每个点点权 $$a_i$$，保证 $$a_i$$各不相同，现在随机选两个点 $$u,v$$，求 $$f(u,v)=\phi(a_u\cdot a_v)\cdot dis(u,v)$$ 的期望，$$mod\ 10^9+7$$。 链接：[http://codeforces.com/contest/809/problem/E](http://codeforces.com/contest/809/problem/E "http://codeforces.com/contest/809/problem/E") ###Solution 首先，有一个结论：$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)},g=gcd(a,b)$$ 证明：考虑找一个 $$x$$，使得 $$x|b,gcd(\frac{b}{x},a)=1,gcd(x,\frac{b}{x})=1$$ 且 $$a$$ 包含 $$x$$ 中所有质因子。 那么 $$\phi(a\cdot b)=\phi(a)\cdot x\cdot\phi(\frac{b}{x})=\frac{\phi(a)\cdot\phi(b)\cdot x}{\phi(x)}$$ 显然，$$x$$ 是 $$g$$ 的倍数，所以 $$\frac{x}{g}=\frac{\phi(x)}{\phi(g)}$$，所以$$\phi(a\cdot b)=\frac{\phi(a)\cdot\phi(b)\cdot g}{\phi(g)}$$ 有了这个结论之后可以考虑点分，那么设 $$dis(x)$$ 表示 $$x$$ 到当前根的距离。 设 $$h(x)=\frac{x}{\phi(x)}$$，那么$$f(u,v)=\phi(a_u)\cdot\phi(a_v)\cdot h(g)\cdot(dis(u)+dis(v)),g=gcd(a_u,a_v)$$ 考虑当 $$u$$ 确定时，需要知道 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))$$ 和 $$\sum\phi(a_v)\cdot h(gcd(a_u,a_v))\cdot dis(v)$$。 设 $$g(x)=h(x)-\sum[y|x,y\neq x]g(y)$$，那么 $$h(gcd(a_u,a_v))=\sum[x|a_u,x|a_v]g(x)$$ 这样就可以直接枚举约数算贡献了。 ###Code ```c++ #include typedef long long ll; inline void repr(int&a,int b){if(ato,x); sz[x]+=sz[i->to]; } } inline void dfs2(int x,int fa) { int t=rsz-sz[x]; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { repr(t,sz[i->to]); dfs2(i->to,x); } if(tne) if(i->to!=fa&&!vis[i->to]) dfs3(i->to,x,dis+1); } inline void dfs4(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P,A,B; foe(i,v[w[x]]) { get(*i,A,B); ans=(ans+(ll)a*B+(ll)b*A)%P; } for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) dfs4(i->to,x,dis+1); } inline void work(int x) { dfs1(x,0); rsz=nsz=sz[x],nro=x; dfs2(x,0); vis[x=nro]=1; foe(i,v[w[x]])set(*i,phi[w[x]],0); for(edge*i=p[x];i;i=i->ne) if(!vis[i->to]) { dfs4(i->to,x,1); dfs3(i->to,x,1); } fo0(i,qe)g[q[i]]=h[q[i]]=-1; qe=0; for(edge*i=p[x];i;i=i->ne) if(!vis[i->to])work(i->to); } int main() { fo1(i,N-1)for(int j=i;j /archives/181/ 2017-02-28T00:16:00+08:00 ###Description ![fa(1).jpg][1] ###Solution $$\sum_i^n\sum_j^m[\mu(gcd(i,j))\neq 0]lcm(i,j)$$ $$=\sum_k^n|\mu(k)|\sum_i^{\frac{n}{k}}\sum_j^{\frac{n}{k}}[gcd(i,j)=1]i\cdot j\cdot k$$ $$=\sum_k^n|\mu(k)|\cdot k\sum_d^{\frac{n}{k}}\mu(d)\cdot d^2\sum_i^{\frac{n}{k\cdot d}}\sum_j^{\frac{m}{k\cdot d}}i\cdot j$$ $$=\sum_k^n\sum_d[d|k]\mu(d)\cdot d^2\cdot|\mu(\frac{k}{d})|\cdot\frac{p}{d}\cdot\frac{\frac{n}{k}\cdot(\frac{n}{k}+1)}{2}\cdot\frac{\frac{m}{k}\cdot(\frac{m}{k}+1)}{2}$$ 最后的式子，前面是积性函数，后面根号分块 ###Code ```c++ #define _GLIBCXX_IOSTREAM #include #define N 4000001 int pri[N],pm,f[N],ps[N],pc[N]; bool np[N]; int main() { for(int i=2;i /archives/180/ 2017-02-20T22:27:00+08:00 ##Description 幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的2600岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 这时幽香发现了一件非常有趣的事情，太阳花田有n块空地。在过去，幽香为了方便，在这n块空地之间修建了n-1条边将它们连通起来。也就是说，这n块空地形成了一个树的结构。 有n个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺，他们选择了c中颜色的衣服，每种颜色恰好可以用一个0到c-1之间的整数来表示。并且每个人都站在一个空地上，每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。 粉丝们策划的一个节目是这样的，选中两个粉丝A和B（A和B可以相同），然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来（包括端点），幽香就能看到一个长度为A到B之间路径上的所有粉丝的数目（包括A和B）的颜色序列。一开始大家打算让人一两个粉丝（注意：A,B和B,A是不同的，他们形成的序列刚好相反，比如红绿蓝和蓝绿红）都来一次，但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。 于是他们想要问题，在这个树上，一共有多少可能的不同的颜色序列（子串）幽香可以看到呢？ 太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。 ###Input 第一行两个正整数n,c。表示空地数量和颜色数量。 第二行有n个0到c-1之间，由空格隔开的整数，依次表示第i块空地上的粉丝的衣服颜色。（这里我们按照节点标号从小到大的顺序依次给出每块空地上粉丝的衣服颜色）。 接下来n-1行，每行两个正整数u,v，表示有一条连接空地u和空地v的边。 ###Output 一行，输出一个整数，表示答案。 ###Sample Input 7 3 0 2 1 2 1 0 0 1 2 3 4 3 5 4 6 5 7 2 5 ###Sample Output 30 ###HINT 对于所有数据，1nxt[t]=cur; if(!p){cur->link=start;goto naive;} q=p->nxt[t]; if(p->ma+1==q->ma){cur->link=q;goto naive;} sq=pm++; sq->ma=p->ma+1; memcpy(sq->nxt,q->nxt,sizeof(q->nxt)); for(;p&&p->nxt[t]==q;p=p->link)p->nxt[t]=sq; sq->link=q->link; q->link=sq; cur->link=sq; naive:lst=cur; } struct edge { int to;edge*ne; }_e[200000],*e=_e,*p[100001]; inline void add(int a,int b) { *e=(edge){b,p[a]};p[a]=e++; } int c[100001],deg[100001]; void dfs(int x,int fa) { add(c[x]); node*t=_A::lst; for(edge*i=p[x];i;i=i->ne) if(i->to^fa) { _A::lst=t; dfs(i->to,x); } } node*q[N*2]; int main() { int n,x,y; scanf("%d%*d",&n); for(int i=1;iinc) q[i]->nxt[j]->inc=1e9,q[qe++]=q[i]->nxt[j]; for(int i=qe-1;~i;i--) { for(int j=0;jnxt[j])q[i]->cnt+=q[i]->nxt[j]->cnt; q[i]->cnt++; } printf("%lld",start->cnt-1); } ``` /archives/176/ 2017-01-24T19:59:00+08:00 2018.3.3：更新了测试代码，加入了更多写法，修复了一些致命错误 测试机CPU为Intel® Celeron® Processor G3900，内存为8GB DDR4，系统为Debian 9。 编译命令为g++ test.cpp -o test -O3。 先放测试代码： ```c++ #include #include #include #include #define N 1024 #define T 100000 int fa[N+233],st[N+233],sz[N+233]; int find1(int x) { return x==fa[x]?x:fa[x]=find1(fa[x]); } inline int find2(int x) { return x==fa[x]?x:fa[x]=find2(fa[x]); } inline int find3(int x) { while(x!=fa[x])x=fa[x]=fa[fa[x]];return x; } inline int find4(int x) { int se=0;st[0]=x; while(fa[x]!=x)st[++se]=x=fa[x]; while(se)fa[st[--se]]=x; return x; } inline int find5(int x) { int t=x,p; while(x!=fa[x])x=fa[x]; while(t!=x)p=fa[t],fa[t]=x,t=p; return x; } int find6(int x) { return 0>fa[x]?x:fa[x]=find6(fa[x]); } inline int find7(int x) { return 0>fa[x]?x:fa[x]=find7(fa[x]); } inline int find8(int x) { while(fa[x]>=0&&fa[fa[x]]>=0)x=fa[x]=fa[fa[x]];return fa[x] /archives/175/ 2017-01-20T22:21:00+08:00 ###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1 ###Code ```c++ #include typedef double lf; #define fo0(i,n) for(int i=0,i##end=n;i>1|(i&1)nxt[u]; } cur=tmp; } } } inline void count() { for(node *x=tm-1;x>=t;x--) if(x->fail)x->fail->cnt+=x->cnt; } #define P 1000000007 inline int cnt() { int ans=0; for(node *x=tm-1;x>t+1;x--) ans=mod(ans+x->cnt,P); return ans; } char s[100000]; num p[N]; int po[100001]; int main() { scanf("%s",s); int n=strlen(s); fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P); int y=0; while((1 /archives/163/ 2017-01-08T00:20:00+08:00 ###Description 给定一个长度为n的正整数数列a[i]。 定义2个位置的graze值为两者位置差与数值差的和，即graze(x,y)=|x-y|+|a[x]-a[y]|。 2种操作（k都是正整数）： 1.Modify x k：将第x个数的值修改为k。 2.Query x k：询问有几个i满足graze(x,i) /archives/159/ 2016-12-26T15:09:00+08:00 ###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1 /archives/158/ 2016-12-26T10:48:00+08:00 ###Description 菩萨为行，福慧双修，智人得果，不忘其本。 ——唐朠立《大慈恩寺三藏法师传》 有才而知进退，福慧双修，这才难得。 ——乌雅氏 如何福慧双修？被太后教导的甄嬛徘徊在御花园当中。突然，她发现御花园中的花朵全都是红色和蓝色的。她冥冥之中得到了响应：这就是指导她如何福慧双修的！ 现在御花园可以看作是有N块区域，M条小路，两块区域之间可通过小路连接起来。现在甄嬛站在1号区域，而她需要在御花园中绕一绕，且至少经过1个非1号区 域的区域。但是恰好1号区域离碎玉轩最近，因此她最后还是要回到1号区域。由于太后教导她要福慧双修，因此，甄嬛不能走过任何一条她曾经走过的路。但是， 御花园中来往的奴才们太多了，而且奴才们前行的方向也不一样，因此甄嬛在走某条小路的时候，方向不同所花的时间不一定一样。天色快暗了，甄嬛需要尽快知道 至少需要花多少时间才能学会如何福慧双修。如果甄嬛无法达到目的，输出“-1”。 ###Input 第一行仅2个正整数n,m，意义如题。 接下来m行每行4个正整数s,t,v,w，其中s,t为小路所连接的两个区域的编号，v为甄嬛从s到t所需的时间，w为甄嬛从t到s所需的时间。数据保证无重边。 ###Output 仅一行，为甄嬛回到1号区域所需的最短时间，若方案不存在，则输出-1 ###Sample Input 3 3 1 2 2 3 2 3 1 4 3 1 5 2 ###Sample Output 8 ###Solution 一条合法路径一定是1->a->...->b->1这样的 考虑a和b一定有至少一个二进制位不同 所以按二进制分组，每次新建一个源点和汇点，分别连向某位为1和0的点，然后跑最短路 ###Code ```c++ #include #define mp(a,b) std::make_pair(a,b) int n,p[40001],dis[40001]; bool vis[40001]; std::priority_queueq; struct edge { int to,ne,w; }e[200001]; inline void add(int i,int a,int b,int w) { e[i].to=b,e[i].ne=p[a],e[i].w=w,p[a]=i; } inline void yjq(int andv,int anda,int &ans) { memset(dis,0x7f,sizeof(dis)); memset(vis,0,sizeof(vis)); for(int j=p[1];j;j=e[j].ne) if((e[j].to&andv)==anda) q.push(mp(dis[e[j].to]=e[j].w,e[j].to)); while(!q.empty()) { int k=q.top().second;q.pop(); if(vis[k])continue; vis[k]=1; for(int j=p[k];j;j=e[j].ne) if(e[j].to==1) { if((k&andv)!=anda&&ans>dis[k]+e[j].w)ans=std::min(ans,dis[k]+e[j].w); } else if(dis[e[j].to]>dis[k]+e[j].w) { q.push(mp(dis[e[j].to]=dis[k]+e[j].w,e[j].to)); } } } int main() { int m; scanf("%d%d",&n,&m); for(int i=0;i