codeforces 442D Adam and Tree
题意:
给出一棵树，最开始只有1个节点。
每个时刻，这棵树会长出一个叶子。
树上每条边都有且只有1种颜色，并且同一种颜色的边都连通。
定义一个点到根的距离为该点到根的路径上的颜色种数。
求每个时刻树上最大距离的最小值。
分析:
考虑每次向上更新dp值，直到更新到根或者不能更新为止。
由树链剖分可知这样做的复杂度是O(nlogn)的。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=1e6+5;
int n;
int dp[MAXN],p[MAXN];
int mx1[MAXN],mx2[MAXN];
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
scanf("%d",&n);
puts("0");
for(int i=2;i<=n;++i){
scanf("%d",p+i);
dp[i]=1;
int cur=i;
while(cur!=1){
int par=p[cur];
if(dp[cur]>mx1[par]){
mx2[par]=mx1[par];
mx1[par]=dp[cur];
}
else if(dp[cur]>mx2[par]){
mx2[par]=dp[cur];
}
cur=par;
int res=max(mx1[cur],mx2[cur]+1);
if(res==dp[cur])break;
dp[cur]=res;
}
printf("%d\n",mx1[1]);
}
return 0;
}
Link
题意:
有n(n<=20000)个小球，最开始都未被染色。
进行m(m<=20000)次操作，操作分为2种类型。
0.回到第x次操作的状态
1.将小球x和y所在的集合合并
然后进行k(k<=20000)次染色操作。
第i次染色操作将时间ti时xi所在连通块中最多zi个小球染色。
如果一个小球被染色了，那么任意时刻它都被染色了。
求最多能将多少小球染色。
分析:
很容易想到网络流的做法，但是一般的建图方法的点数和边数都无法接受。
考虑用可持久化的思想优化网络流建图。
首先处理连通性时我们会用到用主席树实现的可持久化并查集。
注意，这时不能使用路径压缩，要按秩合并来优化。
然后可以发现可持久化并查集就可以来优化建图了。
我们只考虑叶子。
S向最初版本的每个叶子连容量1的边。
每次更新时将历史版本向当前版本连容量为+∞的边；
合并时，向集合代表元连容量为+∞的边。
每次染色时，找到ti版本xi所在集合的代表元，向T连容量为zi的边。
然后跑最大流就行了。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define S 1
#define T 2
#define inf 0x7f7f7f7f
#define gap(i) e[i].c-e[i].f
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=80005;
int Id=2;
typedef struct node*star;
struct node{
int f,id,sz;
star ch[2];
}pool[MAXN*20];
star tail=pool;
inline star query(star x,int l,int r,int pos){
while(l<r){
int mid=(l+r)>>1,d=pos>mid;
if(d)l=mid+1; else r=mid;
x=x->ch[d];
}
return x;
}
int n,m,k,Head[MAXN];
star rt[MAXN];
struct edge{
int t,c,f,n;
edge(int t=0,int c=0,int n=0):
t(t),c(c),f(0),n(n){}
}e[MAXN<<2];
int head[MAXN],tot=1;
inline void AddEdge(int s,int t,int c=1){
e[++tot]=edge(t,c,head[s]),head[s]=tot;
e[++tot]=edge(s,0,head[t]),head[t]=tot;
}
void build(star&x,int l,int r){
x=tail++;
if(l==r){
x->f=l,x->sz=1;
AddEdge(S,x->id=++Id);
return;
}
int mid=(l+r)>>1;
build(x->ch[0],l,mid);
build(x->ch[1],mid+1,r);
}
void update(star&y,star x,int l,int r,int t,int f,int v){
y=++tail; *y=*x;
if(l==r){
y->f=f,y->sz+=v;
AddEdge(x->id,y->id=++Id,inf);
return;
}
int mid=(l+r)>>1,d=t>mid;
if(d)l=mid+1; else r=mid;
update(y->ch[d],x->ch[d],l,r,t,f,v);
}
star find(int idx,int x){
star res=query(rt[idx],1,n,x);
return res->f==x?res:find(idx,res->f);
}
inline void Init(){
Scan(n),Scan(m),Scan(k);
build(rt[0],1,n);
}
inline void Merge(int idx,int x,int y){
star fx=find(idx,x);
star fy=find(idx,y);
if(fx->f==fy->f)return;
if(fx->sz>fy->sz)swap(fx,fy);
update(rt[idx],rt[idx],1,n,fx->f,fy->f,0);
update(rt[idx],rt[idx],1,n,fy->f,fy->f,fx->sz);
fx=query(rt[idx],1,n,fx->f);
fy=query(rt[idx],1,n,fy->f);
AddEdge(fx->id,fy->id,inf);
}
int d[MAXN],p[MAXN],q[MAXN];
int cur[MAXN],g[MAXN];
inline int isap(int s,int t,int n){
rep(i,1,n+1)d[i]=n;
int tail=1;
q[1]=t; d[t]=0;
rep(h,1,tail+1){
int x=q[h];
++g[d[x]],cur[x]=head[x];
for(int i=head[x],y;i;i=e[i].n)
if(!e[i].c&&d[y=e[i].t]==n){
d[y]=d[x]+1;
q[++tail]=y;
}
}
int flow=0,x=s,a,f;
while(d[s]<n){
if(x==t){
a=inf;
for(int i=t;i!=s;i=e[p[i]^1].t)
a=min(a,gap(p[i]));
for(int i=t;i!=s;i=e[p[i]^1].t)
e[p[i]].f+=a,e[p[i]^1].f-=a;
flow+=a;
x=s;
}
f=1;
for(int&i=cur[x];i;i=e[i].n)
if(gap(i)&&d[x]==d[e[i].t]+1){
f=0;
p[x=e[i].t]=i;
break;
}
if(f){
if(!(--g[d[x]]))break;
f=n-1;
for(int i=head[x];i;i=e[i].n)
if(gap(i))f=min(f,d[e[i].t]);
++g[d[x]=f+1];
cur[x]=head[x];
if(x!=s)x=e[p[x]^1].t;
}
}
return flow;
}
inline void Solve(){
rep(i,1,m+1){
rt[i]=rt[i-1];
int t,x,y;
Scan(t),Scan(x);
if(t)Scan(y),Merge(i,x,y);
else rt[i]=rt[x];
}
rep(i,0,k){
int x,y,w;
Scan(x),Scan(y),Scan(w);
star f=find(x,y);
AddEdge(f->id,T,w);
}
printf("%d\n",isap(S,T,Id));
}
int main(){
freopen("link.in","r",stdin);
freopen("link.out","w",stdout);
Init(); Solve(); return 0;
}
Run
题意:
给出一张图(点数为n,边数为m)的一个生成树和一些非树边。
每条非树边有一个代价w，表示炸毁这条边需要付出的代价。
求炸毁一些非树边使得图中不存在偶环所付出的最小代价。
特别地，生成树上点的度数不超过10.
数据范围:n<=1000,m<=4000
分析:
首先如果一条非树边跨越了树上奇数条边，则这条边必须炸毁。
剩下的边，如果任意两条边所跨越的树上路径有公共边，则会存在偶环。
考虑到每个节点的儿子最多只有10个，我们可以考虑状压dp.
令f[x][s]表示以x为根的子树,只考虑集合s中儿子时能保留的边的最大权值。
令g[x][i]表示以x为根的子树,不考虑x的第i个儿子时能保留的边的最大权值。
每条非树边，只在它的端点的lca处考虑影响。
为了让路径不重复，则该非树边所覆盖的路径都不能被选。
暴力从一个端点到lca统计不考虑路径上的边时的最大权值。
再与该非树边没有覆盖的部分一起更新答案。
复杂度O(n*210+n*m)
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define Max(x,y) if(x<y)x=y
#define Min(x,y) if(x>y)x=y
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=1005;
const int MAXS=1<<10;
int n,m;
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
e[++tot]=edge(t,head[s]),head[s]=tot;
e[++tot]=edge(s,head[t]),head[t]=tot;
}
int p[MAXN],dep[MAXN];
vector<int>ch[MAXN],qy[MAXN];
void dfs(int x){
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
p[y]=x;
dep[y]=dep[x]+1;
ch[x].pb(y);
dfs(y);
}
}
inline int lca(int x,int y){
if(dep[x]>dep[y])swap(x,y);
while(dep[y]>dep[x])y=p[y];
while(p[x]!=p[y])x=p[x],y=p[y];
return x==y?x:p[x];
}
struct edge1{
int u,v,w;
inline void scan(){
Scan(u),Scan(v),Scan(w);
}
}tmp[MAXN*5];
int ans;
inline void Init(){
Scan(n),Scan(m);
rep(i,1,m+1){
tmp[i].scan();
ans+=tmp[i].w;
if(!tmp[i].w){
AddEdge(tmp[i].u,tmp[i].v);
}
}
dfs(1);
rep(i,1,m+1){
if(!tmp[i].w)continue;
int u=tmp[i].u,v=tmp[i].v;
int Lca=lca(u,v);
if((dep[u]+dep[v]-dep[Lca]*2)&1)continue;
qy[Lca].pb(i);
}
}
int dp[MAXN];
int f[MAXN][MAXS],g[MAXN][10];
inline int swim(int x,int par,int&res){
int ban=-1;
while(x!=par){
if(~ban)res+=g[x][ban];
else res+=dp[x];
int s=ch[p[x]].size();
rep(i,0,s)
if(x==ch[p[x]][i]){
ban=i; break;
}
x=p[x];
}
return ban;
}
void tree_dp(int x){
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x])tree_dp(y);
int s=ch[x].size();
int maxs=1<<s;
rep(set,0,maxs){
int res=0;
rep(i,0,s)
if(set>>i&1){
res+=dp[ch[x][i]];
}
Max(f[x][set],res);
}
int c=qy[x].size();
rep(i,0,c){
int u=tmp[qy[x][i]].u;
int v=tmp[qy[x][i]].v;
int res=tmp[qy[x][i]].w;
int bu=max(0,1<<swim(u,x,res));
int bv=max(0,1<<swim(v,x,res));
rep(set,0,maxs){
if(bu&&(set&bu)==bu||bv&&(set&bv)==bv)
continue;
int ns=set^bu^bv;
Max(f[x][ns],res+f[x][set]);
}
}
rep(set,0,maxs){
rep(i,0,s)
if(!(set>>i&1)){
Max(g[x][i],f[x][set]);
}
Max(dp[x],f[x][set]);
}
}
inline void Solve(){
tree_dp(1);
ans-=dp[1];
printf("%d\n",ans);
}
int main(){
freopen("run.in","r",stdin);
freopen("run.out","w",stdout);
Init(); Solve(); return 0;
}
听说下雨天，分块和莫队更配哦~
恩。。。先跪PoPoQQQ
bzoj3585 mex
题目大意: 询问区间mex值
这题有用线段树的O(nlogn)做法，以前发过了，所以这里不做讨论
既然是区间询问且支持离线的数据结构题，我们很容易想到用莫队算法。
那么问题就在于区间之间如何转移。
想法1: 用平衡树维护插入和删除，询问时在平衡树上二分。
这样做每次插入、删除和询问都是O(logn)的
由于莫队算法需要进行O(q*sqrt(n))次插入或删除，则总的复杂度会达到O(q*sqrt(n)*logn).
这个做法的瓶颈在于插入和删除时的花费太大。
想法2: 将权值分块，维护每种权值出现的次数和每块有多少种权值出现。
这样可以做到每次O(1)的插入和删除，插入和删除的总
询问时先暴力找到第一个存在未存在的数的块，再在这个块内暴力，复杂度O(sqrt(n))。
虽然询问的复杂度高于上一种做法，但是实际上询问只会有q次，总的复杂度依然是O(n*sqrt(n)).
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=2e5+5;
int n,m,B,tot;
int a[MAXN],pos[MAXN];
struct qy{
int l,r,id;
}q[MAXN];
inline bool cmp(const qy&a,const qy&b){
if(pos[a.l]!=pos[b.l])return a.l<b.l;
return pos[a.l]&1?a.r<b.r:a.r>b.r;
}
inline void Init(){
Scan(n),Scan(m);
B=sqrt(n)+1;
tot=n/B+1;
rep(i,1,n+1){
Scan(a[i]);
if(a[i]>n)a[i]=n;
}
rep(i,0,n+1)pos[i]=i/B+1;
rep(i,1,m+1){
Scan(q[i].l),Scan(q[i].r);
q[i].id=i;
}
}
int cnt[MAXN],cnt1[MAXN];
inline void Add(int x){
if(++cnt[x]==1)++cnt1[pos[x]];
}
inline void Del(int x){
if(!(--cnt[x]))--cnt1[pos[x]];
}
inline int query(){
int i=1;
for(;i<=tot&&cnt1[i]==B;++i);
for(i=(i-1)*B;cnt[i]&&i<n;++i);
return i;
}
int ans[MAXN];
inline void Solve(){
sort(q+1,q+1+m,cmp);
int l=q[1].l,r=q[1].r;
rep(i,l,r+1)Add(a[i]);
ans[q[1].id]=query();
rep(i,2,m+1){
int ll=q[i].l,rr=q[i].r;
for(;r<rr;Add(a[++r]));
for(;r>rr;Del(a[r--]));
for(;l>ll;Add(a[--l]));
for(;l<ll;Del(a[l++]));
ans[q[i].id]=query();
}
rep(i,1,m+1)
printf("%d\n",ans[i]);
}
int main(){
Init(); Solve(); return 0;
}
bzoj4129 Haruna's Breakfast
题目大意: 询问树上两点间路径的mex值，支持单点修改
这题是上一题的加强版，从线形推广到树形。
这题如果从线段树入手会十分困难(其实是博主太弱了不会这样做，有会这种做法的请联系我)
考虑到莫队算法是可以推广到树上的，我们直接用上一题的思路就好了。
由于带修改，对树分块时块的大小最好设为n2/3,对权值分块还是sqrt(n)就好。
简单说下树上路径的转移方法，为了方便，以下所说的路径均不含lca。
假设现在的路径是(x1,y1),需要转移到路径(x2,y2).
我们将路径(x1,x2),(y1,y2)取反，就得到了(x2,y2).
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=50005;
int B1,Bn,a[MAXN],pos[MAXN];
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
e[++tot]=edge(t,head[s]),head[s]=tot;
e[++tot]=edge(s,head[t]),head[t]=tot;
}
int n,m,B2,bel[MAXN],siz[MAXN];
struct qy{
int x,y,z,id;
qy(int x=0,int y=0,int z=0,int id=0):
x(x),y(y),z(z),id(id){}
}q[MAXN];
inline bool cmp(const qy&a,const qy&b){
if(bel[a.x]!=bel[b.x])return bel[a.x]<bel[b.x];
if(bel[a.y]!=bel[b.y])
return bel[a.x]&1?bel[a.y]<bel[b.y]:bel[a.y]>bel[b.y];
return bel[a.y]&1?a.z<b.z:a.z>b.z;
}
struct tarjan{
int x,id,n;
tarjan(int x=0,int id=0,int n=0):x(x),id(id),n(n){}
}t[MAXN<<1];
int thd[MAXN],qtot;
inline void AddTarjan(int x,int y,int id){
t[++qtot]=tarjan(y,id,thd[x]),thd[x]=qtot;
t[++qtot]=tarjan(x,id,thd[y]),thd[y]=qtot;
}
bool col[MAXN];
int f[MAXN];
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
int p[MAXN],dep[MAXN],lca[MAXN];
void dfs(int x){
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
if(siz[bel[x]]<B2){
++siz[bel[y]=bel[x]];
}
p[y]=x;
dep[y]=dep[x]+1;
dfs(y);
}
col[x]=1;
for(int i=thd[x],y;i;i=t[i].n)
if(col[y=t[i].x])lca[t[i].id]=find(y);
f[x]=p[x];
}
bool on[MAXN];
int cnt[MAXN],cnt1[MAXN];
inline void Add(int x){
if(++cnt[x]==1)++cnt1[pos[x]];
}
inline void Del(int x){
if(--cnt[x]==0)--cnt1[pos[x]];
}
inline int query(){
int i=1;
for(;i<Bn&&cnt1[i]==B1;++i);
for(i=(i-1)*B1;i<n&&cnt[i];++i);
return i;
}
inline void Xor(int x){
on[x]^=1;
if(on[x])Add(a[x]);
else Del(a[x]);
}
struct modify{
int x,f,t;
modify(int x=0,int f=0,int t=0):
x(x),f(f),t(t){}
}mo[MAXN];
int mod_tot,qy_tot;
inline void change(int x,int y){
if(on[x])Del(a[x]);
a[x]=y;
if(on[x])Add(a[x]);
}
inline void Modify(int cur,int to){
for(;cur<to;++cur)change(mo[cur+1].x,mo[cur+1].t);
for(;cur>to;--cur)change(mo[cur].x,mo[cur].f);
}
inline void Rev(int x,int y){
if(dep[x]>dep[y])swap(x,y);
while(dep[y]>dep[x])Xor(y),y=p[y];
while(x!=y)Xor(x),Xor(y),x=p[x],y=p[y];
}
int ans[MAXN];
inline void Init(){
Scan(n),Scan(m);
B1=sqrt(n),Bn=n/B1+1;
B2=pow(n,2./3);
pos[0]=1;
rep(i,1,n+1){
pos[i]=i/B1+1;
Scan(a[i]);
if(a[i]>n)a[i]=n;
f[i]=bel[i]=i;
}
rep(i,1,n){
int x,y;
Scan(x),Scan(y);
AddEdge(x,y);
}
rep(i,1,m+1){
int t,x,y;
Scan(t),Scan(x),Scan(y);
if(t){
++qy_tot;
q[qy_tot]=qy(x,y,mod_tot,qy_tot);
AddTarjan(x,y,qy_tot);
}
else{
if(y>n)y=n;
mo[++mod_tot]=modify(x,a[x],y);
a[x]=y;
}
}
dfs(1);
rep(i,1,qy_tot+1){
if(bel[q[i].x]>bel[q[i].y])
swap(q[i].x,q[i].y);
}
}
inline void Solve(){
sort(q+1,q+1+qy_tot,cmp);
int x=q[1].x,y=q[1].y,z=q[1].z;
int Lca=lca[q[1].id];
Modify(mod_tot,z);
Rev(x,y);
Xor(Lca);
ans[q[1].id]=query();
Xor(Lca);
rep(i,2,qy_tot+1){
Modify(z,q[i].z),z=q[i].z;
Rev(x,q[i].x),x=q[i].x;
Rev(y,q[i].y),y=q[i].y;
Lca=lca[q[i].id];
Xor(Lca);
ans[q[i].id]=query();
Xor(Lca);
}
rep(i,1,qy_tot+1){
printf("%d\n",ans[i]);
}
}
int main(){
Init(); Solve(); return 0;
}
存一下最近几场比赛的代码
太弱没脸发题解，反正有官方题解对吧
CH弱省胡策
r3:
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define eps 1e-8
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
const int MAXN=5e5+5;
const int MAXM=3005;
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN];
int head[MAXN];
inline void AddEdge(int s,int t){
static int o=1;
e[o]=edge(t,head[s]),head[s]=o++;
}
int par[MAXN][20],dep[MAXN];
int rt;
void prev(int x){
if(dep[x])return;
if(~*par[x]){
prev(*par[x]);
AddEdge(*par[x],x);
dep[x]=dep[*par[x]]+1;
for(int i=0;par[x][i];++i)
par[x][i+1]=par[par[x][i]][i];
}
else rt=x,dep[x]=1;
}
int B[MAXN],R[MAXN];
int b[MAXN],r[MAXN],w[MAXN];
bool u[MAXN];
int n,m,k,l;
inline int swim(int x,int h){
for(int i=0;h;++i,h>>=1)
if(h&1)x=par[x][i];
return x;
}
void dp(int x){
for(int i=head[x],y;i;i=e[i].n){
dp(y=e[i].t);
B[x]+=B[y],R[x]+=R[y];
}
}
typedef double db;
const db pi=acos(-1.);
#define sqr(x) (db(x)*(x))
struct poi{
int x,y,w;
poi(int x=0,int y=0,int w=0):
x(x),y(y),w(w){}
inline db alpha(){return atan2(y,x);}
}p[MAXM];
inline poi operator-(const poi&a,const poi&b){
return poi(a.x-b.x,a.y-b.y);
}
inline void Init(){
Scan(n),Scan(k),Scan(l);
rep(i,1,n){
Scan(b[i]),Scan(r[i]);
Scan(w[i]),Scan(*par[i]),Scan(u[i]);
}
rep(i,1,n)prev(i);
rep(i,1,n){
B[i]+=b[i],R[i]+=r[i];
if(dep[i]<=k)continue;
int y=swim(i,k);
B[y]-=b[i],R[y]-=r[i];
}
dp(rt);
rep(i,1,n)
if(u[i])p[++m]=poi(B[i],R[i],w[i]);
}
inline db normalize(db x){
while(x<-pi)x+=pi*2.;
while(x>=pi)x-=pi*2.;
return x;
}
struct event{
db alpha;
int w;
event(db alpha=0,int w=0):alpha(alpha),w(w){}
}eve[MAXM<<2];
int tot;
inline bool cmp(const event&a,const event&b){
return a.alpha!=b.alpha?a.alpha<b.alpha:a.w>b.w;
}
inline db dis(const poi&a,const poi&b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
inline int calc(int x){
tot=0;
rep(i,1,m){
if(i==x)continue;
db L=dis(p[x],p[i]);
if(L-l*2>eps)continue;
db alpha=(p[i]-p[x]).alpha();
db delta=acos(L/(l*2));
db s=normalize(alpha-delta);
db t=normalize(alpha+delta);
eve[++tot]=event(s,p[i].w);
eve[++tot]=event(t,-p[i].w);
if(s>t){
eve[++tot]=event(-pi,p[i].w);
eve[++tot]=event(pi,-p[i].w);
}
}
sort(eve+1,eve+1+tot,cmp);
int res=0,sum=0;
rep(i,1,tot){
sum+=eve[i].w;
res=max(res,sum);
}
return res+p[x].w;
}
inline void Solve(){
int ans=0;
rep(i,1,m)ans=max(ans,calc(i));
printf("%d\n",ans);
}
int main(){
Init(); Solve(); return 0;
}
#include <map>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inv(x,P) qpow(x,P-2,P)
#define DFT(a,n,P) fft(a,n,0,P)
#define IDFT(a,n,P) fft(a,n,1,P)
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
const int MAXN=(1<<18)+5;
typedef unsigned long long ll;
const int P1=1004535809;
const int P2=998244353;
const int G=3;
const ll P=(ll)P1*P2;
inline ll qpow(ll x,ll k,ll M){
ll ans=1;
for(;k;x=x*x%M,k>>=1)
if(k&1)ans=ans*x%M;
return ans;
}
int w[2][MAXN],r[MAXN],rn;
inline void init_fft(int n,int bit,int P){
rn=inv(n,P);
int g=qpow(G,(P-1)/n,P);
w[0][0]=w[0][n]=1;
rep(i,1,n-1)w[0][i]=(ll)w[0][i-1]*g%P;
rep(i,0,n)w[1][i]=w[0][n-i];
rep(i,1,n)r[i]=(r[i>>1]>>1)|((i&1)<<(bit-1));
}
inline void fft(int*a,int n,int t,int P){
rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1)
for(int j=0;j<n;j+=i)
for(int k=0;k<i>>1;++k){
int re=(ll)a[(i>>1)+j+k]*w[t][n/i*k]%P;
a[(i>>1)+j+k]=(a[j+k]+P-re)%P;
a[j+k]=(a[j+k]+re)%P;
}
if(t)rep(i,0,n-1)a[i]=(ll)a[i]*rn%P;
}
bool ban[MAXN];
int p[MAXN],phi[MAXN],tot;
inline void get_phi(int n){
phi[1]=1;
rep(i,2,n){
if(!ban[i]){
p[++tot]=i;
phi[i]=i-1;
}
rep(j,1,tot){
if((ll)i*p[j]>n)break;
int x=i*p[j];
ban[x]=1;
if(i%p[j]){
phi[x]=phi[i]*(p[j]-1);
}
else{
phi[x]=phi[i]*p[j];
break;
}
}
}
rep(i,1,n)phi[i]%=23;
}
inline ll qmul(ll a,ll b,ll M){
ll ans=0;
for(;b;b>>=1,a=(a<<1)%M)
if(b&1)ans=(ans+a)%M;
return ans;
}
const int r_P2=inv(P2,P1);
const int r_P1=inv(P1,P2);
inline ll crt(ll x1,ll x2){
ll ans=0;
ans+=qmul(qmul(x1,P2,P),r_P2,P);
ans+=qmul(qmul(x2,P1,P),r_P1,P);
return ans%P;
}
int n,len,bit;
int a[MAXN],c[MAXN];
map<int,int>g;
inline void Init(){
Scan(n);
get_phi(n);
len=n<<1,bit=1;
while(1<<bit<len)++bit;
len=1<<bit;
g[1]=0;
int tmp=1;
rep(i,1,100000){
tmp=(ll)tmp*G%P1;
g[tmp]=i;
}
rep(i,0,n-1){
Scan(a[i]);
if(i)a[i]=(a[i]+a[i-1])%P1;
}
rep(i,0,n-1)a[i]=g[a[i]];
}
int a1[MAXN],a2[MAXN];
int c1[MAXN],c2[MAXN];
inline void calc_C(){
rep(i,0,n-1){
a1[i]=a2[i]=a[i];
c1[i]=c2[i]=phi[i];
}
init_fft(len,bit,P2);
DFT(a2,len,P2),DFT(c2,len,P2);
rep(i,0,len-1)c2[i]=(ll)a2[i]*c2[i]%P2;
IDFT(c2,len,P2);
init_fft(len,bit,P1);
DFT(a1,len,P1),DFT(c1,len,P1);
rep(i,0,len-1)c1[i]=(ll)a1[i]*c1[i]%P1;
IDFT(c1,len,P1);
rep(i,0,n-1)c[i]=qpow(G,crt(c1[i],c2[i])%(P1-1),P1);
for(int i=n;i;--i)c[i]=c[i-1];
c[0]=0;
}
inline void Solve(){
calc_C();
DFT(c,len,P1);
rep(i,0,len-1)c[i]=(ll)c[i]*c[i]%P1;
IDFT(c,len,P1);
int ans=0;
rep(i,0,n)ans=(ans+c[i])%P1;
printf("%d\n",ans);
}
int main(){
Init(); Solve(); return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
const int MAXN=5e6+5;
const int Mod=1e9+7;
typedef long long ll;
bool ban[MAXN];
int p[MAXN],tot;
int fac[MAXN],fib[MAXN];
inline void get_prime(int n){
fib[1]=fac[1]=1;
rep(i,2,n){
fib[i]=(fib[i-1]+fib[i-2])%Mod;
if(!ban[i])p[++tot]=i,fac[i]=i;
rep(j,1,tot){
if(1ll*i*p[j]>n)break;
ban[i*p[j]]=1;
fac[i*p[j]]=p[j];
if(!(i%p[j]))break;
}
}
}
int n,f[MAXN];
inline int gcd(int a,int b){
for(;b;swap(a,b),b%=a);
return a;
}
int ans,mx;
inline void Init(){
get_prime(5e6);
Scan(n);
rep(i,1,n){
int tp,x;Scan(tp);
if(tp){
int a,b;
Scan(a),Scan(b);
x=a+b-gcd(a,b);
}
else Scan(x);
++f[x];
ans=(ans+fib[x])%Mod;
mx=max(x,mx);
}
}
ll d[MAXN];
void div(int x,int cur,int v){
if(x==1){
d[cur]+=v;
return;
}
else{
int res=fac[x],cnt=0,tmp=1;
for(;!(x%res);++cnt,x/=res);
rep(i,0,cnt){
div(x,cur*tmp,v);
tmp*=res;
}
}
}
inline void Solve(){
rep(i,1,mx)if(f[i])div(i,1,f[i]);
for(int i=mx;i;--i){
if(!d[i])continue;
d[i]=d[i]*(d[i]-1)>>1;
for(int j=i<<1;j<=mx;j+=i)d[i]-=d[j];
ans=(ans+d[i]*fib[i]%Mod)%Mod;
}
printf("%d\n",ans);
}
int main(){
Init(); Solve(); return 0;
}
r4
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define eps 1e-6
#define inf 1e20
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define fore(i,x) for(int i=head[x];i;i=e[i].n)if(e[i].c>e[i].f)
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
const int MAXN=2000;
typedef double db;
struct edge{
int t;db c,f;int n;
edge(int t=0,db c=0,db n=0):
t(t),c(c),f(0),n(n){}
}e[MAXN<<2];
int head[MAXN],tot;
inline void AddEdge(int s,int t,db c){
e[++tot]=edge(t,c,head[s]),head[s]=tot;
e[++tot]=edge(s,0,head[t]),head[t]=tot;
}
int d[MAXN],p[MAXN],g[MAXN],cur[MAXN];
int q[MAXN];
inline db isap(int s,int t,int n){
rep(i,1,n)d[i]=n;
rep(i,0,n)g[i]=0;
int tail=1;
q[tail]=t,d[t]=0;
for(int j=1;j<=tail;++j){
int x=q[j];
for(int i=head[x],y;i;i=e[i].n)
if(!e[i].c&&d[y=e[i].t]==n){
d[y]=d[x]+1;
q[++tail]=y;
}
}
rep(i,1,n){
cur[i]=head[i],++g[d[i]];
}
db flow=0,a;int x=s,f;
while(d[s]<n){
if(x==t){
a=inf;
for(int i=t;i!=s;i=e[p[i]^1].t){
a=min(a,e[p[i]].c-e[p[i]].f);
}
for(int i=t;i!=s;i=e[p[i]^1].t){
e[p[i]].f+=a,e[p[i]^1].f-=a;
}
flow+=a;
x=s;
}
f=1;
for(int&i=cur[x];i;i=e[i].n)
if(e[i].c>e[i].f&&d[x]==d[e[i].t]+1){
f=0,p[x=e[i].t]=i; break;
}
if(f){
if(!(--g[d[x]]))break;
f=n-1;
fore(i,x)f=min(f,d[e[i].t]);
++g[d[x]=f+1];
cur[x]=head[x];
if(x!=s)x=e[p[x]^1].t;
}
}
return flow;
}
inline void clear(){
memset(head,0,sizeof head);
tot=1;
}
int n,m;
#define S n+m+1
#define T n+m+2
int c[MAXN];
int u[MAXN],v[MAXN],w[MAXN];
db sum;
inline void Init(){
Scan(n),Scan(m);
rep(i,1,n)Scan(c[i]);
rep(i,1,m){
Scan(u[i]),Scan(v[i]);
Scan(w[i]);
}
}
inline bool check(db x){
clear();
sum=0;
rep(i,1,m){
AddEdge(S,i+n,w[i]),sum+=w[i];
}
rep(i,1,n)AddEdge(i,T,x*c[i]);
rep(i,1,m){
AddEdge(i+n,u[i],inf);
AddEdge(i+n,v[i],inf);
}
sum-=isap(S,T,T);
return sum<eps;
}
inline void Solve(){
db l=0,r=1e9;
while(r-l>eps){
db mid=(l+r)/2.;
if(check(mid))r=mid;
else l=mid;
}
printf("%.2f\n",l);
}
int main(){
Init(); Solve(); return 0;
}
留坑QAQ
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define inf 0x7f7f7f7f
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
const int MAXN=50005;
struct edge{
int t,n;
edge(int t=0,int n=0):t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
e[++tot]=edge(t,head[s]),head[s]=tot;
e[++tot]=edge(s,head[t]),head[t]=tot;
}
int sum[MAXN]={-1},dis[MAXN];
int n,p[MAXN],w[MAXN],mx[MAXN][2];
void dfs(int x){
sum[x]=w[x];
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
p[y]=x,dfs(y);
sum[x]+=sum[y];
dis[x]+=sum[y]+dis[y];
if(sum[y]>sum[mx[x][0]]){
mx[x][1]=mx[x][0];
mx[x][0]=y;
}
else if(sum[y]>sum[mx[x][1]]){
mx[x][1]=y;
}
}
}
int find(int x,int s=0,int c=0){
int res=dis[x]+s+c;
if(mx[x][0]){
int y=mx[x][0];
int ns=s+c+dis[x]-dis[y]-sum[y];
int nc=c+sum[x]-sum[y];
int tmp=dis[y]+ns+nc;
if(tmp<res){
return find(y,ns,nc);
}
}
return res;
}
bool flag[MAXN];
void remove(int x){
int y=p[x];
flag[x]= x==mx[y][0];
if(flag[x])mx[y][0]=mx[y][1];
int t=dis[x];
while(y){
t+=sum[x];
dis[y]-=t;
sum[y]-=sum[x];
flag[y]= y==mx[p[y]][0];
if(flag[y]){
if(sum[mx[p[y]][1]]>sum[y]){
mx[p[y]][0]=mx[p[y]][1];
}
}
y=p[y];
}
}
void recover(int x){
int y=p[x];
if(flag[x])mx[y][0]=x;
int t=dis[x];
while(y){
t+=sum[x];
dis[y]+=t;
sum[y]+=sum[x];
if(flag[y])mx[p[y]][0]=y;
y=p[y];
}
}
int rt,ans=inf;
void dp(int x){
for(int i=head[x],y;i;i=e[i].n)
if((y=e[i].t)!=p[x]){
remove(y);
ans=min(ans,find(y)+find(rt));
recover(y);
dp(y);
}
}
inline void Init(){
Scan(n);
for(int i=1,x,y;i<n;++i){
Scan(x),Scan(y);
AddEdge(x,y);
}
for(int i=1;i<=n;++i)Scan(w[i]);
dfs(rt=1);
}
inline void Solve(){
dp(rt);
printf("%d\n",ans);
}
int main(){
Init(); Solve(); return 0;
}
r5
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define DFT(a,n) fft(a,n,0)
#define IDFT(a,n) fft(a,n,1)
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef long long ll;
const int P=998244353;
inline ll qpow(ll x,int k){
ll ans=1;
for(;k;x=x*x%P,k>>=1)
if(k&1)ans=ans*x%P;
return ans;
}
const int MAXN=(1<<18)+5;
int r[MAXN],w[2][MAXN],rn;
inline void init_fft(int n,int b){
rn=qpow(n,P-2);
int g=qpow(3,(P-1)/n);
w[0][0]=w[0][n]=1;
rep(i,1,n)w[0][i]=1ll*w[0][i-1]*g%P;
rep(i,0,n+1)w[1][i]=w[0][n-i];
rep(i,1,n){
r[i]=(r[i>>1]>>1)|((i&1)<<(b-1));
}
}
inline void fft(int*a,int n,int t){
rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1)
for(int j=0;j<n;j+=i)
for(int k=0;k<i>>1;++k){
int v=1ll*a[(i>>1)+j+k]*w[t][n/i*k]%P;
a[(i>>1)+j+k]=(a[j+k]+P-v)%P;
a[j+k]=(a[j+k]+v)%P;
}
if(t)rep(i,0,n)a[i]=1ll*a[i]*rn%P;
}
int n,l,bit;
int a[MAXN],b[MAXN];
int fac[MAXN],inv[MAXN];
int x[MAXN],y[MAXN];
inline void Init(){
Scan(n);
rep(i,0,n+1)Scan(b[i]);
l=n<<1|1,bit=1;
while(1<<bit<l)++bit;
l=1<<bit;
init_fft(l,bit);
fac[0]=1;
rep(i,1,n+1)fac[i]=1ll*fac[i-1]*i%P;
inv[0]=inv[1]=1;
rep(i,2,n+1){
int a=P/i,b=P%i;
inv[i]=1ll*a*(P-inv[b])%P;
}
rep(i,2,n+1)
inv[i]=1ll*inv[i]*inv[i-1]%P;
}
inline void Solve(){
rep(i,0,n+1){
x[i]=1ll*fac[n-i]*b[n-i]%P;
if((n-i)&1)if(x[i])x[i]=P-x[i];
}
rep(i,0,n+1)y[i]=inv[i];
DFT(x,l),DFT(y,l);
rep(i,0,l)x[i]=1ll*x[i]*y[i]%P;
IDFT(x,l);
rep(i,0,n+1){
a[i]=1ll*inv[i]*x[n-i]%P;
if(i&1)if(a[i])a[i]=P-a[i];
}
rep(i,0,n+1)printf("%d ",a[i]);
}
int main(){
Init(); Solve(); return 0;
}
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
const int MAXN=305;
int n,k;
int e[MAXN][MAXN];
int main(){
Scan(n),Scan(k);
rep(i,1,n+1)e[i][i]=1;
int m=n-k+1;
rep(i,1,m+1)rep(j,i+1,m+1)
e[i][j]=e[j][i]=1;
rep(i,m+1,n+1)e[i][i-1]=e[i-1][i]=1;
rep(i,1,n+1){
rep(j,1,n+1)putchar(e[i][j]+48);
puts("");
}
return 0;
}
留坑QAQ
UOJ Round#8
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lch x->l,l,mid
#define rch x->r,mid+1,r
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
const int MAXN=2e5+5;
typedef struct node*star;
struct data{
int l_iro,r_iro;
int iro_cnt;
data(int l_iro=0,int r_iro=0,int iro_cnt=0):
l_iro(l_iro),r_iro(r_iro),iro_cnt(iro_cnt){}
};
inline data operator+(const data&a,const data&b){
data c;
c.l_iro=a.l_iro,c.r_iro=b.r_iro;
c.iro_cnt=a.iro_cnt+b.iro_cnt;
if(a.r_iro==b.l_iro)--c.iro_cnt;
return c;
}
struct node{
data d;
star l,r;
}pool[MAXN<<4];
star tail=pool;
void build(int*a,star&x,int l,int r){
x=tail++;
if(l==r){
x->d=data(a[l],a[l],1);
return;
}
int mid=(l+r)>>1;
build(a,lch),build(a,rch);
x->d=x->l->d+x->r->d;
}
inline data query(star x,int l,int r,int ll,int rr){
if(l==ll&&r==rr)return x->d;
int mid=(l+r)>>1;
if(rr<=mid)return query(lch,ll,rr);
if(ll>mid) return query(rch,ll,rr);
return query(lch,ll,mid)+query(rch,mid+1,rr);
}
star rta,rtb;
int n,m,q,a[MAXN],b[MAXN];
int main(){
Scan(n),Scan(m);
for(int i=1;i<=n;++i)Scan(a[i]);
for(int i=1;i<=n;++i)a[i+n]=a[i];
build(a,rta,1,n<<1);
for(int i=1;i<=m;++i)Scan(b[i]);
for(int i=1;i<=m;++i)b[i+m]=b[i];
build(b,rtb,1,m<<1);
Scan(q);
for(int i=1;i<=q;++i){
int sx,sy,tx,ty;
Scan(sx),Scan(sy),Scan(tx),Scan(ty);
if(sx>tx)swap(sx,tx);
if(sy>ty)swap(sy,ty);
int t1=query(rta,1,n<<1,sx,tx).iro_cnt;
t1=min(t1,query(rta,1,n<<1,tx,sx+n).iro_cnt);
int t2=query(rtb,1,m<<1,sy,ty).iro_cnt;
t2=min(t2,query(rtb,1,m<<1,ty,sy+m).iro_cnt);
int ans=t1+t2-2;
printf("%d\n",ans);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lch x->l,l,mid
#define rch x->r,mid+1,r
#define LL long long
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
const int MAXN=2e5+5;
typedef struct node*star;
struct data{
int min,max;
data(int min=0,int max=0):
min(min),max(max){}
};
inline data operator+(const data&a,const data&b){
return data(min(a.min,b.min),max(a.max,b.max));
}
struct node{
data d;
bool rev;
inline void rev_it(){
d.min=100000-d.min;
d.max=100000-d.max;
swap(d.min,d.max);
rev^=1;
}
inline void down(){
if(!rev)return;
l->rev_it(),r->rev_it();
rev=0;
}
inline void updt(){
d=l->d+r->d;
}
star l,r;
}pool[MAXN<<4];
star tail=pool;
void build(int*a,star&x,int l,int r){
x=tail++;
if(l==r){
x->d=data(a[l],a[l]);
return;
}
int mid=(l+r)>>1;
build(a,lch),build(a,rch);
x->updt();
}
LL ans;
inline LL calc(int a,int b,int c,int x,int y){
return 1ll*a*x+1ll*b*y+1ll*c*x*y;
}
inline void query(star x,int l,int r,int ll,int rr,int a,int b,int c){
if(ll>r||rr<l)return;
if(l==r){
ans=max(ans,calc(a,b,c,l,x->d.max));
return;
}
LL g=calc(a,b,c,min(r,rr),x->d.max);
if(g<=ans)return;
int mid=(l+r)>>1;
x->down();
LL g1=calc(a,b,c,min(mid,rr),x->l->d.max);
LL g2=calc(a,b,c,min(r,rr),x->r->d.max);
if(g1>g2)query(lch,ll,rr,a,b,c),query(rch,ll,rr,a,b,c);
else query(rch,ll,rr,a,b,c),query(lch,ll,rr,a,b,c);
}
int y[MAXN];
inline void modify(star x,int l,int r,int pos,int y){
if(l==r){
x->d=data(y,y);
return;
}
int mid=(l+r)>>1;
x->down();
if(pos>mid)modify(rch,pos,y);
else modify(lch,pos,y);
x->updt();
}
inline void modify1(star x,int l,int r,int ll,int rr){
if(ll<=l&&r<=rr)return x->rev_it();
x->down();
int mid=(l+r)>>1;
if(ll<=mid)modify1(lch,ll,rr);
if(rr>mid) modify1(rch,ll,rr);
x->updt();
}
int n,m,q,x0;
const int P=998244353;
inline int rand_x(){
return (x0=((1ll*x0*100000005%P+20150609)%P))/100;
}
star rt;
inline void Solve(){
build(y,rt,1,n);
for(int i=1;i<=m;++i){
char c;while(c=g(),c<'A'||c>'Z');
if(c=='C'){
int x=rand_x()%n+1;
int y1=rand_x()%100001;
modify(rt,1,n,x,y1);
}
else if(c=='R'){
int l=rand_x()%n+1;
int r=rand_x()%n+1;
if(l>r)swap(l,r);
modify1(rt,1,n,l,r);
}
else{
int l=rand_x()%n+1;
int r=rand_x()%n+1;
if(l>r)swap(l,r);
int a,b,c;
Scan(a),Scan(b),Scan(c);
ans=-1ll<<60;
query(rt,1,n,l,r,a,b,c);
printf("%lld\n",ans);
}
}
}
int main(){
Scan(n),Scan(m),Scan(x0);
for(int i=1;i<=n;++i)
y[i]=rand_x()%100001;
Solve();
return 0;
}
留坑QAQ
TopCoder SRM518 Div1 1000 Nim
题意:
有k(k<=109)堆石子，每堆石子的数量都是不大于L(L<=50000)的质数，
问有多少种初始状态是先手必败状态，mod 1000000007
定义卷积C=A*B,Cn=∑i,j [i^j=n]*Ai*Bj,则答案为[x0]Ak,其中Ai=[i为质数]
Fast Walsh Transform
考虑一种Transformation u(f),满足u(A)*u(B)=u(A*B),
并且存在u(f)的Inverse Transformation v(f),满足v(u(f))=f
假设向量x的长度为n
当n为1时,显然u(x)=x,因为0^0=0,满足u(A)*u(B)=u(A*B)
当n为2时，设A=(x1,y1),B=(x2,y2),则A*B=(x1*x2+y1*y2,x1*y2+x2*y1)
设x=(x1,x2),此时dwt(x)=(x1-x2,x1+x2)
dwt(A)*dwt(B)=((x1-y1)*(x2-y2),(x1+y1)*(x2+y2))=dwt(A*B)
对于n为大于等于2的2的整次幂,x=(x1,x2),x1和x2的长度为n/2
dwt(x)=(dwt(x1)-dwt(x2),dwt(x1)+dwt(x2))
令y=dwt(x),考虑其逆变换idwt(y)=x,当n=1时同理idwt(y)=y
当n为大于等于2的2的整次幂,y=(y1,y2),
解方程y1=dwt(x1)-dwt(x2),y2=dwt(x1)+dwt(x2)
解得:idwt(y)=(idwt((y1+y2)/2),idwt((y2-y1)/2))
虽然我并不清楚这是怎么想出来的，但是在知道有这个变换的情况下，
理解它的正确性还是比较容易的，而且它的形式也很优美呢。
class Nim{
public:
static const int MAXN=(1<<17)+5;
static const int Mod=1e9+7;
typedef long long ll;
inline ll qpow(ll x,int k,int M){
ll ans=1;
for(;k;x=x*x%M,k>>=1)
if(k&1)ans=ans*x%M;
return ans;
}
int r2;
int a[MAXN];
void dwt(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,len=r-mid;
dwt(l,mid),dwt(mid+1,r);
for(int i=l;i<=mid;++i){
int x=a[i],y=a[i+len];
a[i]=(x-y+Mod)%Mod;
a[i+len]=(x+y)%Mod;
}
}
void idwt(int l,int r){
if(l==r)return;
int mid=(l+r)>>1,len=r-mid;
for(int i=l;i<=mid;++i){
int x=1ll*a[i]*r2%Mod;
int y=1ll*a[i+len]*r2%Mod;
a[i]=(x+y)%Mod;
a[i+len]=(y+Mod-x)%Mod;
}
idwt(l,mid),idwt(mid+1,r);
}
bool ban[MAXN];
int p[MAXN],tot;
inline void get_prime(int n){
ban[1]=1;
for(int i=2;i<=n;++i){
if(!ban[i])p[++tot]=i;
for(int j=1;j<=tot;++j){
if(1ll*i*p[j]>n)break;
ban[i*p[j]]=1;
if(!(i%p[j]))break;
}
}
}
inline int count(int K,int L){
r2=qpow(2,Mod-2,Mod);
get_prime(L);
for(int i=1;i<=L;++i)a[i]=!ban[i];
int l=1<<16;
dwt(0,l-1);
for(int i=0;i<l;++i)
a[i]=qpow(a[i],K,Mod);
idwt(0,l-1);
return a[0];
}
};
codechef Milestones
题意:
平面上有n(n<=10000)个点,已知用7条直线就能完全覆盖它们.
求最多用1条直线可以覆盖多少个点
随机1000次就能过了。。。
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define g() getchar()
template<class Q>void Scan(Q&x){
char c;int f=1;
while(c=g(),c<48||c>57)if(c=='-')f=-1;
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
x*=f;
}
#define rep(i,a,b) for(int i=a;i<b;++i)
typedef int ll;
const int MAXN=10005;
struct poi{
ll x,y;
inline void scan(){
Scan(x),Scan(y);
}
poi(ll x=0,ll y=0):x(x),y(y){}
}p[MAXN];
inline poi operator-(const poi&a,const poi&b){
return poi(a.x-b.x,a.y-b.y);
}
inline ll cross(const poi&a,const poi&b){
return a.x*b.y-a.y*b.x;
}
int T,n,ans;
inline int calc(int s,int t){
if(s==t)(++t)%=n;
int res=0;
rep(i,0,n)
if(!cross(p[i]-p[s],p[t]-p[s]))++res;
return res;
}
inline void Solve(){
Scan(n);
rep(i,0,n)p[i].scan();
ans=0;
rep(i,0,1000){
ans=max(ans,calc(rand()%n,rand()%n));
}
printf("%d\n",ans);
}
int main(){
srand(time(0));
for(Scan(T);T--;Solve());
return 0;
}
codeforces round290 Div1 E Fox And Polygon
题意:
给出一个正n边形和它的一个三角剖分.
要求通过每次选择两个相邻的三角形，将它们构成的四边形的对角线翻转
使得最后变为该正n边形的另一个三角剖分。
先找出将任意三角剖分化为同一个三角剖分的方法。
然后，就可以一个正着做，一个反着做来达到目的了。
将任意三角剖分化为以1号点为剖分点的扇形剖分，顺时针考虑每一个应该出现的剖分边,如果它不存在，
就找到一条阻碍它存在的剖分边，将它取反。
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAXN=1005;
bool e[MAXN][MAXN];
int n;
inline void clear(){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
e[i][j]=0;
}
typedef pair<int,int>op;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
vector<op>s;
int type;
inline void Xor(int x,int y){
for(int i=2;i<=n;++i)
if(e[i][x]&&e[i][y]){
e[x][y]=e[y][x]=0;
e[1][i]=e[i][1]=1;
if(!type)s.pb(mp(x,y));
else s.pb(mp(1,i));
break;
}
}
inline void Solve(){
clear();
for(int i=3,x,y;i<n;++i){
scanf("%d%d",&x,&y);
e[x][y]=e[y][x]=1;
}
for(int i=1;i<=n;++i){
int j=i+1;
if(i==n)j=1;
e[i][j]=e[j][i]=1;
}
s.clear();
for(int i=2;i<=n;){
if(e[1][i]){
++i;
continue;
}
for(int j=i+1;j<=n;++j)
if(e[1][j]){
Xor(i-1,j);
break;
}
}
}
op ans[MAXN*20];
int cnt;
int main(){
scanf("%d",&n);
Solve();
for(int i=0;i<s.size();++i)
ans[++cnt]=s[i];
type=1;
Solve();
for(int i=s.size();i;--i)
ans[++cnt]=s[i-1];
printf("%d\n",cnt);
for(int i=1;i<=cnt;++i)
printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}
codechef Random Number Generator
题意:求常系数齐次递推数列的第n项
当递推系数非零项很多的时候暴力复位一次是O(k2)的
构造特征矩阵M的特征多项式f(x)=xk-∑i ci*xi
由f(M)=0,那么我们复位时只需要mod f(x)就好
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define g() getchar()
template<class Q>void Scan(Q&x){
char c; while(c=g(),c<48||c>57);
for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}
#define G 3
#define maxn 65536
#define DFT(a,n) fft(a,n,0)
#define IDFT(a,n) fft(a,n,1)
#define INV(x) qpow(x,P-2)
#define rep(i,a,b) for(int i=a;i<(b);++i)
using namespace std;
const int MAXN=(1<<16)+5;
const int P=104857601;
typedef long long ll;
inline ll qpow(ll x,int k){
ll ans=1;
for(;k;x=x*x%P,k>>=1)
if(k&1)ans=ans*x%P;
return ans;
}
int r[MAXN],w[2][MAXN],rn;
inline void init_fft(int n,int b){
rn=INV(n);
rep(i,1,n){
r[i]=(r[i>>1]>>1)|((i&1)<<(b-1));
}
}
inline void fft(int*a,int n,int t){
rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1)
for(int j=0;j<n;j+=i)
for(int k=0;k<i>>1;++k){
int re=1ll*a[(i>>1)+j+k]*w[t][maxn/i*k]%P;
a[(i>>1)+j+k]=(a[j+k]+P-re)%P;
a[j+k]=(a[j+k]+re)%P;
}
if(t)rep(i,0,n)a[i]=1ll*a[i]*rn%P;
}
int k,len,bit;
inline void inv(int*a,int*b){
static int c[MAXN],l;
b[0]=1,b[1]=0,l=1;
rep(j,1,bit+1){
l<<=1;
rep(i,0,l)c[i]=a[i];
rep(i,l,l<<1)b[i]=c[i]=0;
init_fft(l<<1,j+1);
DFT(b,l<<1),DFT(c,l<<1);
rep(i,0,l<<1){
b[i]=1ll*b[i]*(2+P-1ll*b[i]*c[i]%P)%P;
}
IDFT(b,l<<1);
rep(i,l,l<<1)b[i]=0;
}
}
int m[MAXN],dm[MAXN],im[MAXN];
int ta[MAXN],ra[MAXN];
inline void mod(int*a){
DFT(ta,len),DFT(a,len);
rep(i,0,len)a[i]=1ll*a[i]*ta[i]%P;
IDFT(a,len);
rep(i,0,k-1)ra[i]=a[(k-1<<1)-i];
rep(i,k-1,len)ra[i]=0;
DFT(ra,len);
rep(i,0,len)ra[i]=1ll*ra[i]*im[i]%P;
IDFT(ra,len);
rep(i,0,k-1)ta[i]=ra[k-2-i];
rep(i,k-1,len)ta[i]=0;
DFT(ta,len);
rep(i,0,len)ta[i]=1ll*ta[i]*dm[i]%P;
IDFT(ta,len);
rep(i,0,k)a[i]=(a[i]+P-ta[i])%P;
rep(i,k,len)a[i]=0;
}
inline void Init(){
int n=maxn;
int g=qpow(G,(P-1)/n);
w[0][0]=w[0][n]=1;
rep(i,1,n)w[0][i]=1ll*w[0][i-1]*g%P;
rep(i,0,n+1)w[1][i]=w[0][n-i];
}
ll n;
int a[MAXN],ans[MAXN],x[MAXN];
int main(){
Init();
Scan(k),Scan(n),--n;
len=k+1,bit=1;
while(1<<bit<len)++bit;
len=1<<bit;
rep(i,0,k)Scan(a[i]);
for(int i=k-1;~i;--i){
Scan(m[i]),m[i]=(P-m[i])%P;
}
if(k==1){
int res=qpow((P-m[0])%P,n%(P-1))*a[0]%P;
printf("%d\n",res);
return 0;
}
m[k]=1;
rep(i,0,k+1)dm[i]=m[k-i];
inv(dm,im);
len<<=1,++bit;
rep(i,0,k+1)dm[i]=m[i];
rep(i,k+1,len)dm[i]=im[i]=0;
DFT(dm,len),DFT(im,len);
for(ans[0]=x[1]=1;n;n>>=1){
if(n&1){
rep(i,0,len)ta[i]=x[i];
mod(ans);
}
rep(i,0,len)ta[i]=x[i];
mod(x);
}
int res=0;
rep(i,0,k){
res=(res+1ll*a[i]*ans[i])%P;
}
printf("%d\n",res);
return 0;
}
hdu4914 Linear recursive sequence
题意:给出序列f,fn=(n>0)?a*fn-p+b*fn-q:1,求第n项
叉姐论文: k阶矩阵M的任意幂次都能用M小于k次的幂次来线性表示
所以我们构造多项式fn(x),[xi]fn(x)表示用小于k次的幂次线性表示时i次幂前的系数
用多项式乘法+快速幂计算fn(x),每次乘法后溢出k-1次的部分暴力还原
这题 mod 119，中间结果不会太大，所以直接用复数域上的fft，做完一次乘法后再取模就好
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define DFT(a) fft(a,len,0)
#define IDFT(a) fft(a,len,1)
#define rep(i,a,b) for(int i=a;i<(b);++i)
using namespace std;
const int MAXN=(1<<18)+5;
typedef double db;
const db Pi=acos(-1.);
typedef long long ll;
const int Mod=119;
struct cp{
db r,i;
cp(db r=0,db i=0):r(r),i(i){}
friend cp operator+(const cp&a,const cp&b){
return cp(a.r+b.r,a.i+b.i);
}
friend cp operator-(const cp&a,const cp&b){
return cp(a.r-b.r,a.i-b.i);
}
friend cp operator*(const cp&a,const cp&b){
return cp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
}
}w[2][MAXN];
inline cp Exp(db x){
return cp(cos(x),sin(x));
}
int r[MAXN];
inline void init_fft(int n,int b){
w[0][0]=w[0][n]=cp(1.,0);
cp g=Exp(Pi*2./n);
rep(i,1,n)w[0][i]=w[0][i-1]*g;
rep(i,0,n+1)w[1][i]=w[0][n-i];
rep(i,1,n){
r[i]=(r[i>>1]>>1)|((i&1)<<(b-1));
}
}
inline void fft(cp*a,int n,int t){
rep(i,1,n)if(i<r[i])swap(a[i],a[r[i]]);
for(int i=2;i<=n;i<<=1)
for(int j=0;j<n;j+=i)
for(int k=0;k<i>>1;++k){
cp re=a[(i>>1)+j+k]*w[t][n/i*k];
a[(i>>1)+j+k]=a[j+k]-re;
a[j+k]=a[j+k]+re;
}
if(t)rep(i,0,n)a[i].r/=n;
}
cp ta[MAXN],tb[MAXN];
int n,A,B,p,q,len,bit;
struct poly{
int a[MAXN];
inline void mul(const poly&o){
rep(i,0,q)ta[i]=cp(a[i]),tb[i]=cp(o.a[i]);
rep(i,q,len)ta[i]=tb[i]=cp();
DFT(ta),DFT(tb);
rep(i,0,len)ta[i]=ta[i]*tb[i];
IDFT(ta);
rep(i,0,len)a[i]=ll(ta[i].r+0.5)%Mod;
for(int i=len;i>=q;--i)if(a[i]){
a[i-p]=(a[i-p]+a[i]*A%Mod)%Mod;
a[i-q]=(a[i-q]+a[i]*B%Mod)%Mod;
}
}
}a,b;
inline void qpow(poly&ans,poly&x,int k){
rep(i,0,len)ans.a[i]=x.a[i]=0;
ans.a[0]=x.a[1]=1;
for(;k;x.mul(x),k>>=1)
if(k&1)ans.mul(x);
}
int f[MAXN];
inline int F(int x){return x>0?f[x]:1;}
int main(){
while(~scanf("%d%d%d%d%d",&n,&A,&B,&p,&q)){
A%=Mod,B%=Mod;
rep(i,1,q<<1|1){
f[i]=(F(i-p)*A+F(i-q)*B)%Mod;
}
if(n<=(q<<1)){
printf("%d\n",f[n]);
continue;
}
len=q<<1|1,bit=1;
while(1<<bit<len)++bit;
len=1<<bit;
init_fft(len,bit);
qpow(a,b,n-q);
int ans=0;
for(int i=q-1;~i;--i){
ans=(ans+a.a[i]*f[i+q])%Mod;
}
printf("%d\n",ans);
}
return 0;
}
