BZOJ 4926: 皮皮妖的递推 June 9, 2017 ###Description YOUSIKI学习了递推，于是他请皮皮妖给他出道题，皮皮妖说： f(1)=1，f(i)=i-f(i-1)，求f(n) YOUSIKI看了一眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说： f(1)=1，f(i)=i-f(f(i-1))，求f(n) YOUSIKI看了两眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说： f(1)=1，f(i)=i-f(f(f(i-1)))，求f(n) YOUSIKI看了三眼把它秒切了，于是他要求皮皮妖加大难度，皮皮妖想了想，说： ... ... ... YOUSIKI看了m眼，但是没有能秒切，于是他找到你，请你帮他解决这个问题。 ###Input 一行两个正整数n,m。n<=10^18，m<=10^6 ###Output 一行一个整数f(n) ###Sample Input 4 2 ###Sample Output 3 ###HINT 样例解释：f(1)=1，f(2)=2-f(f(1))=1，f(3)=3-f(f(2))=2，f(4)=4-f(f(3))=3 ###Solution 为了描述简洁，把 $$f(f(..f(i)..))$$ 记为 $$f^x(i)$$。 显然，$$f(i)-f(i-1)=0\ or\ 1$$，设 $$h(i)$$ 表示最大的 $$x$$，使得对于任意 $$j\in [1,x]$$，$$f^j(i)\neq f^j(i-1)$$。 可以发现 $$f$$ 的转移可以表示为： $$f(1)=f(2)=1$$，对于 $$i\ge 3$$，若 $$h(i-1)\ge m$$，那么 $$f(i)=f(i-1),h(i)=0$$，否则 $$f(i)=f(i-1)+1,h(i)=h(f(i))+1$$（正确性显然）。 如果有办法求出 $$h$$，那么 $$f(i)=\sum_j^i[h(j)\le m-1]-1(i\neq 1)$$。 假设 $$m=4$$，将 $$h$$ 的表列出： ``` 0 0 1 2 3 4 0 5 0 1 6 0 1 2 7 0 1 2 3 8 ``` 换一种写法： ``` 0 0 1 2 3 4 0 5 0 1 6 0 1 2 7 0 1 2 3 8 0 1 2 3 4 0 9 0 1 2 3 5 0 4 0 1 ``` 可以发现从第二行开始（首行记为第 $$0$$ 行），每一行是把上一行的数复制一遍，加 $$1$$，然后在每个 $$\ge m$$ 的数后面加上 $$0$$ 得到的（正确性显然）。 如果把 $$\ge m$$ 的数都写成 $$m$$，那么表会变成这样： ``` 0 0 1 2 3 4 0 4 0 1 4 0 1 2 4 0 1 2 3 4 0 1 2 3 4 0 4 0 1 2 3 4 0 4 0 1 ``` 可以发现对于 $$i>m$$，第 $$i-1$$ 行是第 $$i$$ 行的前缀，且第 $$i$$ 行多出的部分是第 $$i-m$$ 行的内容（可使用数学归纳法证明）。 回到原问题，现在需要求 $$\sum_i^n[h(i)\le m-1]$$。 $$1$$ 到 $$n$$ 的 $$h$$ 一定包含若干整行和最后不满一行的部分。 对于每一行，可以用 $$a(i)$$ 表示这一行数的总数，$$b(i)$$ 表示这一行 $$\le m-1$$ 的数的个数。 显然，$$a(i)=b(i)=1(0\le i\le m),a(m+1)=2,b(m+1)=1$$，当 $$i\ge m+2$$ 时，$$a(i)=a(i-1)+a(i-m),b(i)=b(i-1)+b(i-m)$$。 事实上 $$b(i)$$ 并没有必要计算，因为 $$b(i)=a(i-1)$$。 这样已经可以解决前面的整行了。 对于后面不满一行的部分，可以从最后一行开始往前枚举，如果当前行的大小不超过需要的大小，那么就可以把当前行加入答案（在当前需要大小为 $$1$$ 时，需要特判只有一个 $$m$$ 的情况）。 这一部分可以由前面关于前缀的结论证明。 然后这题就完了。 <del>其他题解都直接给个莫名其妙的结论就跑，颓了几天这个题，真 $$tm$$ 爽。</del> ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; const int N=5000007; ll n,s,ans,a[N]; int m,i,j; int main() { scanf("%lld%d",&n,&m); if(n==1)return puts("1"),0; if(n<=m+2)return printf("%lld",n-1),0; for(i=0;i<=m;i++)a[i]=1; a[m+1]=2; s=m+4; for(i=m+2;s<=n;i++) s+=a[i]=a[i-1]+a[i-m]; i--; for(j=0;j+1<i;j++)ans+=a[j]; n-=s-a[i]; for(;n>1;i--) if(n>=a[i])n-=a[i],ans+=a[i-1]; printf("%lld",ans+1); } ```
Codeforces 809E. Surprise me! May 25, 2017 ###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<bits/stdc++.h> typedef long long ll; inline void repr(int&a,int b){if(a<b)a=b;} #define mset(a,b) memset(a,b,sizeof(a)) #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i) const int N=200007,P=1000000007; struct edge { int to;edge*ne; }_e[N*2],*e=_e,*p[N]; inline void add(int a,int b) { *e=(edge){b,p[a]};p[a]=e++; } std::vector<int>v[N]; int n,pr[N],pm,phi[N],inv[N],f[N],w[N],sz[N],rsz,nro,nsz,g[N],h[N],q[N],qe,ans; bool vis[N]; inline void dfs1(int x,int fa) { sz[x]=1; for(edge*i=p[x];i;i=i->ne) if(i->to!=fa&&!vis[i->to]) { dfs1(i->to,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(t<nsz)nsz=t,nro=x; } inline void set(int x,int y,int z) { if(!~g[x])q[qe++]=x,g[x]=h[x]=0; g[x]=(g[x]+(ll)y*f[x])%P; h[x]=(h[x]+(ll)z*f[x])%P; } inline void get(int x,int&y,int&z) { if(~g[x])y=g[x],z=h[x]; else y=z=0; } inline void dfs3(int x,int fa,int dis) { int a=phi[w[x]],b=(ll)a*dis%P; foe(i,v[w[x]])set(*i,a,b); for(edge*i=p[x];i;i=i->ne) 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<N;j+=i)v[j].push_back(i); fo(i,2,N-1) { if(!vis[i])pr[pm++]=i,phi[i]=i-1; for(int j=0;i*pr[j]<N;j++) { vis[i*pr[j]]=1; if(i%pr[j]==0) { phi[i*pr[j]]=phi[i]*pr[j]; break; } phi[i*pr[j]]=phi[i]*(pr[j]-1); } } phi[1]=1; inv[1]=1; fo(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P; fo1(i,N-1) { f[i]=(ll)i*inv[phi[i]]%P; foe(j,v[i])if(i^*j)(f[i]+=P-f[*j])%=P; } scanf("%d",&n); fo1(i,n)scanf("%d",w+i); fo0(i,n-1) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } mset(vis,0); mset(g,0xff); mset(h,0xff); work(1); ans=(ll)ans*inv[n]%P*inv[n-1]%P*2%P; printf("%d",ans); } ```
BZOJ 2694 & 4659 Lcm February 28, 2017 ###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<bits/stdc++.h> #define N 4000001 int pri[N],pm,f[N],ps[N],pc[N]; bool np[N]; int main() { for(int i=2;i<N;i++) { if(!np[i])pri[pm++]=i,f[i]=1,ps[i]=i,pc[i]=1; int rf; if(pc[i]==1)rf=f[i]*(ps[i]-ps[i]*ps[i]); else if(pc[i]==2)rf=-f[i]*ps[i]*ps[i]*ps[i]; else rf=0; for(int j=0;i*pri[j]<N;j++) { np[i*pri[j]]=1; if(i%pri[j])f[i*pri[j]]=rf,ps[i*pri[j]]=pri[j],pc[i*pri[j]]=1; else { f[i*pri[j]]=f[i],ps[i*pri[j]]=pri[j],pc[i*pri[j]]=pc[i]+1; break; } } f[i]=rf; } f[1]=1; for(int i=1;i<N;i++) f[i]+=f[i-1]; int T; for(scanf("%d",&T);T--;) { int n,m,ans=0; scanf("%d%d",&n,&m); for(int i=1,t,p,q;i<=n&&i<=m;i=t+1) { p=n/i,q=m/i,t=std::min(n/p,m/q); ans+=(f[t]-f[i-1])*p*(p+1)*q*(q+1)>>2; } printf("%d\n",ans&0x3fffffff); } } ``` [1]: /usr/uploads/2017/02/3245901942.jpg [2]: /usr/uploads/2017/02/1279320617.png
BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡 February 20, 2017 ##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 对于所有数据，1<=n<=100000, 1<=c<=10。 对于15%的数据，n<=2000。 另有5%的数据，所有空地都至多与两个空地相邻。 另有5%的数据，除一块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。 另有5%的数据，除某两块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。 ###Solution 考虑一条从u到v的路径上的字符串，如果在两端不断加节点，一定可以扩充成一条两个度数为1的节点间的路径上的子串。 那么显然有一种方法是把20个节点两两间的字符串建成广义SAM，然后直接统计，但是这样时间、内存都会超。 建广义SAM时，每次会把last设为初始节点，那么对于这道题，也可以类似优化。 把每个度数为1的节点作为根dfs，每次dfs时记下当前last，然后在处理完一棵子树后还原last。 ###Code ```c++ #define _GLIBCXX_IOSTREAM #include<bits/stdc++.h> typedef long long ll; #define N 2000010 struct node { int ma,inc;ll cnt; node*link,*nxt[10]; }pool[N*2],*pm=pool+1,*start=pool; namespace _A{node*lst,*cur,*p,*q,*sq;} void add(int t) { using namespace _A; cur=pm++; cur->ma=lst->ma+1; for(p=lst;p&&!p->nxt[t];p=p->link)p->nxt[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;i<=n;i++) scanf("%d",c+i); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); deg[x]++; deg[y]++; add(x,y); add(y,x); } for(int i=1;i<=n;i++)if(deg[i]==1) _A::lst=start,dfs(i,0); for(node*i=pool;i<pm;i++) for(int j=0;j<10;j++)if(i->nxt[j])i->nxt[j]->inc++; int qe=0; for(node*i=pool;i<pm;i++) if(!i->inc)i->inc=1e9,q[qe++]=i; for(int i=0;i<qe;i++) for(int j=0;j<10;j++)if(q[i]->nxt[j])if(!--q[i]->nxt[j]->inc) q[i]->nxt[j]->inc=1e9,q[qe++]=q[i]->nxt[j]; for(int i=qe-1;~i;i--) { for(int j=0;j<10;j++)if(q[i]->nxt[j])q[i]->cnt+=q[i]->nxt[j]->cnt; q[i]->cnt++; } printf("%lld",start->cnt-1); } ```
BZOJ 3160: 万径人踪灭 January 20, 2017 ###Description 略。见[BZOJ3160][1] ###Solution 对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者manacher可以得出 考虑以每个位置为中心的对称元素对个数f[i]，那么i位置对答案的贡献是$$2^{f[i]}-1$$ 如果把a视为1，b视为-1，然后把原串长度\*4，卷积，那么以i为中心的元素对如果相同，则贡献1，否则贡献-1 ###Code ```c++ #include<bits/stdc++.h> typedef double lf; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) inline int mod(int x,int y){if(x>=y)return x-y;return x;} #define N 524288 struct num { lf r,i; num(){r=i=0;} num(lf x){r=x,i=0;} num(lf x,lf y){r=x,i=y;} num(const num &x){r=x.r,i=x.i;} inline num& operator +=(const num &x){r+=x.r,i+=x.i;} inline num& operator -=(const num &x){r-=x.r,i-=x.i;} inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;} inline num operator +(const num &x){num t=*this;t+=x;return t;} inline num operator -(const num &x){num t=*this;t-=x;return t;} inline num operator *(const num &x){num t=*this;t*=x;return t;} }; int id[N]; num tx[N],mf[N]; inline void init_id(int y) { fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1; } #define idft(a,b) dft(a,b,1) inline void dft(num *s,int n,bool II=0) { fo0(i,1<<n)tx[i]=s[id[i]]; fo1(p,n) { lf tmp=M_PI*2/(1<<p); if(II)tmp=-tmp; num t0(1),t1(cos(tmp),sin(tmp)); fo0(i,1<<p-1)mf[i]=t0,t0*=t1; num X,Y; for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir) { X=tx[i|j],Y=tx[i|j|ir]*mf[j]; tx[i|j]=X+Y,tx[i|j|ir]=X-Y; } } fo0(i,1<<n)s[i]=tx[i]; } #define N2 100010 struct node { int len,cnt; node *nxt[2],*fail; }t[N2+2],*tm=t+2; inline void build(char *s,int n) { t[0].len=0,t[1].len=-1; node *cur=t+1,*tmp,*t2; t[0].fail=t+1; for(int i=0;i<n;i++) { char u=s[i]-'a'; for(;s[i]!=s[i-1-cur->len];cur=cur->fail); if(cur->nxt[u]) cur=cur->nxt[u],cur->cnt++; else { tmp=cur->nxt[u]=tm++; tmp->len=cur->len+2; tmp->cnt=1; if(tmp->len==1) tmp->fail=t; else { for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail); tmp->fail=t2->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<<(y+1))<n*4)y++;y++; fo0(i,n)p[i]=s[i]=='a'?1:-1; init_id(y); dft(p,y); fo0(i,1<<y)p[i]*=p[i]; idft(p,y); lf t=1.0/(1<<y); int ans=0; fo0(i,n*2-1) { int cnt=round(p[i].r*t); cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2; ans=mod(ans+po[cnt],P); } build(s,n); count(); printf("%d",mod(ans+P-cnt(),P)); } ``` [1]: http://www.lydsy.com/JudgeOnline/problem.php?id=3160
BZOJ 2989: 数列 & 4170: 极光 January 8, 2017 ###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)<=k。因为可持久化数据结构的流行，询问不仅要考虑当前数列，还要考虑任意历史版本，即统计任意位置上出现过的任意数值与当前的a[x]的graze值<=k的对数。（某位置多次修改为同样的数值，按多次统计） ###Input 第1行两个整数n,q。分别表示数列长度和操作数。 第2行n个正整数，代表初始数列。 第3--q+2行每行一个操作。 ###Output 对于每次询问操作，输出一个非负整数表示答案 ###Sample Input 3 5 2 4 3 Query 2 2 Modify 1 3 Query 2 2 Modify 1 2 Query 1 1 ###Sample Output 2 3 3 ###HINT N<=60000 修改操作数<=40000 询问<=60000 Max{a[i]}含修改<=100000 ###Solution 这道题其实是维护两种操作，向平面上加点，查询菱形内点数 把(x,y)变为(x+y,x-y)，菱形就变成了正方形 假设某个询问是以(x0,y0)为中心，边长为2k的正方形，那么可以拆成两个，一个是x>=x0-k且x<=x0+k且y<=y0+k的点数，另一个是x>=x0-k且x<=x0+k且y<y0-k的点数，把两个询问做差就和原询问相同 那么可以CDQ分治，按y排序，x用树状数组维护 ###Code ```c++ #include<bits/stdc++.h> using namespace std; int n,m,s[60001],ans[60000],ac,qc,mx; struct query { int x,y,k,id;char op; }q[230000],tmp[230000]; inline void add(int x,int y){q[qc].x=x+y,q[qc].y=x-y,qc++,mx=max(mx,x+y);} int p[160001]; inline void pl(int x){for(;x<=mx;x+=x&-x)p[x]++;} inline int qr(int x){if(x<=0)return 0;int r=0;for(x=min(x,mx);x;x^=x&-x)r+=p[x];return r;} inline void cl(int x){for(;x<=mx;x+=x&-x)p[x]=0;} void work(int l,int r) { if(l==r)return; int mid=(l+r)>>1; work(l,mid),work(mid+1,r); int i1=l,i2=mid+1,ti=l; for(;i2<=r;tmp[ti++]=q[i2++]) { for(;i1<=mid&&q[i1].y<=q[i2].y;tmp[ti++]=q[i1++]) if(!q[i1].op)pl(q[i1].x); if(q[i2].op) { if(q[i2].op==1) ans[q[i2].id]+=qr(q[i2].x+q[i2].k)-qr(q[i2].x-q[i2].k-1); else ans[q[i2].id]+=qr(q[i2].x-q[i2].k-1)-qr(q[i2].x+q[i2].k); } } for(;i1<=mid;tmp[ti++]=q[i1++]); for(i1=l;i1<=mid;i1++)if(!q[i1].op)cl(q[i1].x); for(i1=l;i1<=r;i1++)q[i1]=tmp[i1]; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",s+i),add(i,s[i]); char tmp[10];int a,b; while(m--) { scanf("%s%d%d",tmp,&a,&b); if(tmp[0]=='M') add(a,s[a]=b); else { int x=a+s[a],y=a-s[a]; q[qc].x=x,q[qc].y=y+b,q[qc].k=b,q[qc].id=ac,q[qc].op=1,qc++; q[qc].x=x,q[qc].y=y-b-1,q[qc].k=b,q[qc].id=ac,q[qc].op=2,qc++; ac++; } } work(0,qc-1); for(int i=0;i<ac;i++) printf("%d\n",ans[i]); } ```
BZOJ 4750: 密码安全 January 1, 2017 ###Description 有些人在社交网络中使用过许多的密码，我们通过将各种形式的信息转化为 01 信号，再转化为整数，可以将这个人在一段时间内使用过的密码视为一个长度为 n 的非负整数序列 A_1,A_2,...,A_n 。一个人相邻几次在社交网络中使用的密码很有可能是类似的，这使得密码并不是足够安全。为了检验某些人在某些时间段内是否可能受到不安全的影响，我们需要计算上述序列的复杂程度。 ![aa.jpg][1] 的值，这将作为我们评估密码复杂程度的一个部分。由于答案可能很大，你只需要给出答案对10^9+61 取模的值即可。 ###Input 第一行包含一个正整数 T ，表示有 T 组测试数据。 接下来依次给出每组测试数据。对于每组测试数据： 第一行包含一个正整数 n 。 第二行包含 n 个非负整数，表示 A_1,A_2,?,A_n 。 保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。 100% 的数据满足：1≤T≤200,1≤n≤10^5,1≤∑n≤10^6,0≤A_i≤10^9 ###Output 对于每组数据输出一行，包含一个整数，表示答案对10^9+61 取模的值。 ###Sample Input 3 1 61 5 1 2 3 4 5 5 10187 17517 24636 19706 18756 ###Sample Output 3721 148 821283048 ###Solution 单调栈扫一遍得到以每个数为最大值的区间，然后按位记前缀xor和的前缀和，对每个数分别统计答案 ###Code ```c++ #include<bits/stdc++.h> #define P 1000000061 int s[100001],S[100001],l[100001],r[100001],G[100010],*C=G+9; int main() { int T;for(scanf("%d",&T);T--;) { int n,m=0,i,j,t,p,A=0; scanf("%d",&n);s[n]=2e9; for(i=0;i<n;i++)scanf("%d",s+i); for(i=0;i<=n;i++) { while(m&&s[i]>=s[S[m-1]])r[S[--m]]=i-1; l[i]=m?S[m-1]+1:0,S[m++]=i; } for(j=0;j<30;j++) { for(i=t=p=0;i<n;i++)C[i]=t+=p^=s[i]>>j&1; for(i=0;i<n;i++) { t=C[i-1]-C[l[i]-2],p=C[r[i]]-C[i-1]; A=(((1ll*t*(r[i]-i+1-p)+1ll*p*(i-l[i]+1-t))%P<<j)%P*s[i]+A)%P; } } printf("%d\n",A); } } ``` [1]: /usr/uploads/2017/01/1896004125.jpg
BZOJ 2958&3269: 序列染色 December 26, 2016 ###Description 给出一个长度为N由B、W、X三种字符组成的字符串S，你需要把每一个X染成B或W中的一个。 对于给出的K，问有多少种染色方式使得存在整数a,b,c,d使得: 1<=a<=b<c<=d<=N Sa,Sa+1,...,Sb均为B Sc,Sc+1,...,Sd均为W 其中b=a+K-1,d=c+K-1 由于方法可能很多，因此只需要输出最后的答案对109+7取模的结果。 ###Input 第一行两个正整数N,K 第二行一个长度为N的字符串S ###Output 一行一个整数表示答案%(109+7)。 ###Sample Input 5 2 XXXXX ###Sample Output 4 ###Solution 首先搞出B和W的前缀个数，那么可以O(1)判某段区间能否为B或W 然而这样对于超过K个的会算重 对于连续的B和W，考虑用最后K个计算，则不会算重（可以在序列最后加一个X，更好写） 状态可以设计成f[i][j][k]表示考虑前i位，状态为j，这一位选了k，j为0,1,2分别代表BW都没有，只有B，BW都有 转移看代码 ###Code ```c++ #include<bits/stdc++.h> #define mod 1000000007 int n,k,bp[1000010],wp[1000010],f[1000010][3][2]; char s[1000010]; int main() { scanf("%d%d%s",&n,&k,s+1); s[++n]='X'; for(int i=1;i<=n;i++) { bp[i]=bp[i-1]+(s[i]=='B'); wp[i]=wp[i-1]+(s[i]=='W'); } f[0][0][0]=1; for(int i=1;i<=n;i++) { if(s[i]=='B'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(s[i]=='W'||s[i]=='X') for(int j=0;j<3;j++)f[i][j][1]=(f[i-1][j][0]+f[i-1][j][1])%mod; if(i<=k)continue; if((s[i]=='B'||s[i]=='X')&&!(bp[i-1]-bp[i-k-1])) { f[i][2][0]=(f[i][2][0]+f[i-k][1][1])%mod; f[i][1][0]=(f[i][1][0]-f[i-k][1][1])%mod; } if((s[i]=='W'||s[i]=='X')&&!(wp[i-1]-wp[i-k-1])) { f[i][1][1]=(f[i][1][1]+f[i-k][0][0])%mod; f[i][0][1]=(f[i][0][1]-f[i-k][0][0])%mod; } } int ans=f[n][2][0]; if(ans<0)ans+=mod; printf("%d\n",ans); } ```
BZOJ 4398: 福慧双修 December 26, 2016 ###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<bits/stdc++.h> #define mp(a,b) std::make_pair(a,b) int n,p[40001],dis[40001]; bool vis[40001]; std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >, std::greater<std::pair<int,int> > >q; 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<m;i++) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); add(i*2+1,a,b,c); add(i*2+2,b,a,d); } int ans=0x7fffffff; for(int i=1;i<=n;i<<=1) { yjq(i,i,ans); yjq(i,0,ans); } printf("%d",ans); } ```
BZOJ 2432: [Noi2011]兔农 December 20, 2016 ###Description 农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？ 聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。 ###Input 输入一行，包含三个正整数n, k, p。 ###Output 输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。 ###Sample Input 6 7 100 ###Sample Output 7 ###Solution 按模k余数写出数列，则为 1,1,...,a,0, a,a,...,b,0, b,b,...,c,0, ... 这个数列最后有可能每一排首项循环，也有可能不再出现0 每次求a的逆元，则其在fib数列中首次出现位置就是a后面下一个0的位置，如果没有0特判 ###Code ```c++ #include<bits/stdc++.h> typedef long long ll; #define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++) #define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++) #define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) void exgcd(int a,int b,int &x,int &y){if(b)exgcd(b,a%b,y,x),y-=(a/b)*x;else x=1,y=0;} ll n; int k,p,pos[1000000],f[6000010]={0,1,1},p2[1000000]; struct mat { int a[3][3]; inline void operator *=(mat x) { ll t[3][3];memset(t,0,sizeof(t)); fo0(i,3)fo0(j,3)fo0(k,3)t[i][k]+=(ll)a[i][j]*x.a[j][k]; fo0(i,3)fo0(j,3)a[i][j]=t[i][j]%p; } inline mat operator *(mat x) { mat r=*this;r*=x;return r; } }; mat pow(mat a,ll p) { mat r=(mat){1,0,0,0,1,0,0,0,1}; for(;p;p>>=1,a*=a)if(p&1)r*=a; return r; } struct data { int st,len;mat x; }s[1000001]; inline mat get(ll n,int tt) { mat r=(mat){1,0,0,0,1,0,0,0,1}; if(!n)return r; for(;n>=s[tt].len;n-=s[tt++].len)r*=s[tt].x; return r*pow((mat){0,1,0,1,1,0,0,0,1},n); } int main() { scanf("%lld%d%d",&n,&k,&p); for(int i=3;;i++) { f[i]=f[i-1]+f[i-2]; if(f[i]>=k)f[i]-=k; if(!pos[f[i]])pos[f[i]]=i; if(f[i]==1&&f[i-1]==0)break; } int ns=1,sc=1; for(;!p2[ns];sc++) { s[sc].st=ns; p2[ns]=sc; int t1,t2; exgcd(k,ns,t1,t2); if(t2<0)t2+=k; t1=pos[t2]; if((ll)ns*t2%k!=1||!t1)break; s[sc].len=t1; s[sc].x=pow((mat){0,1,0,1,1,0,0,0,1},t1-1)*(mat){0,1,0,1,1,0,0,-1,1}; ns=(ll)ns*f[t1-1]%k; } mat bfm=(mat){1,0,0,0,1,0,0,0,1},lpm=(mat){1,0,0,0,1,0,0,0,1},ans=(mat){1,0,0,0,1,0,0,0,1}; ll bf=0,lp=0; fo1(i,p2[ns]-1)bf+=s[i].len,bfm*=s[i].x; fo(i,p2[ns],sc-1)lp+=s[i].len,lpm*=s[i].x; if(!lp)lp=1,lpm=(mat){0,1,0,1,1,0,0,0,1}; if(n<bf) { ans*=get(n,1); } else { ans*=bfm;n-=bf; ans*=pow(lpm,n/lp); ans*=get(n%lp,p2[ns]); } int a1=ans.a[0][1]+ans.a[2][1]; while(a1>=p)a1-=p;while(a1<0)a1+=p; printf("%d\n",a1); } ```