2-SAT 乱水
看了下2-SAT，然后随便水了两道题
POJ3207 这个段哥当时讲过，然而我当时十分Naive。。
这题良心到Tarjan都不用写直接写个BCJ就好了因为连边的特殊性
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1050
int n,m,ln[N][2],fa[N],ri,ss=1,st=0,ans=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline bool Intersect(int x,int y)
{return ln[x][0]>ln[y][0]&&ln[x][0]<ln[y][1]&&ln[x][1]>ln[y][1];}
int Find(int x)
{return fa[x]==x?x:(fa[x]=Find(fa[x]));}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
ln[i][0]=Read();ln[i][1]=Read();fa[i]=i;fa[i+m]=i+m;
if (ln[i][0]>ln[i][1]) swap(ln[i][0],ln[i][1]);
}
for (int i=1;i<m;i++)
for (int j=i+1;j<=m;j++)
if (Intersect(i,j)||Intersect(j,i))
fa[Find(i)]=Find(j+m),fa[Find(i+m)]=Find(j);
for (int i=1;i<=m;i++)
if (Find(i)==Find(i+m)) {ans=-1;break;}
if (ans) puts("the evil panda is lying again");else
puts("panda is telling the truth...");
return 0;
}
POJ3678
Tarjan然后求个强连通分量，如果i和i'在同一强连通分量内就肯定是无解的。
至于怎么证并不知道= =，而且这题还没有对称性
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 2050
#define M 3000050
int fi[N],c[M][2],low[N],n,m,ss,ri,li[N],cl[N],st,ln[M][2];
int s[N];bool b[N];char d[20];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(int x,int y)
{c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;ln[ss][0]=x;ln[ss][1]=y;}
void DFS(int x,int y)
{
int k=++ri;li[ri]=x;low[x]=y;b[x]=1;
for (int i=fi[x];i;i=c[i][1])
if (b[c[i][0]])
low[x]=min(low[x],low[c[i][0]]);else
if (!low[c[i][0]])
DFS(c[i][0],y+1),low[x]=min(low[x],low[c[i][0]]);
if (low[x]==y)
{
st++;
for (int i=k;i<=ri;i++)
b[li[i]]=0,cl[li[i]]=st;
ri=k-1;
}
}
int main()
{
n=Read();m=Read();
for (int i=1;i<=m;i++)
{
int q=Read()+1,w=Read()+1,e=Read();
scanf("%s",d);
if (d[0]=='A'&&!e)
Line(q,w+n),Line(w,q+n);else
if (d[0]=='A')
Line(q+n,q),Line(w+n,w);else
if (d[0]=='O'&&!e)
Line(q,q+n),Line(w,w+n);else
if (d[0]=='O')
Line(q+n,w),Line(w+n,q);else
if (e)
Line(q+n,w),Line(q,w+n),Line(w,q+n),Line(w+n,q);else
Line(q,w),Line(w,q),Line(q+n,w+n),Line(w+n,q+n);
}
for (int i=1;i<=n*2;i++)
if (!low[i]) DFS(i,1);
for (int i=1;i<=n;i++)
if (cl[i]==cl[i+n])
{puts("NO");return 0;}
puts("YES");
return 0;
}
还有输出字典序最小解的就是暴力O(nm)DFS
任意解的就是在上面Tarjan的基础上拓扑排序一下，每次选一个出度为0的未染色点，把它的对应点i和i的所有前驱全部标为不选。因为有之前那个性质所以并不用拓扑排序过程中无需判无解。
后缀自动机乱做
最近看了SAM课件+论文+博客
基本懂是什么sxbk东西了，有几个主要性质：一个状态所代表的子串互为后缀，并且长度连续；有一个right集合是这个子串出现的位置集合；当前状态的parent状态也是当前状态的子串的后缀，并且其right集合包含了当前状态的right集合；当前状态的最长长度已经处理出来了就是val，而最短长度就是BFS一遍可以得到（maya明明这个就是suf的val+1的所以不用求了）；suf可以建成一棵树；right集合可以O(S)求最大最小值或者元素个数，这些都要先把suf树上的叶子节点也就是所有前缀所代表的状态设个初值然后就可以往上传值，并且两个节点的right集合要不就交集为空要不就一个为另外一个的祖先，而求出这个集合可以用启发式合并。
然后背了下模板，还要学下怎么建后缀数组，准备把cls课件还有论文上面的题目写掉一些。
SPOJ LCS：
求两个子串的最长公共子串
将其中一个的SAM建出来，另外一个在上面跑一遍，同时记录跑完当前字符之后当前的状态以及当前匹配长度，这东西之所以不能直接当成val是因为有可能比val小，于是每往下走的时候就val++，当当前匹配不了时就suf走，然而由性质当前的长度肯定大于suf的长度所以往回走的时候长度又要变成val。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 250050
#define M 26
char b[N];
struct State
{
State *suf,*go[M];int val;
State(): val(0),suf(0)
{memset(go,0,sizeof(go));}
} *root,*last,*cur,statePool[N*2],*now;int ans,t;
void extend(int w)
{
State *p=last,*np=cur++;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p) np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;
memcpy(nq->go,q->go,sizeof q->go);
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
int main()
{
scanf("%s",b);
cur=statePool;root=last=cur++;
for (char* i=b;*i;i++)
extend(*i-'a');
scanf("%s",b);
t=0;now=root;
for (char* i=b;*i;i++)
if (now->go[*i-'a'])
now=now->go[*i-'a'],ans=max(ans,++t);else
{
while (now&&!now->go[*i-'a']) now=now->suf;
if (now==NULL)
now=root,t=0;else
ans=max(ans,t=now->val+1),now=now->go[*i-'a'];
}
cout <<ans<<endl;
return 0;
}
SPOJ LCS2：
给10个串要求最大匹配大小
当然也是求出第一个串的SAM，然后每个串在上面跑一遍，每跑一遍每个节点记录当前跑出来的最长匹配是多少，并且这个东西可以传给suf的，这样跑10遍，每个点每次跑出的答案要取最小值，所有点的最小值还要取个最大值就是答案。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 200050
#define M 26
char b[N];
struct State
{
State *par,*go[M],*ne;int val,t[12],ma;
State(): ne(0),par(0)
{memset(go,0,sizeof(go));memset(t,0,sizeof(t));}
} *root,*last,statePool[N],*cur,*fi[N];
int st=0,ans=0,len;
inline State* Line(int x)
{cur->val=x;cur->ne=fi[x];fi[x]=cur;return cur++;}
void extend(int w)
{
State *p=last,*np=Line(p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->par;
if (!p)
np->par=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->par=q;else
{
State *nq=Line(p->val+1);
memcpy(nq->go,q->go,sizeof q->go);
nq->par=q->par;
q->par=np->par=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->par;
}
}
last=np;
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;last=root=Line(0);
for (char *i=b;*i;i++) extend(*i-'a');
while (st++,scanf("%s",b)!=EOF)
{
State* now=root;int s=0;
for (char *i=b;*i;i++)
{
int k=*i-'a';
while (now&&!now->go[k])
now=now->par,s=now?now->val:0;
if (!now)
now=root,s=0;else
now=now->go[k],now->t[st]=max(now->t[st],++s);
}
}
for (int i=len;i>=1;i--)
for (State* j=fi[i];j;j=j->ne)
{
int l=i;
for (int k=1;k<st;k++)
{
l=min(l,j->t[k]);
if (j->par)
j->par->t[k]=max(j->par->t[k],j->t[k]);
}
ans=max(ans,l);
}
cout <<ans<<endl;
return 0;
}
SPOJ SUBLEX：
求一个长为n(n<=9w)串的去重的子串集合中的第k(k∈int)大的串并输出，q(q<=500)组询问
还是建出SAM，然后处理出每个状态的可达子串有多少个，这个东西可以拓扑排序之后算一下就好了。然后将询问排序，从root出发依次处理每个询问，同时枚举当前状态的每个转移计算加上这个转移的子串数后是否超过答案，是则到下一个转移，否则进入这个转移。这题时限还只有0.2s左右，还好不卡int（虽然不知道能不能卡），T了好几发删掉了long long才勉强过，SPOJ卡时卡的sxbk。话说一开始这题没看样例以为没有去重的。这样的话每个状态的所代表的子串个数就是right集大小*（最长子串长度-最短子串长度），这样不加long long能过就sxbk了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 180050
#define M 26
#define fr first
#define sc second
struct State
{State *go[M],*suf,*ne;int val,t,wz;};
State *root,*last,*cur,statePool[N],*fi[N],*Stack[N];
int st,len,m,ans[M*20][2],sta[N];
pair <int,int> qu[M*20];char b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line(State* y,ll x)
{y->val=x;y->ne=fi[x];fi[x]=y;}
void extend(int w)
{
State *p=last,*np=cur;Line(cur++,p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur;Line(cur++,(p->val)+1);
memcpy(nq->go, q->go, sizeof q->go);
nq->suf=q->suf;q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Right()
{
State* now=root;int l=0;
for (char *i=b;*i;i++)
{
int k=*i-'a';
if (now->go[k])
now=now->go[k];else
{
while (now&&!now->go[k]) now=now->suf;
if (!now) now=root;else now=now->go[k];
}
now->wz=l++;
}
for (int i=len;i>=1;i--)
for (State* j=fi[i];j;j=j->ne)
j->suf->wz=j->wz,j->t=1;
for (int i=len;i>=0;i--)
for (State* j=fi[i];j;j=j->ne)
for (int k=0;k<M;k++)
if (j->go[k]) j->t+=j->go[k]->t;
}
inline void Update(int x,int y,int z)
{ans[z][1]=x;ans[z][0]=x-y+1;}
void Solve()
{
m=Read();
for (int i=1;i<=m;i++)
qu[i].fr=Read(),qu[i].sc=i;
sort(qu+1,qu+m+1);int ri=1,i=1;ll now=0;
Stack[1]=root;sta[1]=0;
while (i<=m)
{
if (!Stack[ri]->go[sta[ri]])
sta[ri]++;else
if (now+Stack[ri]->go[sta[ri]]->t<qu[i].fr)
now+=Stack[ri]->go[sta[ri]]->t,sta[ri]++;else
if (now+1==qu[i].fr)
Update(Stack[ri]->go[sta[ri]]->wz,ri,qu[i++].sc);else
now++,Stack[ri+1]=Stack[ri]->go[sta[ri]],sta[++ri]=0;
while (ri&&sta[ri]==26) sta[--ri]++;
}
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;st=-1;Line(cur,0);last=root=cur++;
for (char *i=b;*i;i++) extend(*i-'a');
Right();Solve();
for (int i=1;i<=m;i++)
{
for (int j=ans[i][0];j<=ans[i][1];j++)
putchar(b[j]);
printf("\n");
}
return 0;
}
SPOJ NSUBSTR
求字符串中每个长度的相同子串最多有多少，n<=25w
直接求right集合大小，而这个大小是可以更新1~val的ans的，所以对于每个节点直接更新val的ans，最后再从后往前扫一遍用长的ans更新短的ans
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 250050
#define M 26
struct State
{State *suf,*go[M],*ne;int val,ri;};
State *root,*last,*cur,statePool[N*2],*fi[N];
int len,ans[N];char b[N];
inline State* Line(int x)
{cur->ne=fi[x];cur->val=x;fi[x]=cur;return cur++;}
void extend(int w)
{
State *p=last,*np=Line(p->val+1);
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=Line(p->val+1);
memcpy(nq->go,q->go,sizeof q->go);
nq->suf=q->suf;
q->suf=np->suf=nq;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;
}
void Right()
{
State* now=root;
for (char *i=b;*i;i++)
{
int k=*i-'a';
while (now&&!now->go[k])
now=now->suf;
now=now->go[k];
now->ri++;
}
for (int i=len;i>=1;i--)
for (now=fi[i];now;now=now->ne)
now->suf->ri+=now->ri;
}
int main()
{
scanf("%s",b);len=strlen(b);
cur=statePool;root=last=Line(0);
for (char* i=b;*i;i++) extend(*i-'a');
Right();
for (;root!=cur;root++)
ans[root->val]=max(ans[root->val],root->ri);
for (int i=len-1;i>=1;i--)
ans[i]=max(ans[i+1],ans[i]);
for (int i=1;i<=len;i++)
printf("%d\n",ans[i]);
return 0;
}
SPOJ NSUBSTR2
动态加字符，同时给定一个串并且询问这个串在母串中出现几次。强制在线
如果没有修改就是直接处理出每个点的right集合大小。这样也差不多，反正每个点要求出自己子树内的叶子节点个数，就可以上LCT了。在建图过程中不会对suf树造成太大影响，只要处理下nq、q还有np的情况就好了。
然而SPOJ卡时间卡的实在sxbk，我硬是把所有能想到的优化都加上了还不能过，最后还是把每次询问的结点Splay一下才过了= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 160050
#define M 26
struct State
{State *suf,*go[M];int val,t;};
State *root,*last,statePool[N],*cur;
int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans;
bool fz[N],d[N];char b[N];
inline void fzj(int x)
{
if (!x||!fz[x]) return;
swap(c[x][0],c[x][1]);
fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]];
fz[x]=fz[0]=0;
}
inline void adj(int x)
{
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
ad[x]=ad[0]=0;
}
inline void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else
rf[x]=rf[i],rf[i]=0;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
}
void Up(int x)
{if (fa[x]) Up(fa[x]);fzj(x);adj(x);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
}
void Access(int x)
{
int i=0;
while (x)
{
Splay(x);
rf[c[x][1]]=fa[i]=x;
fa[c[x][1]]=rf[i]=0;
c[x][1]=i;i=x;x=rf[x];
}
}
void Delete(int x,int y)
{
Splay(x);
if (rf[x]==y) rf[x]=0;else
Splay(y),c[y][1]=fa[x]=0;
}
void extend(int w)
{
State *p=last,*np=cur++;np->t=++st;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;nq->t=++st;
memcpy(nq->go,q->go,sizeof q->go);
Delete(q->t,q->suf->t);t[st]=t[q->t];
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
rf[q->t]=st;rf[st]=nq->suf->t;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;rf[np->t]=np->suf->t;
Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t);
}
int main()
{
scanf("%s",b);
cur=statePool;root=last=cur++;root->t=st=1;
for (char* i=b;*i;i++) extend(*i-'a');
cin >>m>>A>>B;
while (m--)
{
scanf("%s",b);State* now=root;ans=0;
for (char* i=b;*i;i++)
if (!now->go[*i-'a'])
{ans=-1;break;}else
now=now->go[*i-'a'];
ans=ans?0:(Splay(now->t),t[now->t]);
printf("%d\n",ans);
extend((A*ans+B)%26);
}
return 0;
}
BZOJ2555
跟上题基本上一样= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 3000050
#define M 26
struct State
{State *suf,*go[M];int val,t;};
State *root,*last,statePool[N],*cur;
int st,fa[N],rf[N],c[N][2],ad[N],t[N],A,B,m,ans,n,mask;
bool fz[N],d[N];char b[N],f[M];
inline void fzj(int x)
{
if (!x||!fz[x]) return;
swap(c[x][0],c[x][1]);
fz[c[x][0]]=!fz[c[x][0]];fz[c[x][1]]=!fz[c[x][1]];
fz[x]=fz[0]=0;
}
inline void adj(int x)
{
if (!x||!ad[x]) return;
t[x]+=ad[x];ad[c[x][0]]+=ad[x];ad[c[x][1]]+=ad[x];
ad[x]=ad[0]=0;
}
inline void Rotate(int x)
{
int i=fa[x],j=fa[i],k=c[i][0]==x;
if (j) c[j][c[j][1]==i]=x;else
rf[x]=rf[i],rf[i]=0;
if (c[x][k]) fa[c[x][k]]=i;
c[i][!k]=c[x][k];fa[i]=x;
c[x][k]=i;fa[x]=j;
}
void Up(int x)
{if (fa[x]) Up(fa[x]);fzj(x);adj(x);}
void Splay(int x)
{
Up(x);
while (fa[x])
{
if (fa[fa[x]])
Rotate(c[fa[fa[x]]][0]==fa[x]^c[fa[x]][0]==x?x:fa[x]);
Rotate(x);
}
}
void Access(int x)
{
int i=0;
while (x)
{
Splay(x);
rf[c[x][1]]=fa[i]=x;
fa[c[x][1]]=rf[i]=0;
c[x][1]=i;i=x;x=rf[x];
}
}
void Delete(int x,int y)
{
Splay(x);
if (rf[x]==y) rf[x]=0;else
Splay(y),c[y][1]=fa[x]=0;
}
void extend(int w)
{
State *p=last,*np=cur++;np->t=++st;
np->val=p->val+1;
while (p&&!p->go[w])
p->go[w]=np,p=p->suf;
if (!p)
np->suf=root;else
{
State *q=p->go[w];
if (q->val==p->val+1)
np->suf=q;else
{
State *nq=cur++;nq->t=++st;
memcpy(nq->go,q->go,sizeof q->go);
Delete(q->t,q->suf->t);t[st]=t[q->t];
nq->val=p->val+1;
nq->suf=q->suf;
q->suf=np->suf=nq;
rf[q->t]=st;rf[st]=nq->suf->t;
while (p&&p->go[w]==q)
p->go[w]=nq,p=p->suf;
}
}
last=np;rf[np->t]=np->suf->t;
Access(np->t);Splay(np->t);ad[np->t]=1;adj(np->t);
}
int main()
{
scanf("%d%s",&m,b);
cur=statePool;root=last=cur++;root->t=st=1;
for (char* i=b;*i;i++) extend(*i-'A');
while (m--)
{
scanf("%s%s",f,b);
for (int i=0,len=strlen(b),Mask=mask;i<len;i++)
Mask=(Mask*131+i)%len,swap(b[i],b[Mask]);
if (f[0]=='A')
for (char* i=b;*i;i++) extend(*i-'A');else
{
State* now=root;ans=0;
for (char* i=b;*i;i++)
if (!now->go[*i-'A'])
{ans=-1;break;}else
now=now->go[*i-'A'];
ans=ans?0:(Splay(now->t),t[now->t]);
printf("%d\n",ans);mask^=ans;
}
}
return 0;
}
BZOJ 3676
题面：给定一个串，一个回文子串的权值是它的长度*它的出现次数，要求求出串中最大权值。|S|<=30w
题解：因为是在Keavil论文上看到这道题，但是按他的思路一直都没想出来怎么做，主要是一个状态可以是很多子串，所以不能直接更新出现次数。后来知道这题好像有至少三种写法真是sxbk，回文自动机的写法以后补，还有一个好神的hash和hzwer的SAM写法。后面两种主要都是有一个性质就是一个串中的不同的回文子串个数是O(n)的，感觉果然是manacher没学好= =，所以就可以直接在manacher过程中搞。hash解法好像是在manacher过程中把当前这个串hash然后建出一棵树，然后好像就可以搞了。SAM就是manacher的时候用当前回文子串倍增找到这个串所在答案，查询right集合大小更新答案。搞懂之后还调了好久，一开始naive没看空间限制，后面重新用数组写一遍才勉强卡过限制，结果还是写挂了好多地方调了好久= =，果然人太弱了。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
#define M 26
#define ll long long
int fi[N],ne[N*2],val[N*2],go[N*2][M],suf[N*2][19];ll ans=0;
int pre[N],p[N*2],b[N*2],n,m,root,last,cur,ri[N*2];char c[N];
void extend(int w,int x)
{
int p=last,np=cur++;
val[np]=val[p]+1;
ne[np]=fi[val[np]];fi[val[np]]=np;
while (p&&!go[p][w])
go[p][w]=np,p=suf[p][0];
if (!p)
suf[np][0]=root;else
{
int q=go[p][w];
if (val[q]==val[p]+1)
suf[np][0]=q;else
{
int nq=cur++;
val[nq]=val[p]+1;
ne[nq]=fi[val[nq]];fi[val[nq]]=nq;
memcpy(go[nq],go[q],sizeof go[q]);
suf[nq][0]=suf[q][0];
suf[q][0]=suf[np][0]=nq;
while (p&&go[p][w]==q)
go[p][w]=nq,p=suf[p][0];
}
}
ri[last=pre[x]=np]=1;
}
void Set_up()
{
for (int i=n;i>=1;i--)
for (int j=fi[i];j;j=ne[j])
ri[suf[j][0]]+=ri[j];
for (int i=1;i<=n;i++)
for (int j=fi[i];j;j=ne[j])
for (int k=0;k<18&&suf[suf[j][k]][k];k++)
suf[j][k+1]=suf[suf[j][k]][k];
}
inline ll max(ll x,ll y)
{return x>y?x:y;}
void Query(int x,int y)
{
if (x>y) return;
int t=pre[y];
for (int i=18;i>=0;i--)
if (suf[t][i]&&val[suf[t][i]]>=y-x+1)
t=suf[t][i];
ans=max(ans,(ll)(ri[t])*(y-x+1));
}
void Manacher()
{
int k=0,l=-1;
for (int i=0;i<n;i++)
b[i*2+1]=c[i];
n*=2;b[n+1]=-1;
for (int i=0;i<=n;i++)
{
if (i<l) p[i]=min(p[k*2-i],l-i+1);
while (i-p[i]>=0&&b[i-p[i]]==b[i+p[i]])
Query(i-p[i] >> 1,i+p[i]-1 >> 1),p[i]++;
if (i+p[i]-1>l)
l=i+p[i]-1,k=i;
}
}
int main()
{
scanf("%s",c);n=strlen(c);
cur=1;last=root=cur++;
for (int i=0;i<n;i++) extend(c[i]-'a',i);
Set_up();Manacher();
cout <<ans<<endl;
return 0;
}
SAM转后缀数组就是标记每个结束状态然后DFS一遍SAM就很愉快了。
计算几何
又开了一个坑= =
首先是tsinsen的A1420 裸的动态凸包
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define eps 1e-8
struct Point
{
double a1,a2;
} t;
bool operator< (const Point &x,const Point &y)
{ double d=atan2(x.a2-t.a2,x.a1-t.a1),f=atan2(y.a2-t.a2,y.a1-t.a1),
o=(x.a1-t.a1)*(x.a1*t.a1)+(x.a2-t.a2)*(x.a2*t.a2),
p=(y.a1-t.a1)*(y.a1*t.a1)+(y.a2-t.a2)*(y.a2*t.a2);
return d+eps<f||fabs(d-f)<eps&&o<p;}
multiset <Point> li;
set <Point> :: iterator it,ti;
int n,m;
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
void Set_up()
{
Point a[4];double q=0,w=0,e,k;int i,j,l;
for (int i=1;i<=3;i++)
Read(),k=Read(),e=Read(),a[i].a1=k,a[i].a2=e,q+=k,w+=e;
t.a1=q/3;t.a2=w/3;
for (int i=1;i<=3;i++) li.insert(a[i]);
return;
}
inline double Cha(Point x,Point y,Point z)
{
return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1));
}
void Insert(Point x)
{
int i,j,k,l;Point q,w,e;
it=li.lower_bound(x);
if (it==li.end()||it==li.begin())
it=li.end(),q=*(--it),w=*(li.begin());else
w=*(it--),q=*it;ti=it;
if (Cha(q,x,w)<=eps) return;
while (li.size()>2)
{
if (it==li.begin()) it=li.end();
e=*(--it);
if (Cha(e,q,x)<=eps)
li.erase(ti);else break;
ti=it;q=e;
}
it=ti=li.lower_bound(w);
while (li.size()>2)
{
it++;if (it==li.end()) it=li.begin();
e=*(it);
if (Cha(x,w,e)<=eps)
li.erase(ti);else break;
ti=it;w=e;
}
li.insert(x);
return;
}
bool Check(Point x)
{
int i,j,k,l;Point q,w,e;
if (x.a1==t.a1&&x.a2==t.a2) return 1;
it=li.lower_bound(x);
if (it==li.end()) it=li.begin();
ti=it==li.begin()?li.end():it;ti--;
return Cha(*ti,x,*it)<=eps;
}
int main()
{
int i,j,q,w,e;Point k,l;
scanf("%d",&n);
li.clear();
Set_up();
for (i=4;i<=n;i++)
{
m=i;
q=Read();k.a1=Read();k.a2=Read();
if (q==1)
Insert(k);else
if (Check(k))
printf("YES\n");else
printf("NO\n");
}
return 0;
}
然后是BZOJ1069，凸包+单调性乱搞
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 4050
#define eps 1e-8
#define INF 0x7f7f7f7f
struct Point
{
double a1,a2;
} a[N],mi;
int n,m,li[N],ri;
double ans=0;
bool operator== (const Point &x,const Point &y)
{return fabs(x.a1-y.a1)<eps&&fabs(x.a2-y.a2)<eps;}
bool operator!= (const Point &x,const Point &y)
{return fabs(x.a1-y.a1)>eps||fabs(x.a2-y.a2)>eps;}
inline double Cha(Point x,Point y,Point z)
{return ((y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1));}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double max(double x,double y)
{return x<y?y:x;}
inline double Square(Point x,Point y,Point z)
{
return fabs((y.a1-x.a1)*(z.a2-x.a2)-(y.a2-x.a2)*(z.a1-x.a1))/2;
}
inline bool cmp(Point x,Point y)
{
double i=atan2(x.a2-a[n].a2,x.a1-a[n].a1),
j=atan2(y.a2-a[n].a2,y.a1-a[n].a1);
return i+eps<j||(fabs(i-j)<eps&&dis(x,a[n])+eps<dis(y,a[n]));
}
void Init()
{
int i,k;
memset(li,0,sizeof(li));
scanf("%d",&n);
mi.a1=mi.a2=INF;
for (i=1;i<=n;i++)
{
scanf("%lf%lf",&a[i].a1,&a[i].a2);
if (a[i].a1<mi.a1||(a[i].a1==mi.a1&&a[i].a2<mi.a2))
mi=a[k=i];
}
swap(a[k],a[n]);
return;
}
void Graham()
{
li[1]=n;li[ri=2]=1;
while (a[li[2]]==a[li[1]]&&li[2]<n) li[2]++;
if (li[2]==n) {ri--;return;}
for (int i=li[2]+1;i<n;i++)
if (a[i]!=a[li[ri]])
{
while (ri-1&&Cha(a[li[ri-1]],a[li[ri]],a[i])+eps<0) ri--;
li[++ri]=i;
}
while (ri-2&&Cha(a[li[ri-1]],a[li[ri]],a[1])+eps<0) ri--;
return;
}
void Solve()
{
int i,j,k,l;double q,w,e;
for (i=1;i<=ri;i++) li[i+ri]=li[i];
for (i=1;i<ri;i++)
{
k=0;j=i+1;q=0;w;
for (l=1;l<=ri;l++)
if ((w=Square(a[li[i]],a[li[l]],a[li[j]]))>q)
k=l,q=w;
l=i+1;
for (;j<=ri;j++)
{
while (Square(a[li[i]],a[li[j]],a[li[k+1]])>
Square(a[li[i]],a[li[j]],a[li[k]])) k++;
while (l<j&&Square(a[li[i]],a[li[j]],a[li[l+1]])>
Square(a[li[i]],a[li[j]],a[li[l]])) l++;
q=Square(a[li[i]],a[li[j]],a[li[l]]);
if (k!=l) q+=Square(a[li[i]],a[li[j]],a[li[k]]);
ans=max(ans,q);
}
}
return;
}
int main()
{
Init();
sort(a+1,a+n,cmp);
Graham();
Solve();
printf("%.3lf\n",ans);
return 0;
}
BZOJ1043 裸的求圆交点
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
{
double a1,a2;
} a[N],b[N];
double r[N],ans=0;
int n,m,ri;
inline double min(double x,double y)
{return x<y?x:y;}
inline double max(double x,double y)
{return x>y?x:y;}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double cmp(Point x,Point y)
{return x.a1+eps<y.a1||(fabs(x.a1-y.a1)<eps&&x.a2<y.a2);}
inline bool Intersect(int x,int y)
{
int i,j,k,l;double q=dis(a[x],a[y]),w,e;
if (q+eps>=r[x]+r[y]||(r[y]>r[x]&&r[y]-r[x]+eps>=q)) return 0;
if (q<=r[x]-r[y]+eps) return 1;
w=atan2(a[x].a2-a[y].a2,a[x].a1-a[y].a1);
e=acos((sqr(r[y])+sqr(q)-sqr(r[x]))/(2*r[y]*q));
b[ri].a1=w-e;b[ri].a2=w+e;
if (b[ri].a1+eps<-pi)
b[++ri].a1=b[ri-1].a1+2*pi,b[ri].a2=pi,b[ri-1].a1=-pi;else
if (b[ri].a2>pi+eps)
b[++ri].a2=b[ri-1].a2-2*pi,b[ri].a1=-pi,b[ri-1].a2=pi;
ri++;
return 0;
}
double Solve(int x)
{
int i,j,k,l;double q=0,w,e;ri=1;
for (i=1;i<x;i++)
if (Intersect(i,x)) return 0;
sort(b+1,b+ri,cmp);
for (i=2;i<ri;i++)
if (b[i].a1+eps<=b[i-1].a2)
b[i].a1=min(b[i].a1,b[i-1].a1),
b[i].a2=max(b[i].a2,b[i-1].a2),
b[i-1].a1=b[i-1].a2=0;
for (i=1;i<ri;i++)
q+=(b[i].a2-b[i].a1)*r[x];
return 2*pi*r[x]-q;
}
int main()
{
int i,j,k,l,q,w,e;
memset(r,0,sizeof(r));
scanf("%d",&n);
for (i=n;i>=1;i--)
scanf("%lf%lf%lf",&r[i],&a[i].a1,&a[i].a2);
for (i=1;i<=n;i++)
ans+=Solve(i);
printf("%.3lf\n",ans);
return 0;
}
BZOJ2300：看一眼吓傻，完全不知道有删点的动态凸包怎么做= =只记得好像有论文上面提到过，感觉巨神于是没管了= =后来发现没有加点操作，就是倒着搞的SB题了= =。然后因为某些细节一直没调出来，后来坑到了数据才过了= =。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
#define N 200050
#define eps 1e-9
struct Point
{
double a1,a2;
} a[N];
set <Point> li;
set <Point> :: iterator it,ti;
int n,m,qu[N][2];double ans=0,cnt[N];bool b[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.a1-y.a1)+sqr(x.a2-y.a2));}
inline double Cha(Point x,Point y,Point z)
{return (y.a1-x.a1)*(z.a2-y.a2)-(y.a2-x.a2)*(z.a1-y.a1);}
bool operator< (const Point &x,const Point &y)
{ double q=atan2(x.a2,x.a1),w=atan2(y.a2,y.a1);
return q+eps<w||(fabs(q-w)<eps&&x.a1*x.a1+x.a2*x.a2<
y.a1*y.a1+y.a2*y.a2);}
void Set_up()
{
int i,j;Point k,l;double q=Read(),w=Read(),e=Read();
li.insert(k=(Point){q,0});li.insert(l=(Point){w,e});
li.insert((Point){0,eps});
ans=dis((Point){0,0},l)+dis(l,k);
return;
}
inline void Insert(Point x)
{
int i,j;Point k,l;double q,w,e;
it=li.lower_bound(x);ti=it;ti--;k=*it;l=*ti;
if (Cha(l,x,k)<=eps) return;
ans=ans-dis(k,l);
do
{
ti=it;++it;
if (it==li.end()||Cha(x,*ti,*it)>eps) break;
ans=ans-dis(*ti,*it);
li.erase(ti);
} while (1);
ans+=dis(x,*ti);
it=li.lower_bound(l);
do
{
ti=it;--it;
if (ti==li.begin()||Cha(*it,*ti,x)>eps) break;
ans=ans-dis(*ti,*it);
li.erase(ti);
} while (1);
ans+=dis(x,*ti);li.insert(x);
return;
}
void Solve()
{
for (int i=1;i<=m;i++)
if (qu[i][0]==1) b[qu[i][1]]=1;
for (int i=1;i<=n;i++)
if (!b[qu[i][0]])
Insert(a[i]);
for (int i=m;i>=1;i--)
if (qu[i][0]==2)
cnt[i]=ans;else
Insert(a[qu[i][1]]);
for (int i=1;i<=m;i++)
if (qu[i][0]==2)
printf("%.2lf\n",cnt[i]);
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(qu,0,sizeof(qu));memset(b,0,sizeof(b));
memset(cnt,0,sizeof(cnt));
Set_up();n=Read();
for (i=1;i<=n;i++)
a[i].a1=Read(),a[i].a2=Read();
m=Read();
for (i=1;i<=m;i++)
{
qu[i][0]=Read();
if (qu[i][0]==1) qu[i][1]=Read();
}
Solve();
return 0;
}
maya颓了好久终于把这个鬼畜半平面交搞出来了，要注意的是跟前面一样，“孩子cmp函数写挫了你就废了”
，被一堆细节wa了n次= =
BZOJ2618：裸半平面交，坑比的是在BZOJ上过得了在codevs上怎么都过不了= =本来以为是有什么猥琐的细节，但是换了4个其他程序用出错的数据拍了n久硬是没发现问题。话说这个感觉还是写的好丑【捂脸贼】
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
{
double x,y;
} b[N];
struct Line
{
Point x,y;double v;
} a[N];
int n=0,m,t,ri,li[N],le=1;double ans=0;
Point operator+ (const Point &x,const Point &y)
{return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
{return x.x*y.y-x.y*y.x;}
inline bool cmp(Line x,Line y)
{
if (x.v!=y.v) return x.v<y.v;
return (x.y-x.x)*(y.y-x.x)>0;
}
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline Point Intersect(Line x,Line y)
{
double k=(y.x-x.x)*(y.y-x.x),l=(y.y-x.y)*(y.x-x.y);
double q=k/(k+l);Point p;p=x.y-x.x;
p.x=x.x.x+p.x*q;p.y=x.x.y+p.y*q;
return p;
}
inline bool Cao(Line x,Line y,Line z)
{
Point k=Intersect(x,y);
return (k-z.x)*(k-z.y)<=eps;
}
void Solve()
{
int i,j;Point k,l;double q,w,e;int tot=0;
sort(a+1,a+n+1,cmp);
a[n+1].v=-2*pi;
for (i=1;i<=n;i++)
{
if (a[i].v!=a[i-1].v) tot++;
a[tot]=a[i];
}
li[ri=1]=1;le=1;li[ri=2]=2;n=tot;
for (i=3;i<=n;i++)
{
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
while (ri-le&&Cao(a[li[le+1]],a[li[le]],a[i])) le++;
li[++ri]=i;
}
while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++;
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
for (i=le;i<ri;i++)
b[i-le+1]=Intersect(a[li[i]],a[li[i+1]]);
b[ri-le+1]=Intersect(a[li[ri]],a[li[le]]);
if (ri-le+1<3) return;
for (i=1,ri=ri-le+1;i<ri;i++)
ans+=b[i]*b[i+1];
ans+=b[ri]*b[1];
return;
}
int main()
{
t=Read();
for (int i=1;i<=t;i++)
{
Point q,w,e;
m=Read();q.x=Read(),q.y=Read();w=q;
for (int j=2;j<=m;j++)
e.x=Read(),e.y=Read(),a[++n]=(Line){w,e,
atan2(e.y-w.y,e.x-w.x)},w=e;
a[++n]=(Line){w,q,atan2(q.y-w.y,q.x-w.x)};
}
Solve();
printf("%.3lf\n",ans/2);
return 0;
}
BZOJ1038瞭望塔：又是一个半平面交的裸题，又被细节坑了好久= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 1050
#define M 1e12
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
{
double x,y;
} b[N],c[N];
struct Line
{
Point x,y;double v;
} a[N];
int n=0,m=0,li[N];
double ans=2*M;
Point operator+ (const Point &x,const Point &y)
{return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
{return x.x*y.y-x.y*y.x;}
bool operator< (const Line &x,const Line &y)
{return x.v!=y.v?x.v<y.v:(x.y-x.x)*(y.y-x.x)>0;}
inline double min(double x,double y)
{return x<y?x:y;}
inline double sqr(double x)
{return x*x;}
inline double dis(Point x,Point y)
{return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y));}
inline int Read()
{
int x=0;char y;bool z=0;
do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return z?-x:x;
}
inline Point Intersect(Line x,Line y)
{
double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y);
w=q/(w+q);Point e=x.y-x.x;e.x=x.x.x+e.x*w;
e.y=x.x.y+e.y*w;return e;
}
inline bool Cao(Line x,Line y,Line z)
{Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<=eps;}
void Set_up()
{
int i,j;Point k,l,q,w,e;
n=Read();
for (i=1;i<=n;i++) b[i].x=Read();
for (i=1;i<=n;i++) b[i].y=Read();
m=n-1;
for (i=1;i<=m;i++)
a[i].x=b[i],a[i].y=b[i+1],
a[i].v=atan2(b[i+1].y-b[i].y,b[i+1].x-b[i].x);
k.x=k.y=l.x=w.y=-M;q.x=q.y=l.y=w.x=M;
a[++m].x=w;a[m].y=q;a[m].v=pi/2;
a[++m].x=q;a[m].y=l;a[m].v=pi;
a[++m].x=l;a[m].y=k;a[m].v=-pi/2;
a[++m].x=k;a[m].y=w;a[m].v=0;
return;
}
void Half_Inter()
{
int i,j,tot=0,le,ri;Point k,l;double q,w,e;
sort(a+1,a+m+1);
for (i=1;i<=m;i++)
{
if (a[i].v!=a[i-1].v) tot++;
a[tot]=a[i];
}
le=1;ri=2;li[1]=1;li[2]=2;
for (i=3;i<=tot;i++)
{
while (ri-le&&Cao(a[li[le]],a[li[le+1]],a[i])) le++;
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
li[++ri]=i;
}
while (ri-le&&Cao(a[li[ri]],a[li[le]],a[li[le+1]])) le++;
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
for (i=le,ri=m=ri-le+1;i<le+ri-1;i++)
c[i-le+1]=Intersect(a[li[i]],a[li[i+1]]);
c[ri]=Intersect(a[li[le]],a[li[le+ri-1]]);
return;
}
inline void Check(Point x)
{
Line q;int i;q.x=q.y=x;q.y.y=M+1;
if (x.x<b[1].x||x.x>b[n].x) return;
for (int i=1;i<n;i++)
if (x.x>=b[i].x&&x.x<=b[i+1].x)
ans=min(ans,dis(Intersect(q,(Line){b[i],b[i+1],0}),x));
return;
}
inline void cHeck(Point x)
{
Line q;int i;q.x=q.y=x;q.y.y=-M-1;
for (int i=1;i<m;i++)
if ((x.x>=c[i].x)^(x.x>c[i+1].x))
ans=min(ans,dis(Intersect(q,(Line){c[i],c[i+1],0}),x));
return;
}
int main()
{
memset(li,0,sizeof(li));
Set_up();
Half_Inter();
for (int i=1;i<=m;i++) Check(c[i]);
for (int i=1;i<=n;i++) cHeck(b[i]);
printf("%.3lf\n",ans);
return 0;
}
BZOJ3190赛车：也是裸半平面交，真是一路wa。TATQAQ2333改完细节之后代码好丑= =
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10050
#define eps 1e-8
const double pi=acos(-1.0);
struct Point
{
double x,y;
};
struct Line
{
Point x,y;double v;int sg;
} a[N];
int n,m,s=0,li[N],le,ri;bool c[N];
Point operator+ (const Point &x,const Point &y)
{return (Point){x.x+y.x,x.y+y.y};}
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
{return x.x*y.y-x.y*y.x;}
bool operator< (const Line &x,const Line &y)
{return (x.v<y.v)||(x.v==y.v&&(x.y-x.x)*(y.y-x.x)>eps);}
bool operator!= (const Point &x,const Point &y)
{return x.x!=y.x||x.y!=y.y;}
bool operator!= (const Line &x,const Line &y)
{return x.v!=y.v||x.x!=y.x;}
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline Point Intersect(Line x,Line y)
{
Point e;double q=(y.x-x.x)*(y.y-x.x),w=(y.y-x.y)*(y.x-x.y);
w=q/(q+w);e=x.y-x.x;e.x=x.x.x+e.x*w;e.y=x.x.y+e.y*w;
return e;
}
inline bool Cao(Line x,Line y,Line z)
{Point k=Intersect(x,y);return (k-z.x)*(k-z.y)<-eps;}
void Half_Inter()
{
int i,j,tot=0;Point k,l,q,w,e;
sort(a+1,a+n+1);i=1;k.x=0;
while (i<n) {if (a[i]!=a[i+1]) k=Intersect(a[i],a[i+1]);if (k.x>-eps) break;i++;}
li[1]=i;li[2]=i+1;le=1;ri=2;
if (i==n) ri--;
for (i+=2;i<=n;i++)
{
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[i])) ri--;
li[++ri]=i;
}
while (ri-le&&Cao(a[li[ri-1]],a[li[ri]],a[li[le]])) ri--;
while (ri-le)
{
i=le;while (i<ri&&!(a[li[i]]!=a[li[i+1]])) i++;
if (i==ri) break;
k=Intersect(a[li[i]],a[li[i+1]]);
if (k.x>-eps) break;le=i+1;
}
return;
}
int main()
{
int j;
memset(li,0,sizeof(li));memset(c,0,sizeof(c));
scanf("%d",&n);
for (int i=1;i<=n;i++) a[i].x.y=a[i].y.y=Read();
for (int i=1;i<=n;i++) a[i].y.y+=(a[i].v=Read()),
a[i].y.x=1,a[i].sg=i;
Half_Inter();
printf("%d\n",ri-le+1);
for (int i=le;i<=ri;i++)
c[a[li[i]].sg]=1;
for (j=1;j<=n;j++)
{
if (c[j])
{
if (ri-le) printf("%d ",j);else
printf("%d\n",j);
le++;
}
}
return 0;
}
BZOJ1027合金：看上去是三维球面上面的问题，实际上因为是球面，所以投影到坐标系平面上面问题还是等价的。然后就暴力建边跑floyd（之前一直以为n^3会比较有危险，而且还是这种时限四秒题，总觉得还有其它方法，真是naive！）。还有要注意题目里面的细节比如答案为1或2的时候要做讨论，真心被坑wa了n次
话说为毛每次我的笔记作了20页就会丢，真是丧心= =
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 550
#define eps 1e-8
#define INF 0x3f3f3f3f
struct Point
{
double x,y;
} a[N],b[N];
Point operator- (const Point &x,const Point &y)
{return (Point){x.x-y.x,x.y-y.y};}
double operator* (const Point &x,const Point &y)
{return x.x*y.y-x.y*y.x;}
bool operator== (const Point &x,const Point &y)
{return fabs(x.x-y.x)<eps&&fabs(x.y-y.y)<eps;}
int n,m,ss,h[N][N],tot=0,ans=INF;
inline int Calc(Point x,Point y)
{
for (int i=1;i<=m;i++)
{
double q=(y-x)*(b[i]-x);
if (fabs(q)>eps&&q<0) return INF;
if (fabs(q)<eps&&((b[i].x-y.x)*(y.x-x.x)>eps||
(b[i].y-y.y)*(y.y-x.y)>eps)) return INF;
if (fabs(q)<eps&&((b[i].x-x.x)*(x.x-y.x)>eps||
(b[i].y-x.y)*(x.y-y.y)>eps)) return INF;
}
return 1;
}
bool Check()
{
if (m==1)
for (int i=1;i<=n;i++)
if (a[i]==b[1])
{
printf("1\n");return 1;
}
for (int i=3;i<=m;i++)
if (fabs((b[i]-b[1])*(b[2]-b[1]))>eps) return 0;
if (m==1) b[2]=b[1];
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
if (fabs((a[j]-a[i])*(b[2]-b[1]))<eps)
for (int k=1;k<=m;k++)
{
double l=b[k].x-a[i].x,q=b[k].x-a[j].x,
w=b[k].y-a[i].y,e=b[k].y-a[j].y;
if (fabs((a[i]-b[k])*(a[j]-b[k]))>eps) continue;
if ((fabs(l)>eps&&fabs(q)>eps&&l*q>0)||
(fabs(w)>eps&&fabs(e)>eps&&w*e>0)) continue;
printf("2\n");return 1;
}
return 0;
}
int main()
{
memset(h,0,sizeof(h));
scanf("%d%d",&n,&m);a[0].x=b[0].x=-1;
for (int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[0].y);
if (a[i].x!=a[i-1].x||a[i].y!=a[i-1].y) tot++;
a[tot]=a[i];
}
n=tot;tot=0;
for (int i=1;i<=m;i++)
{
scanf("%lf%lf%lf",&b[i].x,&b[i].y,&b[0].y);
if (b[i].x!=b[i-1].x||b[i].y!=b[i-1].y) tot++;
b[tot]=b[i];
}
m=tot;if (Check()) return 0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
h[i][j]=i!=j?Calc(a[i],a[j]):INF;
for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
h[i][j]=min(h[i][j],h[i][k]+h[k][j]);
for (int i=1;i<=n;i++)
ans=min(ans,h[i][i]);
printf("%d\n",ans==INF?-1:ans);
return 0;
}
匹配相关
还差一个一般图最大权匹配貌似就差不多了= =
匹配题目做得少，只好意思贴贴模板= =
Hungary（貌似没有网络流跑得快）：
#include <iostream>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
int a[N][N],c[N],n,m,s;
bool b[N];
inline bool aa(int x)
{
int i;
for (i=1;i<=n;i++)
if (a[x][i] && !b[i])
{
b[i]=1;
if (!c[i] || aa(c[i]))
{
c[i]=x;
return 1;
}
}
return 0;
}
int main()
{
int i,j,k,l,q,w,e=0;
memset(a,0,sizeof(a));memset(c,0,sizeof(c));
scanf("%d%d%d",&n,&m,&s);
for (i=1;i<=s;i++)
{
scanf("%d%d",&k,&l);
a[l][k]=1;
}
for (i=1;i<=m;i++)
{
memset(b,0,sizeof(b));
e+=aa(i);
}
printf("%d\n",e);
for (i=1;i<=n;i++)
printf("%d ",c[i]);
printf("\n");
return 0;
}
KM：
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
#define N 1005
#define INF 0x3f7f7f7f
#define ll long long
struct Point
{
int a1;ll a2;
bool operator < (const Point &x) const
{
return a2<x.a2||(a2==x.a2&&a1<x.a1);
}
};
set <Point> mi;
set <Point> :: iterator it;
ll s[N],v[N][2],h[N][N],ans=0;
int p[N][2],la[N],n,m,nm;
bool b[N][2];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void DFS(int x)
{
int i=p[la[x]][0];
if (!x) return;
p[x][1]=la[x];p[la[x]][0]=x;
DFS(i);
return;
}
void Solve(int x)
{
int i,j;ll q,w,e=0;Point k,l;
while (!mi.empty())
{
it=mi.begin();mi.erase(it);k=*it;k.a2+=e;
if (k.a2)
{
e-=k.a2;
for (i=1;i<=nm;i++)
if (b[i][0])
v[i][0]-=k.a2;
for (i=1;i<=nm;i++)
if (b[i][1])
v[i][1]+=k.a2;
}
for (i=1;i<=nm;i++)
if (b[i][0]&&v[i][0]+v[k.a1][1]==h[i][k.a1])
{la[k.a1]=i;break;}
if (p[k.a1][1])
{
b[k.a1][1]=b[p[k.a1][1]][0]=1;
for (i=1;i<=nm;i++)
if (!b[i][1]&&s[i]+e>v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i])
{
l.a1=i;l.a2=s[i];it=mi.lower_bound(l);mi.erase(it);
l.a2=s[i]=v[i][1]+v[p[k.a1][1]][0]-h[p[k.a1][1]][i]-e;
mi.insert(l);
}
}else
{
DFS(k.a1);return;
}
}
return;
}
int main()
{
int i,j,q,w,e;ll k,l;
memset(s,0,sizeof(s));memset(v,0,sizeof(v));
memset(h,0,sizeof(h));memset(la,0,sizeof(la));
memset(p,0,sizeof(p));memset(b,0,sizeof(b));
scanf("%d%d%d",&n,&m,&e);nm=max(n,m);
for (i=1;i<=e;i++)
h[k=Read()][Read()]=Read();
for (i=1;i<=nm;i++)
for (j=1;j<=nm;j++)
v[i][0]=max(v[i][0],h[i][j]);
for (i=1;i<=nm;i++)
{
memset(s,0,sizeof(s));memset(b,0,sizeof(b));
mi.clear();b[i][0]=1;
for (j=1;j<=nm;j++)
s[j]=v[j][1]+v[i][0]-h[i][j],la[j]=i,
mi.insert((Point){j,s[j]});
Solve(i);
}
for (i=1;i<=n;i++)
ans+=p[i][0]<=m?h[i][p[i][0]]:0;
printf("%lld\n",ans);
for (i=1;i<=n;i++)
printf("%d ",p[i][0]>m||!h[i][p[i][0]]?0:p[i][0]);
printf("\n");
return 0;
}
带花树：
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 505
#define M 500050
#define INF 0x7f7f7f7f
int p[N],pre[N],c[M][2],ss=1,vis[N],sta[N],n,m,st=0,li[M];
int fi[N],ri,fa[N],ans=0;
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
inline void Line (int x,int y)
{
c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
return;
}
int Find(int x)
{
return fa[x]==x?x:(fa[x]=Find(fa[x]));
}
int LCA(int x,int y)
{
for (x=Find(x),y=Find(y),st++;;swap(x,y))
if (x)
{
if (vis[x]==st) return x;
vis[x]=st;x=Find(pre[p[x]]);
}
}
void Blossom(int x,int y,int z)
{
while (Find(x)!=z)
{
pre[x]=y;
if (sta[p[x]]==2) sta[li[++ri]=p[x]]=1;
if (fa[x]==x) fa[x]=z;
if (fa[p[x]]==p[x]) fa[p[x]]=z;
x=pre[y=p[x]];
}
return;
}
int Solve(int x)
{
int i,j,k,l,q,w,e,le=1;
memset(pre,0,sizeof(pre));memset(vis,0,sizeof(vis));
memset(sta,0,sizeof(sta));
for (i=1;i<=n;i++) fa[i]=i;li[ri=sta[x]=1]=x;
for (;le<=ri;le++)
for (i=fi[li[le]];i;i=c[i][1])
if (!sta[c[i][0]])
{
sta[c[i][0]]=2;pre[c[i][0]]=li[le];
if (!p[c[i][0]])
{
for (k=c[i][0];k;)
l=p[pre[k]],p[k]=pre[k],p[p[k]]=k,k=l;
return 1;
}
sta[li[++ri]=p[c[i][0]]]=1;
}else
if (sta[c[i][0]]==1&&Find(c[i][0])!=Find(li[le]))
j=LCA(li[le],c[i][0]),Blossom(li[le],c[i][0],j),
Blossom(c[i][0],li[le],j);
return 0;
}
int main()
{
int i,j,k,l,q,w,e;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
Line(Read(),Read());
for (i=1;i<=n;i++)
if (!p[i]) ans+=Solve(i);
printf("%d\n",ans);
for (i=1;i<=n;i++)
printf("%d ",p[i]);
printf("\n");
return 0;
}
这些都可以在UOJ模板题库里面找到。
FFT
其实早在年初就学过几次FFT了，算导也翻过两遍，就是从没写过。
昨天做题目异常烦躁，于是滚去背了下FFT模板（本来是准备早自习抽个时间背的，但是发现这个还是蛮好背的，毕竟带花树都背下来了= =），然后水了两道题。
UOJ#34
贴个模板= =，其实我是从耗时少的里面随便找了一个@kiana的背的，虽然还没看懂这个非递归版本是怎么搞的（其实是不想去认真看了= =），反正感觉也够用了。
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 300050
const double pi=acos(-1.0);
struct complex
{
double r,i;
complex (){}
complex (double _r,double _i) {r=_r;i=_i;}
} a[N],b[N],c[N];
complex operator+(const complex &A,const complex &B)
{return complex(A.r+B.r,A.i+B.i);}
complex operator-(const complex &A,const complex &B)
{return complex(A.r-B.r,A.i-B.i);}
complex operator*(const complex &A,const complex &B)
{return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);}
int n,m,k,len,bit,rev[N];
inline int Read()
{
int x=0;char y;
do y=getchar(); while (y<'0'||y>'9');
do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
return x;
}
void FFT(complex* a,int n,int f)
{
for (int i=0;i<n;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int p=1;p<n;p <<= 1)
{
complex wn(cos(pi/p),sin(pi/p)*f);
for (int i=0;i<n;i+=(p << 1))
{
complex e(1,0);
for (int j=0;j<p;j++,e=e*wn)
{
complex x=a[i+j],y=e*a[i+j+p];
a[i+j]=x+y;a[i+j+p]=x-y;
}
}
}
if (f!=1)
for (int i=0;i<n;i++) a[i].r/=n;
return;
}
int main()
{
n=Read()+1;m=Read()+1;k=n+m-1;len=1;bit=0;
while (len<k) len <<= 1,bit++;
for (int i=0;i<n;i++) a[i].r=Read();
for (int i=0;i<m;i++) b[i].r=Read();
for (int i=1;i<len;i++)
rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1));
FFT(a,len,1);FFT(b,len,1);
for (int i=0;i<len;i++)
c[i]=a[i]*b[i];
FFT(c,len,-1);
for (int i=0;i<k;i++)
printf("%d ",(int)(c[i].r+0.5));
printf("\n");
return 0;
}
BZOJ3527万径人踪灭：
其实就是统计回文子序列个数-回文子串个数，后者直接上manacher，前者就可以直接枚举字符直接套FFT算了。
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300050
#define M 1000000007
#define eps 1e-2
#define ll long long
const double pi=acos(-1.0);
struct complex
{
double r,i;
complex(){}
complex(double _r,double _i) {r=_r;i=_i;}
} a[N],b[N],c[N];
complex operator+(const complex &A,const complex &B)
{return complex(A.r+B.r,A.i+B.i);}
complex operator-(const complex &A,const complex &B)
{return complex(A.r-B.r,A.i-B.i);}
complex operator*(const complex &A,const complex &B)
{return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);}
int n,m,len,bit,rev[N],ss,d[N],ft[N];
ll ans;
void TAT(complex* a,int n,int f)
{
for (int i=0;i<n;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int p=1;p<n;p <<= 1)
{
complex wn(cos(pi/p),sin(pi/p)*f);
for (int i=0;i<n;i+=(p << 1))
{
complex e(1,0);
for (int j=0;j<p;j++,e=e*wn)
{
complex x=a[i+j],y=e*a[i+j+p];
a[i+j]=x+y;a[i+j+p]=x-y;
}
}
}
if (f!=1)
for (int i=0;i<n;i++) a[i].r/=n;
return;
}
void QAQ()
{
int i,j,k,l,q,w,e;
len=1;bit=0;
while (ss>len) len <<= 1,bit++;
for (i=1;i<len;i++)
rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1));
TAT(a,len,1);TAT(b,len,1);
for (i=0;i<len;i++) c[i]=a[i]*b[i];
TAT(c,len,-1);
return;
}
ll Manacher()
{
int i,j,k,l,q,w,e;ll s;
memset(ft,0,sizeof(ft));
q=s=0;e=-1;
for (i=0;i<=ss;i++)
{
ft[i]=i>e?1:min(ft[2*q-i],e-i+1);
while (i-ft[i]>=0&&i+ft[i]<=ss&&d[i-ft[i]]==d[i+ft[i]])
ft[i]++;
if (i+ft[i]-1>e)
{
e=i+ft[i]-1;q=i;
}
s+=ft[i]/2;
}
return s%M;
}
inline ll Quick_mi(ll x,int y)
{
ll z=1;
while (y)
{
if (y&1) z=(z*x)%M;
x=(x*x)%M;
y >>= 1;
}
return z;
}
int main()
{
int i,j,k,l,q,w,e,g[N];char f[N];
memset(d,0,sizeof(d));memset(rev,0,sizeof(rev));
scanf("%s",f);n=strlen(f);
for (i=0;i<n;i++)
d[i*2+1]=int(f[i]);
ss=n*2;ans=(M-Manacher())%M;ss--;
for (i=0;i<n;i++)
a[i].r=b[i].r=f[i]=='a';
QAQ();
for (i=0;i<n;i++)
a[i].r=b[i].r=f[i]!='a',a[i].i=b[i].i=0;
for (i=n;i<len;i++)
a[i].r=b[i].r=a[i].i=b[i].i=0;
for (i=0;i<ss;i++)
g[i]=(eps+c[i].r+(!(i&1)&&f[i/2]=='a'))/2;
QAQ();
for (i=0;i<ss;i++)
g[i]+=(eps+c[i].r+(!(i&1)&&f[i/2]=='b'))/2;
for (i=0;i<ss;i++)
ans=(ans+Quick_mi(2,g[i])-1)%M;
cout <<ans<<endl;
return 0;
}
BZOJ3527力：
坑比lydsy没题面，我是到这里看的题。然后发现这个是可以化成卷积形式的，然后就直接FFT了= =
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define ld long double
#define eps (double)(1e-8)
const double pi=acos(-1.0);
struct complex
{
double r,i;
complex (){}
complex (ld _r,double _i) {r=_r;i=_i;}
} a[N],b[N],c[N],f[N];
complex operator+ (const complex &A,const complex &B)
{return complex(A.r+B.r,A.i+B.i);}
complex operator- (const complex &A,const complex &B)
{return complex(A.r-B.r,A.i-B.i);}
complex operator* (const complex &A,const complex &B)
{return complex(A.r*B.r-A.i*B.i,A.r*B.i+A.i*B.r);}
double d[N];
int n,m,len,bit,rev[N];
void FFT(complex* a,int n,int f)
{
for (int i=0;i<n;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
for (int p=1;p<n;p <<= 1)
{
complex wn(cos(pi/p),sin(pi/p)*f);
for (int i=0;i<n;i+=(p << 1))
{
complex e(1,0);
for (int j=0;j<p;j++,e=e*wn)
{
complex x=a[i+j],y=a[i+j+p]*e;
a[i+j]=x+y;a[i+j+p]=x-y;
}
}
}
if (f!=1)
for (int i=0;i<=n;i++)
a[i].r/=n;
return;
}
int main()
{
int i,j,k,l,q,w,e;
memset(d,0,sizeof(d));memset(rev,0,sizeof(rev));
cin >>n;bit=0;len=1;
for (i=0;i<n;i++) scanf("%lf",&d[i]),
a[i].r=d[i];
for (i=1;i<n;i++) b[i].r=(double)1/i/i;
while (len<n*2) len <<= 1,bit++;
for (i=0;i<len;i++)
rev[i]=(rev[i >> 1] >> 1)|((i&1) << (bit-1));
FFT(a,len,1);FFT(b,len,1);
for (i=0;i<len;i++)
c[i]=a[i]*b[i],c[i].r+=eps;
FFT(c,len,-1);
for (i=0;i<len;i++)
a[i].r=b[i].r=a[i].i=b[i].i=0;
for (i=0;i<n;i++)
a[i].r=d[n-i-1],a[i].i=0,b[i].i=0;
for (i=1;i<n;i++) b[i].r=(double)1/i/i;
FFT(a,len,1);FFT(b,len,1);
for (i=0;i<len;i++)
f[i]=a[i]*b[i];
FFT(f,len,-1);
for (i=0;i<n;i++)
printf("%.3lf\n",c[i].r-f[n-i-1].r);
return 0;
}
话说最近的考试题目真是越来越sxbk了，鸿少的题目里面放了FFT也就算了，破太阳的题目里面放了多项式求逆。
等从杭州滚完粗回来就开推Picks的多项式专题
【捂脸贼】好像摆了半个月才开推啊
之前一直不知道有NTT这个东西，于是感觉要取模实在caodan
感觉NTT、多项式逆元、分治FFT也都不难理解的说。。
BZOJ3456城市规划
写的比较丑，反正就是NTT+高能逆元
好像确实时间常数炸翔了，不过在tsinson上面还是过了
复杂度反正算出来是一个log的
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 1004535809
#define G 3
#define ll long long
ll c[N],S[N],T[N],wn[20],jc[N],C[N];
int n,m,len,bit,rev[N];
ll Quick_Power(ll x,int y)
{
ll z=1;
while (y)
{
if (y&1) z=z*x%M;
x=x*x%M;
y >>= 1;
}
return z;
}
void NTT(ll* a,int n,int f)
{
for (int i=0;i<n-1;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
int now=0;
for (int p=1;p<n;p <<= 1)
{
now++;
for (int i=0;i<n;i+=p << 1)
{
ll e=1;
for (int j=0;j<p;j++,e=e*wn[now]%M)
{
ll x=a[i+j],y=e*a[i+j+p]%M;
a[i+j]=(x+y)%M;a[i+j+p]=(x-y+M)%M;
}
}
}
if (f==-1)
{
for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]);
ll Inv=Quick_Power(n,M-2);
for (int i=0;i<n;i++) a[i]=a[i]*Inv%M;
}
}
void Solve(int x)
{
if (x==1) {T[0]=Quick_Power(S[0],M-2);return;}
Solve(x + 1 >> 1);
len=1;bit=0;
while (len<x*2-1) len <<= 1,bit++;
for (int i=1;i<len;i++)
rev[i]=((rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)));
for (int i=0;i<x;i++) c[i]=S[i];
for (int i=x;i<len;i++) c[i]=0;
NTT(T,len,1);NTT(c,len,1);
for (int i=0;i<len;i++)
T[i]=T[i]*(2-T[i]*c[i]%M+M)%M;
NTT(T,len,-1);
for (int i=x;i<len;i++) T[i]=0;
return;
}
int main()
{
cin >>n;
for (int i=0;i<20;i++) wn[i]=Quick_Power(G,M - 1 >> i);
jc[0]=1;C[0]=1;
for (ll i=1,j=1;i<1 << 18;i++,j=j*i%M)
jc[i]=Quick_Power(j,M-2),C[i]=Quick_Power(2,i*(i-1)/2%(M-1));
for (int i=-1;i<n;i++) S[n-i-1]=C[n-i-1]*jc[n-i-1]%M;
Solve(n+1);
len=1;bit=0;
while (len<n*2-1) len <<= 1,bit++;
for (int i=1;i<len;i++)
rev[i]=((rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)));
for (int i=0;i<n;i++) S[i]=C[i+1]*jc[i]%M;
NTT(S,len,1);NTT(T,len,1);
for (int i=0;i<len;i++) c[i]=S[i]*T[i]%M;
NTT(c,len,-1);
cout <<c[n-1]*Quick_Power(jc[n-1],M-2)%M<<endl;
return 0;
}
然后再附上这题的分治解法，复杂度是log^2 n的，然而在tsinson上面交了一发后面4个点挂时间了
但是感觉这些东西都不算难写，只不过感觉难调
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 300050
#define M 1004535809
#define G 3
#define ll long long
ll S[N],T[N],a[N],b[N],c[N],jc[N],cj[N],C[N],wn[20];
int n,m,rev[N];
ll Quick_Power(ll x,int y)
{
ll z=1;
while (y)
{
if (y&1) z=z*x%M;
x=x*x%M;
y >>= 1;
}
return z;
}
void NTT(ll* a,int n,int f)
{
for (int i=1;i<n-1;i++)
if (i<rev[i]) swap(a[i],a[rev[i]]);
int now=1;
for (int p=1;p<n;p <<= 1,now++)
{
for (int i=0;i<n;i+=p << 1)
{
ll e=1;
for (int j=0;j<p;j++,e=e*wn[now]%M)
{
ll x=a[i+j],y=a[i+j+p]*e%M;
a[i+j]=(x+y)%M;a[i+j+p]=(x-y+M)%M;
}
}
}
if (f==-1)
{
for (int i=1;i<n >> 1;i++) swap(a[i],a[n-i]);
ll Inv=Quick_Power(n,M-2);
for (int i=0;i<n;i++) a[i]=a[i]*Inv%M;
}
}
void Solve(int x,int y)
{
int z=x + y >> 1,len,bit;
if (x==y) {T[x]=(C[x+1]+M-T[x]*cj[x]%M)%M;return;}
Solve(x,z);
len=1;bit=0;
while (len < y - x << 1) len <<= 1,bit++;
for (int i=1;i<len;i++)
rev[i]=(rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
for (int i=x;i<=z;i++) a[i-x]=T[i]*jc[i]%M;
for (int i=z-x+1;i<len;i++) a[i]=0;
for (int i=0;i<=y-x;i++) b[i]=S[i];
for (int i=y-x+1;i<len;i++) b[i]=0;
NTT(a,len,1);NTT(b,len,1);
for (int i=0;i<len;i++) a[i]=a[i]*b[i]%M;
NTT(a,len,-1);
for (int i=z-x+1;i<=y-x;i++) T[i+x]=(T[i+x]+a[i])%M;
Solve(z+1,y);
return;
}
int main()
{
cin >>n;
for (int i=0;i<20;i++) wn[i]=Quick_Power(G,M - 1 >> i);
jc[0]=C[0]=1;cj[0]=1;
for (ll i=1;i<1 << 18;i++)
jc[i]=Quick_Power(cj[i]=i*cj[i-1]%M,M-2),
C[i]=Quick_Power(2,i*(i-1)/2%(M-1));
for (ll i=0;i<n;i++) S[i]=C[i]*jc[i]%M;
Solve(0,n-1);
cout <<T[n-1]%M<<endl;
return 0;
}
