ZigZagK的博客 - 2018年5月
type: channel
link: https://zigzagk.top/2018/05/
description: Never give up fighting!
items: [随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解
items: [计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解
items: [随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解
items: [随机]BZOJ5365(2018年5月赛)【回文树】题解
items: [线段树动态开点]BZOJ5358(Lydsy1805月赛)【口算训练】题解
items: NTT
items: [矩阵乘法]BZOJ4417(Shoi2013)【超级跳马】题解
items: [主席树+平衡树]BZOJ4548【小奇的糖果】题解
items: [裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解
items: [SG函数]LOJ2126(HAOI2015)【数组游戏】题解

[随机+Trie]LOJ2313(HAOI2017)【供给侧改革】题解
type: item
date: 2018-05-30T20:49:00+08:00
description: 题目概述给出一个 $n$ 位随机 $01$ 串，定义 $data(L,R)=max\{LCP(Suf_i,Suf_j)|i\not=j,L\le i,j\le R\}$ 。给出 $m$ 个询问 $[L,R]$ ，求 $\sum_{i=L}^{R-1}data(i,R)$ 。解题报告随机 $01$ 串……粗略估计相同的概率为 $({1\over 2})^{len}{R-L+1\choose 2}$ ，那么 $len=50$ 的时候概率就很低了，所以假装 $LCP$ 最大只有 $50$ ，然后我就不会了。可以发现从 $R​$ 往前，$data(i,R)​$ 显然是递增的，所以我们可以记录 $pos_{R,j}​$ 表示 $R​$ 往前的第 $j​$ 个分段处，然后每次询问只需要 $O(50)​$ 回答。怎么构造 $pos$ ？两种方法：1.二分+哈希验证。2.从小到大求 $pos_R$ ，每次加入 $R$ 这个位置，用Trie更新长度为 $j$ 的配对的最晚出现时间 $MAX_j$ ，$pos_{R,j}=\begin{cases}MAX_j&\forall MAX_k<MAX_j,k>j\\0&\exists MAX_k>MAX_j,k>j\end{cases}$ 。示例程序#include<cstdio> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=100000,maxl=50,maxt=maxn*maxl; int n,te,pos[maxn+5][maxl+5];char s[maxn+5]; int si,son[maxt+5][2],lst[maxt+5],now[maxl+5]; inline void Insert(int L,int R){ for (int i=L,j=1,p=0;i<=R;i++,j++){ if (!son[p][s[i]-48]) son[p][s[i]-48]=++si; p=son[p][s[i]-48];now[j]=max(now[j],lst[p]);lst[p]=L; } } int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); scanf("%d%d%s",&n,&te,s+1); for (int i=1;i<=n;i++){ Insert(i,min(i+50,n));for (int j=1;j<=50;j++) pos[i][j]=now[j];pos[i][0]=i-1; for (int j=50,MAX=0;j;j--) if (MAX>pos[i][j]) pos[i][j]=0; else MAX=pos[i][j]; } for (int i=1;i<=te;i++){ int L,R,lst=0,ans=0;scanf("%d%d",&L,&R); for (int j=1;j<=50;j++) if (pos[R][j]) {if (pos[R][j]<L) break;ans+=(pos[R][lst]-pos[R][j])*lst;lst=j;} printf("%d\n",ans+(pos[R][lst]-L+1)*lst); } return 0; }

[计数]BZOJ5366(Lydsy1805月赛)【代码派对】题解
type: item
date: 2018-05-28T21:55:00+08:00
description: 题目概述有 $n$ 个矩阵，问多少三元组 $(i,j,k),i<j<k$ 满足三个矩阵至少有一个相交的格子。解题报告我怎么连计数题都不会……这种题目肯定要考虑枚举相交的格子来统计贡献，但是不可能枚举相交的矩阵，我们再观察一下就会发现只需要枚举相交矩阵的一个角就行了。然后开始疯狂分类讨论，只要按照一定顺序枚举所有方案并判断该方案是否可行就行了，我们先记录：$S_{1,i,j}$ ：左下角为 $(i,j)$ 的矩阵个数。$S_{2,i,j}$ ：左边界包含 $(i,j)$ 的矩阵个数（不含左下角）。$S_{3,i,j}$ ：下边界包含 $(i,j)$ 的矩阵个数（不含左下角）。$S_{4,i,j}$ ：包含 $(i,j)$ 的矩阵个数（不含左边界下边界）。这些用容斥和差分就可以 $O(1000^2)$ 求出来了，接下来列举所有情况（前面的数字表示选了几个），自己推去吧，我根本没想让你们看懂：[3S_1];[2S_1,S_2];[2S_1,S_3];[2S_1,S_4];[2S_2,S_1];[2S_2,S_3];[2S_3,S_1];[2S_3,S_2];[2S_4,S_1];[S_1,S_2,S_4];[S_1,S_2,S_4];[S_1,S_3,S_4];[S_2,S_3,S_4]示例程序#include<cstdio> #include<cctype> #include<cstring> using namespace std; typedef long long LL; const int maxn=100000,maxm=1000; int te,n,s[4][maxm+5][maxm+5];LL ans; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int readi(int &x){ int 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); } #define C2(x) ((LL)(x)*((x)-1)/2) #define C3(x) ((LL)(x)*((x)-1)*((x)-2)/6) int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); for (readi(te);te;te--,memset(s,0,sizeof(s)),ans=0){ for (int i=(readi(n),1);i<=n;i++){ int xl,yl,xr,yr;readi(xl);readi(yl);readi(xr);readi(yr); s[0][xr][yl]++;s[3][xl][yl+1]++;s[3][xl][yr+1]--;s[3][xr][yl+1]--;s[3][xr][yr+1]++; s[1][xl][yl]++;s[1][xr][yl]--;s[2][xr][yl+1]++;s[2][xr][yr+1]--; } for (int j=1;j<=1000;j++) for (int i=1;i<=1000;i++) s[1][i][j]+=s[1][i-1][j]; for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[2][i][j]+=s[2][i][j-1]; for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++) s[3][i][j]+=s[3][i-1][j]+s[3][i][j-1]-s[3][i-1][j-1]; for (int i=1;i<=1000;i++) for (int j=1;j<=1000;j++){ ans+=C3(s[0][i][j]); ans+=C2(s[0][i][j])*(s[1][i][j]+s[2][i][j]+s[3][i][j]); ans+=C2(s[1][i][j…

[随机+主席树二分]BZOJ5361(Lydsy1805月赛)【对称数】题解
type: item
date: 2018-05-28T12:48:00+08:00
description: 题目概述给出一棵 $n​$ 个节点的树，每个节点有权值，一条路径上的对称数定义为最小的出现次数为偶数（包括 $0​$ ）的数，现在给出 $m​$ 个询问 $(x,y)​$ 表示询问 $(x,y)​$ 路径上的对称数。解题报告奇数次偶数次想到异或，我们先给每个权值配对上一个随机数，然后求出路径上的异或值(主席树)，就可以得到这条路径上的权值信息。不过这样还是没法做，但是我们发现这样可以判断一段权值范围内是否均为奇数次。所以考虑二分 $mid$ ，验证 $[1,mid]$ 是否存在偶数次（不是均为奇数次）就行了。如果你用二分+主席树查询，效率为 $O(mlog_2^2n)$ ，然后你就会成功TLE……正确姿势是在主席树上二分，其实也不难理解，就是验证 $mid$ 然后往左走或者往右走，这样就是 $O(mlog_2n)$ 了。ps：有一种特殊数据：树退化成链，且链上权值涵盖所有权值，这样就会导致在主席树上无法查找到答案，所以主席树右边界要多开 $1$ ，没有注意到导致我WA了若干发TAT。示例程序#include<cstdio> #include<cctype> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int maxn=200000,maxa=200001,maxt=1e7,Log=18; int te,n,m,a[maxn+5],fa[maxn+5][Log+5],dep[maxn+5];ULL ha[maxa+5],pre[maxa+5]; int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5],lca; int len,ro[maxn+5],ls[maxt+5],rs[maxt+5];ULL sum[maxt+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int readi(int &x){ int 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 ULL Rand(){ static ULL now;now=((ULL)rand()<<48)+((ULL)rand()<<32)+((ULL)rand()<<16)+rand(); now+=((ULL)(rand()&1)<<47)+((ULL)(rand()&1)<<31)+((ULL)(rand()&1)<<15);return now; } #define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E #define newnode(l,r,s) (ls[len]=(l),rs[len]=(r),sum[len]=(s),len++) int Build(int L,int R){ int now=newnode(0,0,0);if (L==R) return now;int mid=L+(R-L>>1); ls[now]=Build(L,mid);rs[now]=Build(mid+1,R);return now; } int Insert(int p,int pos,ULL k,int l=1,int r=maxa){ int now=newnode(ls[p],rs[p],sum[p]^k);if (l==r) return now;int mid=l+(r-l>>1); if (pos<=mid) ls[now]=Insert(ls[p],pos,k,l,mid); else rs[now]=Insert(rs[p],pos,k,mid+1,r);return now; } int Find(int A,int B,ULL SA=0,ULL SB=0,int l=1,int r=…

[随机]BZOJ5365(2018年5月赛)【回文树】题解
type: item
date: 2018-05-27T18:45:00+08:00
description: 题目概述给你 $n$ 个点，每个点有一个 $[1,n]$ 的随机权值，问有多少回文路径。解题报告因为是随机的……所以你要有信仰，假装回文路径长度最多只有 $5$ 就行了。然后因为他只有 $3s$ 时限……你会TLE不止（小常数巨佬们当我没说）……我们再来理性分析一波：一个串是回文串的概率为 $({1\over n})^{len/2}$ ，当 $len=4$ 的时候概率就只有 $10^{-10}$ 了真棒 。所以我们只要考虑 $len\le 3$ 的情况就行了，瞎搞搞。ps：$n$ 非常小的时候最好还是 $O(n^2)$ 处理，但是BZOJ没卡我，不想管了XD……示例程序#include<cstdio> #include<cctype> #include<cstring> using namespace std; typedef unsigned long long ULL; const int maxn=100000,HASH=19260817; int te,n,a[maxn+5],tp;long long ans; int E,lnk[maxn+5],nxt[(maxn<<1)+5],son[(maxn<<1)+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int readi(int &x){ int tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc(); return (lst=='-'?x=-tot:x=tot),Eoln(ch); } #define Add(x,y) son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E int sum[HASH],stk[maxn+5]; inline void Insert(int x) {if (sum[x]) sum[x]++; else stk[++stk[0]]=x,sum[x]=1;} inline void Clear() {while (stk[0]) sum[stk[stk[0]--]]=0;} int main(){ freopen("H.in","r",stdin); freopen("H.out","w",stdout); for (readi(te);te;te--){ readi(n);for (int i=1;i<=n;i++) readi(a[i]); E=0;memset(lnk,0,sizeof(lnk));ans=n; for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x); for (int i=1;i<=n;i++,Clear()) for (int j=lnk[i];j;j=nxt[j]) ans+=sum[a[son[j]]],Insert(a[son[j]]); for (int i=1;i<=n;i++) for (int j=lnk[i];j;j=nxt[j],Clear()) if (a[i]==a[son[j]]&&i>son[j]){ ans++; for (int t=lnk[i];t;t=nxt[t]) if (son[t]!=son[j]) Insert(a[son[t]]); for (int t=lnk[son[j]];t;t=nxt[t]) if (son[t]!=i) ans+=sum[a[son[t]]]; } printf("%lld\n",ans); } return 0; }

[线段树动态开点]BZOJ5358(Lydsy1805月赛)【口算训练】题解
type: item
date: 2018-05-27T18:28:00+08:00
description: 题目概述给你 $\{a_n\}$ ，给出 $m$ 个询问 $l,r,d$ 表示询问 $a_l\times a_{l+1}\times\cdots\times a_r$ 是不是 $d$ 的倍数。解题报告签到题送温暖，你只需要质因数分解一下，然后线段树动态开点查询就行了。示例程序#include<cstdio> #include<cctype> #include<cstring> using namespace std; const int maxn=100000,maxa=100000,maxt=30000000; int te,n,m,p[maxa+5];bool pri[maxa+5]; int len,ro[maxa+5],ls[maxt+5],rs[maxt+5],sum[maxt+5]; inline void Make(){ pri[0]=pri[1]=true; for (int i=2;i<=maxa;i++){ if (!pri[i]) p[++p[0]]=i; for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++) if (i%p[j]) pri[t]=true; else {pri[t]=true;break;} } } #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int readi(int &x){ int tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<1)+(tot<<3)+(ch^48),ch=readc(); return (lst=='-'?x=-tot:x=tot),Eoln(ch); } #define newnode (ls[++len]=0,rs[len]=0,sum[len]=0,len) void Insert(int &p,int pos,int k,int l=1,int r=n){ if (!p) p=newnode;sum[p]+=k;if (l==r) return;int mid=l+(r-l>>1); if (pos<=mid) Insert(ls[p],pos,k,l,mid); else Insert(rs[p],pos,k,mid+1,r); } int Ask(int p,int L,int R,int l=1,int r=n){ if (!p||R<l||r<L) return 0;if (L<=l&&r<=R) return sum[p];int mid=l+(r-l>>1); return Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r); } inline void Div(int x,int pos){ for (int i=1,tot;i<=p[0]&&p[i]*p[i]<=x;i++) if (!(x%p[i])) {tot=0;while (!(x%p[i])) tot++,x/=p[i];Insert(ro[p[i]],pos,tot);} if (x>1) Insert(ro[x],pos,1); } inline bool check(int x,int L,int R){ for (int i=1,tot;i<=p[0]&&p[i]*p[i]<=x;i++) if (!(x%p[i])) {tot=0;while (!(x%p[i])) tot++,x/=p[i];if (Ask(ro[p[i]],L,R)<tot) return false;} if (x>1&&Ask(ro[x],L,R)<1) return false;return true; } int main(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); for (Make(),readi(te);te;te--){ readi(n);readi(m);len=0;memset(ro,0,sizeof(ro)); for (int i=1,x;i<=n;i++) readi(x),Div(x…

NTT
type: item
date: 2018-05-25T18:29:00+08:00
description: 快速数论变换(Fast Number-Theoretic Transform)，简称NTT(FNTT)。然而这货和FFT基本上一样，就是求 $A(x)B(x)$ ，只不过系数要对 $p$ 取模。原根如果 $g$ 满足 $g^{i}\not\equiv g^{j}(mod\ p),i\not=j$ ，那么称 $g$ 为模 $p$ 意义下的原根。也就是说 $g$ 的次幂能够不遗漏也不重复的取到 $0\sim p-1$ 的所有值，周期为 $\varphi(p)$ ，当 $p$ 为素数的时候为 $p-1$ ，接下来都考虑 $p$ 为素数的情况。这个性质非常的好，我们可以得到 $g^{p}\equiv g(mod\ p)\Rightarrow g^{p-1}\equiv 1(mod\ p)$ ，然后会觉得这个东西怎么这么像 $\omega_n^n=1$ 呢？所以我们令 $g_n=g^{(p-1)/n}$ ，那么只要我们说明原根也有类似单位复数根的性质，就可以把 $g$ 直接当做 $\omega$ 来用了。$$ \begin{aligned} 1.&g_{2n}^{2k}=g^{2k(p-1)/2n}=g^{k(p-1)/n}=g_{n}^{k}\\ 2.&g_{n}^{n/2}=\pm\sqrt{g_n^{n}}\\ &∵ g^{i}\not=g^{j}\\ &∴ g_{n}^{n/2}=-1\\ 3.&(g_{n}^{k})^2=g_{n}^{2k}=g_{n\over 2}^{k} \end{aligned} $$竟然都一样啊，那就很愉快了，至于原根怎么求之后再说。快速数论变换首先你要会背FFT板子，然后你把所有单位复数根换成原根就行了。注意模数需要是 $p=a\times 2^{k}+1$ 的形式，其中 $2^k\ge n$ ，$n$ 为补成二的次幂后得到的数，至于为什么就是防止指数出现分数导致没法处理。所以NTT模数要求比较严格……因此称为NTT模数QAQ，最著名(?)的应该是998244353(好像也叫UOJ模数，雾)。有没有任意模数NTT？安利Manchery的三模数NTT(反正我不会)，还有种比较粗暴的拆系数FFT也可以处理此问题。板子：UOJ34，假装有模数。#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=262144,MOD=998244353; //3是998244353的一个原根 int n,m,A[maxn+5],B[maxn+5],C[maxn+5],G[2][maxn+5],REV[maxn+5]; inline int Pow(int w,int b) { static int s;s=1; while (b) {if (b&1) s=(LL)s*w%MOD;b>>=1;if (b) w=(LL)w*w%MOD;} return s; } inline void Make(int n){ for (int i=2;i<=n;i<<=1) G[0][i]=Pow(3,(MOD-1)/i),G[1][i]=Pow(G[0][i],MOD-2); for (int i=1;i<n;i++) REV[i]=(REV[i>>1]>>1)|((i&1)*(n>>1)); } inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline void NTT(int *a,int n,int f){ for (int i=0;i<n;i++) if (i>REV[i]) swap(a[i],a[REV[i]]); for (int k=1;k<n;k<<=1){ int gn=G[f<0][k<<1],g=1,x,y; for (int i=0;i<n;i+=(k<<1),g=1) for (int j=0;j<k;j++,g=(LL)g*gn%MOD) x=a[i+j],y=(LL)a[i+j+k]*g%MOD,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]=(LL)a[i]*Pow(n,MOD-2)%MOD; } int main(){ freopen("NTT.in","r",stdin); freopen("NTT.out","w",stdout); scanf("%d%d",&n,&m); for (int i=0;i<=n;i++) scanf("%d",&A[i]); for (int i…

[矩阵乘法]BZOJ4417(Shoi2013)【超级跳马】题解
type: item
date: 2018-05-25T09:15:00+08:00
description: 题目概述现有一个 $n$ 行 $m$ 列的棋盘，一只马欲从棋盘的左上角跳到右下角。每一步它向右跳奇数列，且跳到本行或相邻行。跳越期间，马不能离开棋盘。试求跳法种数 $mod\ 30011$ 。解题报告我好菜啊，怎么这都不会啊，Orz ChesterKing。首先先写柿子：$$ f_{i,j}=\sum_{k}f_{i-(2k-1),j-1}+f_{i-(2k-1),j}+f_{i-(2k-1),j+1} $$$m$ 这么大应该是矩乘，但是这样肯定没法做啊QAQ。我们要想办法把这个柿子变成只和相邻几个有关，怎么办呢？想削掉 $\Sigma$ 当然只能记录前缀和啦XD。所以记录 $sum_{0/1,j}$ 表示当前前面和后面的两列前缀和，转移：$$ sum'_{0,i}=sum_{1,i}\\ sum'_{1,i}=sum_{0,i}+sum_{1,i-1}+sum_{1,i}+sum_{1,i+1} $$这样就可以矩乘搞了。示例程序#include<cstdio> using namespace std; const int maxn=100,MOD=30011; int n,m; struct Matrix{ int r,c,s[maxn][maxn]; inline void zero(int n,int m) {r=n;c=m;for (int i=0;i<n;i++) for (int j=0;j<m;j++) s[i][j]=0;} inline void unit(int n) {zero(n,n);for (int i=0;i<n;i++) s[i][i]=1;} }; Matrix f,T; inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline Matrix operator * (const Matrix &a,const Matrix &b){ static Matrix c;c.zero(a.r,b.c); for (int i=0;i<a.r;i++) for (int j=0;j<b.c;j++) for (int k=0;k<a.c;k++) AMOD(c.s[i][j],a.s[i][k]*b.s[k][j]%MOD); return c; } #define ID(x,y) ((x)*n+(y)-1) inline Matrix Pow(Matrix w,int b){ static Matrix s;s.unit(w.r); while (b) {if (b&1) s=s*w;b>>=1;if (b) w=w*w;} return s; } int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); scanf("%d%d",&n,&m);T.zero(n<<1,n<<1); for (int i=1;i<=n;T.s[ID(1,i)][ID(0,i)]++,T.s[ID(0,i)][ID(1,i)]++,i++) for (int j=(i-1<1?1:i-1);j<=i+1&&j<=n;j++) T.s[ID(1,j)][ID(1,i)]++; f.zero(1,n<<1);f.s[0][ID(1,1)]++;f=f*Pow(T,m-2); int ans=MOD-f.s[0][ID(0,n)];f=f*T;AMOD(ans,f.s[0][ID(1,n)]); return printf("%d\n",ans),0; }

[主席树+平衡树]BZOJ4548【小奇的糖果】题解
type: item
date: 2018-05-24T16:22:00+08:00
description: 题目概述有 $n$ 个有颜色的点，颜色有 $K$ 种，现在选一条线段并获取上面或下面的所有点，规定获得的点不能包含所有颜色，问你能获得多少点。解题报告我怎么套路题都不会做啊……首先有显然的贪心，就是选 $K-1$ 个颜色，那么我们先枚举不选的颜色是什么。然后坐标系中就多了一堆限制点，我们肯定是贴着限制点选，所以从下往上或者从下往上搞搞就行了。我是这么做的：从下往上做，每次加入一个点之后就说明坐标系被分成了两半，用set维护一下这些分隔线就行了。示例程序我又被BZOJ卡常了……反正BZOJ3658过了……我不管了……#include<cstdio> #include<vector> #include<set> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; typedef long long LL; const int maxn=100000,maxt=1e7; int te,n,K,c[maxn+5],ro[maxn+5];LL x[maxn+5],y[maxn+5]; int len,sum[maxt+5],ls[maxt+5],rs[maxt+5],X,Y,ans; vector<int> P[maxn+5];vector< pair<int,int> > p[maxn+5]; set<int> pos;set<int>::iterator it; inline void Make(LL *a){ static LL tem[maxn+5];for (int i=1;i<=n;i++) tem[i]=a[i]; sort(tem+1,tem+1+n);tem[0]=unique(tem+1,tem+1+n)-tem-1; for (int i=1;i<=n;i++) for (int L=1,R=tem[0],mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) if (a[i]==tem[mid]) {a[i]=mid;break;} else a[i]<tem[mid]?R=mid-1:L=mid+1; } #define newnode(s,l,r) (sum[len]=(s),ls[len]=(l),rs[len]=(r),len++) int Build(int L,int R){ int now=newnode(0,0,0);if (L==R) return now;int mid=L+(R-L>>1); ls[now]=Build(L,mid);rs[now]=Build(mid+1,R);return now; } int Insert(int p,int pos,int l=1,int r=X){ int now=newnode(sum[p]+1,ls[p],rs[p]);if (l==r) return now;int mid=l+(r-l>>1); if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);return now; } int Ask(int p,int L,int R,int l=1,int r=X){ if (R<l||r<L) return 0;if (L<=l&&r<=R) return sum[p];int mid=l+(r-l>>1); return Ask(ls[p],L,R,l,mid)+Ask(rs[p],L,R,mid+1,r); } inline bool cmp(const pair<int,int> &a,const pair<int,int> &b) {return a.sc<b.sc;} inline int Count(){ for (int i=1;i<=Y;i++) P[i].clear();for (int i=1;i<=n;i++) P[y[i]].push_back(x[i]); int ans=0;len=0;ro[0]=Build(1,X); for (int i=1;i<=Y;i++) for (int j=(ro[i]=ro[i-1],0);j<P[i].size();j++) ro[i]=Insert(ro[i],P[i][j]); for (int i=1;i<=K;i++) p[i].clear(); for (int i=1;i<=n;i++) p[c[i]].push_back(mp(x[i],y[i])); for (int i=1;i<=K;i++){…

[裴蜀定理+DP]LOJ2523(HAOI2018)【奇怪的背包】题解
type: item
date: 2018-05-23T16:50:00+08:00
description: 题目概述给你 $n$ 种物品，每种物品有无数个，体积为 $V_i$ ，选出若干种物品使得这些物品存在一种方案使得体积加起来 $mod\ p=w$ ，问方案数。解题报告怎么我一道HAOI题都不会啊，我实在太菜了（HAOI题太假了）。写成柿子就是验证是否存在 $\{a_{k+1}\}$ 使得 $\sum_{i=1}^{k}a_iV_i\equiv w(mod\ p)\Leftrightarrow \sum_{i=1}^{k}a_iV_i-a_{n+1}p=w$ ，如果 $k=2$ 的话那么就是裴蜀定理，实际上裴蜀定理可以推广到 $k$ 元线性同余方程，就是验证 $(V_1,V_2,\cdots,V_k,p)|w$ ，yy一下还是很显然的（不就是不会证吗，直接说不就好了）。然后我就不会做了QAQ，看题解……再变形一下就是 $((V_1,p),(V_2,p),\cdots,(V_k,p))|(w,p)$ 。为什么这样变形？因为你会发现这么变形之后所有元素就限制在了 $p$ 的因子内！然后你就可以瞎搞了：定义 $f_{i,j}$ 表示用前 $i$ 个因子 $gcd$ 出第 $j$ 个因子的方案数，对于每个因子转移一下，最后 $O(1)$ 回答。$10^9$ 之内因子个数是 $O(10^3)$ 的，颠覆了我的世界观……看来下次看到这种题要多往因子方面想……示例程序#include<cstdio> #include<cctype> #include<cmath> #include<algorithm> #include<unordered_map> using namespace std; typedef long long LL; const int maxd=10000,maxn=1000000,MOD=1e9+7; int n,te,P,D[maxd+5],num[maxd+5],f[2][maxd+5]; int pw[maxn+5];unordered_map<int,int> ID; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int readi(int &x){ int 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(int x){ for (int i=1,S=sqrt(x);i<=S;i++) if (!(x%i)) {D[++D[0]]=i;if (i<x/i) D[++D[0]]=x/i;} sort(D+1,D+1+D[0]);for (int i=1;i<=D[0];i++) ID[D[i]]=i; } int gcd(int a,int b) {if (!b) return a;return gcd(b,a%b);} 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);readi(te);readi(P);Make(P); for (int i=1,x;i<=n;i++) readi(x),num[ID[gcd(x,P)]]++; pw[0]=1;for (int i=1;i<=n;i++) pw[i]=((LL)pw[i-1]<<1)%MOD; for (int i=1,c=1;i<=D[0];i++,c^=1){ for (int j=1;j<=D[0];j++) f[c][j]=f[c^1][j];AMOD(f[c][i],pw[num[i]]-1); for (int j=1;j<=D[0];j++) AMOD(f[c][ID[gcd(D[i],D[j])]],(LL)f[c^1][j]*(pw[num[i]]-1)%MOD); } fo…

[SG函数]LOJ2126(HAOI2015)【数组游戏】题解
type: item
date: 2018-05-22T16:15:00+08:00
description: 题目概述有一个长度为 $n$ 的数组，甲乙两人在上面进行这样一个游戏：首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为 $x$ 。接着，选择一个大小在 $1 \sim n$ 之间的整数 $k$，然后将下标为 $x$、$2x$、...、$kx$ 的格子都进行颜色翻转。不能操作的人输。现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。解题报告我怎么博弈一点都不会啊QAQ，看到这种不可做的奇怪规则就要去想等价规则（然而我根本想不到）。如果我们允许翻黑格子，并把胜利条件定义为把所有格子翻成黑色，会发现这和原来的规则是一样的！因为翻黑格子之后，不可能立刻获胜，下一轮就可以执行同样的操作翻回来，所以最优解不会去翻黑格子，也就是说和原规则等价。去掉只能翻白色格子的限制，解法就很显然了，令 $SG(i)$ 表示 $i$ 棋子的SG函数，那么：$$ SG(i)=mex\{SG(2i)\ xor\ SG(3i)\ xor\cdots xor\ SG(ki)|k\in[2,\lfloor{n\over i}\rfloor\} $$但是 $n$ 是 $10^9$ ？？？过分了吧？我们观察下性质（打个SG函数表）会发现连续的一片SG函数值是相同的，再想想就发现 $i$ 的SG函数值只与 $\lfloor{n\over i}\rfloor$ 有关，因为决定棋子SG函数值的是该棋子控制棋子的数量。那么有用的状态就只有 $O(\sqrt n)$ 个了，$O(n)$ 预处理后每次算一下白色棋子SG函数异或值即可。然而我的写法好像不是很好，带了较大的常数，只能拿 $70$ 分，我就口头AC好了XD。示例程序#include<cstdio> #include<cmath> using namespace std; const int maxn=65000; int n,S,te,ti,vis[maxn+5],sg[2][maxn+5]; #define SG(x) (n/(x)>S?sg[1][x]:sg[0][n/(x)]) inline void Make(){ for (int l,r=n;r;r=l-1){ l=n/(n/r+1)+1;int now=0;vis[0]=++ti; for (int L=r+1,R;L<=n;L=R+1){ R=n/(n/L);int tot=R/l-(L-1)/l; if (tot&1) now^=SG(L),vis[now]=ti; else if (tot>1) vis[now^SG(L)]=ti; } int f=0;while (vis[f]==ti) f++; if (n/l>S) sg[1][l]=f; else sg[0][n/l]=f; } } int main(){ freopen("program.in","r",stdin); freopen("program.out","w",stdout); scanf("%d",&n);S=sqrt(n);Make(); for (scanf("%d",&te);te;te--){ int m,x,ans=0;scanf("%d",&m); while (m--) scanf("%d",&x),ans^=SG(x); puts(ans?"Yes":"No"); } return 0; }