ZigZagK的博客 - 奇技淫巧们
type: channel
link: https://zigzagk.top/tag/%E5%A5%87%E6%8A%80%E6%B7%AB%E5%B7%A7%E4%BB%AC/
items: [离线+bitset维护传递闭包+卡空间]2022“杭电杯”中国大学生算法设计超级联赛（3）10【Range Reachability Query】题解
items: [矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
items: 数据结构水题选讲(By AwD)部分题解
items: CodeChef March Challenge 2019 Division 2
items: [奇技淫巧]LOJ152【乘法逆元 2】题解
items: [FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
items: [离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
items: [Min-Max容斥+树上解方程]LOJ2542(PKUWC2018)【随机游走】题解
items: [线性筛+启发式分裂]NWERC2017F【Factor-Free Tree】题解
items: [二分]Codeforces1059D【Nature Reserve】题解

[离线+bitset维护传递闭包+卡空间]2022“杭电杯”中国大学生算法设计超级联赛（3）10【Range Reachability Query】题解
type: item
date: 2022-07-29T13:09:25+08:00
description: 题目概述HDU7171解题报告题目保证了DAG，所以是个DAG上的传递闭包问题，考虑用bitset做。定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的 $[l_i,r_i]$ 边从 $u_j$ 走到 $i$ 点，用bitset记录。然后做拓扑，对于 $i$ 号边 $x_i\to y_i$ ，则 $f_{y_i}=f_{y_i}\cup(f_{x_i}\cap S_i)$ ，其中 $S_i$ 表示包含 $i$ 号边的询问集合，可以通过扫描线处理。由于 $m$ 比较大恭喜我们成功炸空间了，类似这题，我们想办法把空间除掉个常数，因此我们每隔 $4$ 个扫描线中的点才记录一次bitset，然后查询时再花 $4$ 次补全 $S_i$ ，这样就不会炸空间了。示例程序#include<cstdio> #include<cctype> #include<bitset> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=50000,maxm=100000,maxq=50000,maxs=maxq<<1; int te,n,m,Q,X[maxm+5],Y[maxm+5]; int U[maxq+5],V[maxq+5],L[maxq+5],R[maxq+5]; int E,D[maxn+5],lnk[maxn+5],nxt[maxm+5],ID[maxm+5],to[maxm+5]; int cnt;pair<int,int> s[maxs+5]; int que[maxn+5]; bitset<maxq> S[(maxs>>2)+5],f[maxn+5],now; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Add(int x,int y,int z) {to[++E]=y;ID[E]=z;nxt[E]=lnk[x];lnk[x]=E;} int Find(int x){ int L=0,R=cnt-1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) s[mid].fr<=x?L=mid+1:R=mid-1; return R; } int main(){ for (readi(te);te;te--){ readi(n);readi(m);readi(Q); E=0;for (int i=1;i<=n;i++) lnk[i]=D[i]=0,f[i]=0; for (int i=1,x,y;i<=m;i++) readi(X[i]),readi(Y[i]),Add(X[i],Y[i],i),D[Y[i]]++; cnt=0; for (int i=0;i<Q;i++){ readi(U[i]);readi(V[i]);readi(L[i]);readi(R[i]); s[cnt++]=mp(L[i],i);if (R[i]<m) s[cnt++]=mp(R[i]+1,i); f[U[i]][i]=1; } sort(s,s+cnt); S[0]=0; for (int i=0;i<cnt;i++){ if (!(i&3)) S[(i>>2)+1]=S[i>>2]; S[(i>>2)+1].flip(s[i].sc); } int Head=0,Tail=0; for (int i=1;i<=n;i++) if (!D[i]) que[++Tail]=i; while (Head!=Tail) for (int x=que[++Head],j=lnk[x];j;j=nxt[j]){ int pos=ID[j],k=Fin…

[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
type: item
date: 2021-08-05T18:51:00+08:00
description: 题目概述Starch Cat解题报告正解是猫树，但是我不会，所以我选择黑科技。首先我们能想到一个比较暴力的做法，每次询问 $x,y$ 路径上的最大独立集，就是求 $x\to LCA(x,y),y\to LCA(x,y)$ 的两个最大独立集，然后在 $LCA$ 处讨论一下。定义 $f_{i,0/1}$ 表示 $i$ 点不选/选的最大独立集，然后考虑 $x\to fa_x$ 的DP：$$ f_{fa_x,0}=\max\{f_{x,0},f_{x,1}\}\\ f_{fa_x,1}=f_{x,0}+a_{fa_x} $$这可以用矩阵维护（当然，矩乘定义是 $c_{i,j}=\max_{k}\{a_{i,k}+b_{k,j}\}$ ）：$$ \begin{bmatrix}f_{x,0}&f_{x,1}\end{bmatrix}\begin{bmatrix}0&a_{fa_x}\\0&-\infty\end{bmatrix}=\begin{bmatrix}f_{fa_x,0}&f_{fa_x,1}\end{bmatrix} $$令 $x$ 的矩阵为 $\begin{bmatrix}0&a_{fa_x}\\0&-\infty\end{bmatrix}$ ，那么求出 $x\to LCA(x,y),y\to LCA(x,y)$​ 路径上矩阵的乘积就可以知道DP的值。所以暴力的做法就很显然了：用倍增求出矩阵乘积即可。但是这道题数据范围太大，倍增求LCA的做法复杂度稳定太大了，所以过不了。倍增复杂度太大，我们就考虑常数小很多的树链剖分，但是这样就无法维护ST表了（ST表有重复部分），接下来利用黑科技不重叠ST表来维护区间矩阵乘积就行了。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,LOG=19,maxs=1<<LOG,maxm=maxn<<1,MOD=998244353; int n,m,seed,a[maxn+5],dep[maxn+5],si[maxn+5],fa[maxn+5]; int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5]; int dfn,Lt[maxn+5],Rt[maxn+5],SH[maxn+5],top[maxn+5],lg[maxs+5]; struct Matrix{ LL s[2][2]; void build(LL a,LL b,LL c,LL d) {s[0][0]=a;s[0][1]=b;s[1][0]=c;s[1][1]=d;} void clear() {for (int i=0;i<2;i++) for (int j=0;j<2;j++) s[i][j]=-(1e18);} void unit() {clear();for (int i=0;i<2;i++) s[i][i]=0;} }; Matrix M[maxn+5],A[LOG+1][maxn+5],B[LOG+1][maxn+5]; struct Rand{ unsigned int n,seed; Rand(unsigned int n,unsigned int seed) :n(n),seed(seed){} int get(long long lastans){ seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return (seed^lastans)%n+1; } }; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Add(int x,int…

数据结构水题选讲(By AwD)部分题解
type: item
date: 2019-04-12T09:42:00+08:00
description: 课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $log$ 了，每次再用 $O(\sqrt{n+K})$ 来询问。没有找到原题，代码咕咕咕QAQ……K 小值查询把集合分成三部分：$[1,k],(k,2k],(2k,+\infty)$ ，将第二部分提取出来暴力减去 $k$ 后重新加入集合，此时只剩下两部分 $[1,k],(2k,+\infty)$ ，后一部分减去 $k$ 后依然在第一部分后面，所以可以打tag。因为第二部分至少除以 $2$ ，所以复杂度 $O(nlog_2nlog_2k)$ 。操作均可以用Splay完成，好久没手写平衡树了……#include<cstdio> #include<algorithm> using namespace std; const int maxn=100000,maxt=5e6; int n,m; int len,ro,son[maxt+5][2],val[maxt+5],num[maxt+5],si[maxt+5],tag[maxt+5]; #define cmp(p,k) ((k)==val[p]?-1:(k)>val[p]) inline void Pushup(int p) {si[p]=si[son[p][0]]+num[p]+si[son[p][1]];} inline void Rotate(int &p,int d){ int t=son[p][d];son[p][d]=son[t][d^1];son[t][d^1]=p; Pushup(p);Pushup(t);p=t; } inline void Addtag(int p,int k) {if (!p) return;val[p]+=k;tag[p]+=k;} inline void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;} void Splay(int &p,int k){ int d=cmp(p,k);if (d<0) return;Pushdown(p);int &s=son[p][d],f=cmp(s,k); if (~f) Splay(son[s][f],k),d==f?Rotate(p,d):Rotate(s,f);Rotate(p,d); } void Insert(int &p,int k,int x=1){ if (!p) {p=++len;val[p]=k;num[p]=x;Pushup(p);return;}Pushdown(p); int d=cmp(p,k);if (~d) Insert(son[p][d],k,x); else num[p]+=x;Pushup(p); } int Askkth(int p,int k){ Pushdown(p);int ls=si[son[p][0]];if (ls<k&&k<=ls+num[p]) return val[p]; return k<=ls?Askkth(son[p][0],k):Askkth(son[p][1],k-ls-num[p]); } int Askpre(int p,int k){ if (!p) return -1;Pushdown(p);int now=-1;if (val[p]<k) now=val[p]; return k<=val[p]?max(now,Askpre(son[p][0],k)):max(now,Askpre(son[p][1],k)); } int Asksuf(int p,int k){ if (!p) return 2e9;Pushdown(p);int now=2e9;if (val[p]>k) now=val[p]; return k>=val[p]?min(now,Asksuf(son[p][1],k)):min(now,Asksuf(son[p][0],k)); } void Join(int p,int k){ if (!p) return;Pushdown(p);Insert(ro,val[p]-k,num[p]);Splay(ro,val[p]-k); Join(son[p][0],k);Join(son[p][1],k); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&…

CodeChef March Challenge 2019 Division 2
type: item
date: 2019-03-14T19:42:03+08:00
description: 像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。Chef and Number Game最优解只能是正负分两半。#include<cstdio> #include<algorithm> using namespace std; const int maxn=100000; int te,n,A,B; int main(){ freopen("CHNUM.in","r",stdin);freopen("CHNUM.out","w",stdout); for (scanf("%d",&te);te;te--){ scanf("%d",&n);A=B=0;for (int i=1,x;i<=n;i++) scanf("%d",&x),x>0?A++:B++; if (A<B) swap(A,B);B?printf("%d %d\n",A,B):printf("%d %d\n",A,A); }return 0; }Chef and a Beautiful Digit一旦存在一位 $i$ 使得 $a_i>a_{i+1}$ 或者 $a_i>d(i=n)$ ，就肯定会把 $a_i$ 删掉，所以不停地换就行了。#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxl=20; int te,D,a[maxl+5];LL n; inline int Find() {for (int i=1;i<=a[0];i++) if (a[i]>a[i+1]) return i;return -1;} int main(){ freopen("CHDIGER.in","r",stdin);freopen("CHDIGER.out","w",stdout); for (scanf("%d",&te);te;te--){ scanf("%lld%d",&n,&D);a[0]=0;do a[++a[0]]=n%10,n/=10; while (n);reverse(a+1,a+1+a[0]);a[a[0]+1]=D; for (int pos=Find();~pos;pos=Find()) {for (int i=pos;i<a[0];i++) a[i]=a[i+1];a[a[0]]=D;} for (int i=1;i<=a[0];i++) putchar(a[i]+48);puts(""); }return 0; }Chef got Recipes直接每次 $O(2^5)$ 维护。#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=100000,maxs=1<<5; int te,n,ID[256],num[maxs];LL ans; inline char getlow() {char ch=getchar();while (!islower(ch)) ch=getchar();return ch;} int main(){ freopen("JAIN.in","r",stdin);freopen("JAIN.out","w",stdout); ID['a']=0;ID['e']=1;ID['i']=2;ID['o']=3;ID['u']=4; for (scanf("%d",&te);te;te--){ scanf("%d",&n);for (int i=0;i<maxs;i++) num[i]=0;ans=0; for (int i=1;i<=n;i++){ int S=0;for (char ch=getlow();islower(ch);ch=getchar()) S|=1<<ID[ch]; ans+=num[S^maxs-1];for (int s=S;s;s=s-1&S) num[s]++;num[0]++; }printf("%lld\n",ans); }return 0; }Yet Again a Subarray Problem枚举左端点 $L​$ ，然后从左往右推 $R​$ ，按照题意模拟就行了……本来以为这道题会卡常的……就学了一下树状数组求第 $k$ 大，结果线段树随便过……树状数组求第 $k$ 大：从高位到低位检查，假设当前答案为 $ans$ ，那么第 $i$ 位加上去之后会多出 $(ans,ans+2^i]$ 这一块，即 $c[ans+2^i]$ ，检查加上去会不会大于等于 $k$ ，如果大于等于说明不能加这一位。代码超级短，但是不能处理值…

[奇技淫巧]LOJ152【乘法逆元 2】题解
type: item
date: 2019-03-11T17:01:02+08:00
description: 题目概述有 $n$ 个数 $a_i$ ，求每个数的逆元。解题报告$O(n)$ 求 $n$ 个数逆元？？？Orz WA自动机，感觉这个技巧非常有用，帮助我解决了CC的某道毒瘤题（CC比赛还没结束，就先鸽了）。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=5000000,MOD=1e9+7,PW=998244353; int n,a[maxn+5],s[maxn+5],sv[maxn+5],INV[maxn+5],ans; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);s[0]=1;for (int i=1;i<=n;i++) readi(a[i]),s[i]=(LL)s[i-1]*a[i]%MOD; sv[n]=Pow(s[n],MOD-2);for (int i=n-1;i;i--) sv[i]=(LL)sv[i+1]*a[i+1]%MOD; for (int i=1;i<=n;i++) INV[i]=(LL)sv[i]*s[i-1]%MOD; for (int i=n,pw=1;i;i--,pw=(LL)pw*PW%MOD) AMOD(ans,(LL)INV[i]*pw%MOD);printf("%d\n",ans);return 0; }

[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
type: item
date: 2019-02-27T20:44:04+08:00
description: 题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b$ ，求 $a_t$ 。解题报告令 $c[i]=b[count(i)]$ ，那么 $a_{t}=a_{t-1}*c$ （ $*$ 表示异或卷积），FWT裸题？但是模数可能是偶数？WTF？我们可以先将模数扩大 $n$ 倍，然后就可以在FWT的最后直接除以 $n$（考虑到模其实是减法，所以肯定有 $n​$ 这个因子）。但是这样会爆long long，所以要快速（慢速）乘。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL;typedef long double DB; const int maxm=20,maxn=1<<20; int n;LL t,MOD,a[maxn+5],b[maxm+5],c[maxn+5],cnt[maxn+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void AMOD(LL &x,LL tem) {if ((x+=tem)>=MOD) x-=MOD;} inline LL Mul(LL x,LL y) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;} inline LL Pow(LL w,LL b) {LL s;for (s=1;b;w=Mul(w,w),b>>=1) if (b&1) s=Mul(s,w);return s;} inline void FWT(LL *a,int n,int f){ for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++) {LL x=a[i+j],y=a[i+j+k];AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);} if (f<0) for (int i=0;i<=n;i++) a[i]/=n; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(t);readi(MOD);MOD*=(1<<n); for (int i=0;i<(1<<n);i++) readi(a[i]),a[i]%=MOD;for (int i=0;i<=n;i++) readi(b[i]),b[i]%=MOD; n=1<<n;for (int i=0;i<n;i++) c[i]=b[cnt[i]=cnt[i>>1]+(i&1)];FWT(a,n,1);FWT(c,n,1); for (int i=0;i<n;i++) a[i]=Mul(a[i],Pow(c[i],t));FWT(a,n,-1); for (int i=0;i<n;i++) printf("%lld\n",a[i]);return 0; }

[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
type: item
date: 2019-02-26T18:27:00+08:00
description: 题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊，所以我们来乱搞吧QAQ。把串倒过来，那么就是求后缀的最长公共前缀，这是后缀数组Height数组经典问题，如果询问 $[L,R]$ 满足 $x\in\{rank_i|L\le i\le R\}$ 且 $x-1\in\{rank_i|L\le i\le R\}$ 那么 $Height_x$ 就可以修正这个询问。因此把询问离线之后，通过合并Height数组（大的Height可以合并到相邻的小的Height），我们就可以得到一个 $O(nm)$ 算法。考虑从大到小枚举Height数组，这样我们就可以做到每个询问只修正一次，但是对于 $x$ 要怎么快速找到合法的询问？吃我bitset啦！我们先处理出 $S_i$ 表示符合 $i$ 的询问集合（差分），然后每次通过bitset的&操作就可以快速得到满足条件且还没有被修正过的询问集合，这样复杂度就变成了 $O({nm\over\omega})$ 。还有个黑科技，由于 $m=10^5$ 的时候会MLE，所以我们……做两次 $m=5\cdot10^4$ QAQ！示例程序#include<cstdio> #include<bitset> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int maxn=100000,maxm=50000,maxt=784; int n,Q,SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],h[maxn+5]; char s[maxn+5];int ID[maxn+5],Lg[23333],ans[maxm+5],fat[maxn+5]; #define pw(i) ((ULL)1<<(i)) struct Bitset{ ULL s[maxt];inline void Clear() {for (int i=0;i<maxt;i++) s[i]=0;} inline void Set(int i) {s[i/64]|=pw(i%64);} inline void Unset(int i) {Set(i);s[i/64]^=pw(i%64);} inline void operator &= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]&=a.s[i],s[i+1]&=a.s[i+1],s[i+2]&=a.s[i+2],s[i+3]&=a.s[i+3]; } inline void operator |= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]|=a.s[i],s[i+1]|=a.s[i+1],s[i+2]|=a.s[i+2],s[i+3]|=a.s[i+3]; } inline void operator ^= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]^=a.s[i],s[i+1]^=a.s[i+1],s[i+2]^=a.s[i+2],s[i+3]^=a.s[i+3]; } inline int Next(int x){ int A=x/64,B=x%64;ULL now;if (B<63&&(now=s[A]&~(pw(B+1)-1))) return A*64+Lg[(now&-now)%23333]; for (int i=A+1;i<maxt;i++) if (s[i]) return i*64+Lg[(s[i]&-s[i])%23333];return 2e9; } }q[maxn+5]; inline void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i]; } inline void Make(char *s,int n){ int m=255;for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;Sort(n,m); for (int p=0,k=1;p<n;k<<=1,m=p){ p=0;for (int i=n-k+1…

[Min-Max容斥+树上解方程]LOJ2542(PKUWC2018)【随机游走】题解
type: item
date: 2019-01-31T23:00:00+08:00
description: 题目概述有一棵树，刚开始你在 $X​$ ，每次随机走到相邻的点。有 $q​$ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。解题报告不难想到Min-Max容斥，令 $min(S)$ 表示第一次走到 $S$ 集合中的点的期望时间。然后我可能是智障，我刚开始认为 $min(S)=min\{f(i)|i\in S\}$ ，其中 $f(i)$ 表示 $X$ 第一次走到 $i$ 的期望时间（用高斯消元求解），这显然是错的，因为走到 $i$ 的途中可能就已经经过其他在 $S$ 中的点导致违法。那么正确的定义应该加上一维：$f(i,S)$ 表示从 $i$ 出发第一次到达 $S$ 这个集合中的点的期望时间，则可以列出 $n$ 个方程来求解：$$ f(i,S)=\begin{cases}{1\over d_i}\sum_{(i,j)\in E}f(j,S)+1&i\not\in S\\0&i\in S\end{cases} $$这样是 $O(2^nn^3)$ 的，法老表示可以用奇技淫巧搞过去……我没有深入探究过……反正朴素消元是TLE的……接下来上套路：在树上的高斯消元可以变成 $f(x)=a_xf(fa_x)+b_x$ 的形式，这是怎么想到的呢？考虑在树上的方程：$$ f(x,S)=\begin{cases}{1\over d_x}(\sum f(son,S)+f(fa_x,S))+1&x\not\in S,\text{x is not leaf}\\{1\over d_x}f(fa_x,S)+1&x\not\in S,\text{x is leaf}\\0&x\in S\end{cases} $$从叶子往上代入，移项之后发现每次就只剩了父亲节点，并没有儿子节点，于是可以写成 $f(x)=a_xf(fa_x)+b_x$ 。所以对于 $f(x,S)$ ：$$ f(x,S)={1\over d_x}f(fa_x,S)+{1\over d_x}f(x,S)\sum a_{son}+{1\over d_x}\sum b_{son}+1\\ f(x,S)={1\over d_x(1-{1\over d_x}\sum a_{son})}f(fa_x,S)+{1\over d_x(1-{1\over d_x}\sum a_{son})}\sum b_{son}+{1\over1-{1\over d_x}\sum a_{son}} $$由于 $f(X,S)$ 并没有父亲所以 $min(S)=f(X,S)=b_X$ ，就可以求出 $max(S)$ 了。示例程序#include<cstdio> #include<algorithm> using namespace std; typedef long long LL;typedef long double DB; const int maxn=18,maxs=1<<maxn,MOD=998244353; int n,te,st,d[maxn+5],f[maxn+5],g[maxn+5],ans[maxs],cnt[maxs]; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5]; #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) inline int Inv(int x) {int INV=1;while (x>1) INV=(LL)INV*(MOD-MOD/x)%MOD,x=MOD%x;return INV;} inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline void Solve(int s,int x,int pre=0,int A=0,int B=0){ for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Solve(s,son[j],x),AMOD(A,g[son[j]]),AMOD(B,f[son[j]]); if (s>>x-1&1) f[x]=g[x]=0; else{ int INV=Inv(d[x]);A=Inv((MOD+1-(LL)A*INV%MOD)%MOD);B=(LL)B*INV%MOD;AMOD(B,1); g[x]=(LL)INV*A%MOD;f[x]=(LL)B*A%MOD; } } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d%d",&n,&te,&st); for (int i=1,x,…

[线性筛+启发式分裂]NWERC2017F【Factor-Free Tree】题解
type: item
date: 2018-11-07T16:48:27+08:00
description: 题目概述如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。解题报告首先有结论：如果 $[L,R]$ 可以变成FFT，那么随便选一个合法的作为根都是可以的，画画中序遍历发现挺显然的……问题是怎么求出每个点是否与 $[L,R]$ 中其他点均互质，套路：$i$ 质因数分解之后每个因子最近出现的位置中最近的位置就是 $i$ 能到达的最远位置。至于质因数分解可以用线性筛筛出最小素因子。但是就算这样，每次也不可能暴力找一个合法的根？你错了……就是可以暴力找，只要从两端一起开始找就可以，为什么呢？由于是从两端开始找，所以近的一段会先遇到合法的根，次数是合法的根到端点的距离，这可以看作小的块往大的块合并，是启发式合并的逆过程（启发式分裂？），所以复杂度是正常的。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; const int maxn=1000000,maxa=10000000,maxp=664579; int n,a[maxn+5],pre[maxn+5],nxt[maxn+5],pos[maxp+5],fa[maxn+5]; int D[maxa+5],p[maxp+5];bool pri[maxa+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void Make(){ for (int i=2;i<=maxa;i++){ if (!pri[i]) p[++p[0]]=i,D[i]=p[0]; for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++) {D[t]=D[i];pri[t]=true;if (!(i%p[j])) break;} } } bool Dfs(int L,int R,int p=0){ if (L>R) return true; for (int l=L,r=R;l<=r;l++,r--){ if (R<=nxt[l]&&pre[l]<=L) return fa[l]=p,Dfs(L,l-1,l)&&Dfs(l+1,R,l); if (R<=nxt[r]&&pre[r]<=L) return fa[r]=p,Dfs(L,r-1,r)&&Dfs(r+1,R,r); }return false; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); Make();readi(n);for (int i=1;i<=n;i++) readi(a[i]); for (int i=1;i<=p[0];i++) pos[i]=-1; for (int i=1;i<=n;i++){ pre[i]=1;for (int x=a[i];x>1;x/=p[D[x]]) pre[i]=max(pre[i],pos[D[x]]+1); for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i; } for (int i=1;i<=p[0];i++) pos[i]=n+1; for (int i=n;i;i--){ nxt[i]=n;for (int x=a[i];x>1;x/=p[D[x]]) nxt[i]=min(nxt[i],pos[D[x]]-1); for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i; } if (Dfs(1,n)) {for (int i=1,fst=true;i<=n;i++) fst?fst=false:putchar…

[二分]Codeforces1059D【Nature Reserve】题解
type: item
date: 2018-10-08T21:30:14+08:00
description: 题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定 $x$ 的范围，如果 $x$ 有取值那么就验证成功。因为精度要求 $6$ 位，并且 $r$ 的范围有 $10^{15}$ ，long double精度也不够导致二分停不下来，所以要用奇技淫巧，比如__float128 或者做个 $100$ 次就停止。亲测都可过……示例程序#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long double DB; const int maxn=100000; int n,x[maxn+5],y[maxn+5]; inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-10) return 0;return a<b?-1:1;} inline bool check(DB r,DB A=-9e18,DB B=9e18){ for (int i=1;i<=n;i++){ if (fcmp(r*2*y[i]-(DB)y[i]*y[i],0)<0) return false; A=max(A,-sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]);B=min(B,sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]); }return fcmp(A,B)<=0; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d",&n);bool A=true,B=true; for (int i=1;i<=n;i++) {scanf("%d%d",&x[i],&y[i]);if (y[i]<0) A=false;if (y[i]>0) B=false;} if (!A&&!B) return puts("-1"),0;if (B) for (int i=1;i<=n;i++) y[i]=-y[i]; DB L=0,R=1e15,mid;for (int t=1;t<=100;t++) check(mid=(L+R)/2)?R=mid:L=mid; if (!fcmp(R,1e15)) return puts("-1"),0;printf("%.7f\n",(double)R);return 0; }