这是新坑……
同时开了KDT和LCT的坑【不知道的同学等下就知道了】
READ MORE →
Link Cut Tree 学习笔记
先上一份代码……回去研究研究 @Sdchr
READ MORE →
后缀数组学习笔记
BZOJ2730
XDDD YY了半天的点双联通忽略了最初点双的性质—-割点可能属于多个块
代码施工中
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
#include <cstdio> #include <algorithm> #include <cstring> #include <vector> #include <cstdlib> #define ll long long #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define SIZ 1010 #define N 1000 struct node { int fa,dfn,mn,childcnt; bool iscut; vector <int> belong; void init() { belong.clear(); fa=dfn=mn=childcnt=iscut=0; } }pool[SIZ]; #define FA pool[x].fa #define MN pool[x].mn #define DFN pool[x].dfn #define CNT pool[x].childcnt #define ISCUT pool[x].iscut struct Tedge { int from,to; bool use; Tedge(int _=0,int __=0,bool ___=false) { from=_; to=__; use=false; } bool operator != (const Tedge &x) { return (from!=x.from||to!=x.to); } } edge[N<<1],STA[N]; int TOP; #define E edge[i] #define TO E.to int e_tot,fst[SIZ],cur[SIZ],NXT[N<<1]; void add_e(int a,int b) { edge[e_tot]=Tedge(a,b,false); NXT[e_tot]=fst[a]; fst[a]=e_tot++; edge[e_tot]=Tedge(b,a,false); NXT[e_tot]=fst[b]; fst[b]=e_tot++; } vector <int> BCC[SIZ]; int siz[SIZ],cnt[SIZ],tot; int sta[SIZ],top; bool use[SIZ]; unsigned ll ans1,ans2; // void init(int n) { memset(fst,-1,sizeof(fst)); memset(siz,0,sizeof(siz)); memset(cnt,0,sizeof(cnt)); e_tot=0; tot=0; ans1=0; ans2=1; for(int i=1;i<=N;i++) BCC[i].clear(); int _,__; For(i,1,n) { read(_); read(__); use[_]|=1; use[__]|=1; add_e(_,__); } } void cp(int &x,int y) { x>y?x=y:x=x; } int cd; void tarjan(int x) { use[x]=false; DFN=MN=++cd; for(int i=fst[x];~i;i=NXT[i]) { if(TO==FA) continue; if(edge[i].use) continue; STA[++TOP]=E; E.use=true; i^=1; E.use=true; i^=1; if(!use[TO]) cp(MN,pool[TO].dfn); else { CNT++; pool[TO].fa=x; tarjan(TO); MN=min(MN,pool[TO].mn); if(pool[TO].mn>=DFN) { Tedge cur; tot++; ISCUT=true; do { cur=STA[TOP--]; if(pool[cur.from].belong.size()==0||pool[cur.from].belong.back()!=tot) { pool[cur.from].belong.push_back(tot); BCC[tot].push_back(cur.from); } if(pool[cur.to].belong.size()==0||pool[cur.to].belong.back()!=tot) { pool[cur.to].belong.push_back(tot); BCC[tot].push_back(cur.to); } } while(cur!=E); } } } if(CNT<2&&!FA) ISCUT=false; } int time; void Main(int _) { time++; init(_); For(i,1,1000) cur[i]=fst[i],pool[i].init(); For(i,1,1000) if(use[i]) tarjan(i); For(i,1,1000) { if(!pool[i].dfn) continue; if(!pool[i].iscut) { siz[pool[i].belong[0]]++; continue; } for(int j=0;j<pool[i].belong.size();j++) cnt[pool[i].belong[j]]++,siz[pool[i].belong[j]]++; } For(i,1,tot) if(cnt[i]==1) { ans1++; ans2*=(unsigned ll)(siz[i]==1?1:(siz[i]-1)); } else if(cnt[i]==0) { ans1+=min(siz[i],2); ans2*=(unsigned ll)siz[i]*(siz[i]-1)/2; } printf("Case %d: %llu %llu\n",time,ans1,ans2); } int main() { freopen("BZOJ2730.in","r",stdin); memset(cur,-1,sizeof(cur)); int T; read(T); for(;T;read(T)) Main(T); return 0; } |
BZOJ2982
Lucas定理裸题
恩具体证明请百度 Lucas定理
刚刚发现我是RK3 :-D高兴
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
//---------------OceanEye's Code----------------------// #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define MOD 10007 #define M MOD+100 int pre[M]; void init() { pre[0]=1; for(int i=1;i<=MOD;i++) pre[i]=pre[i-1]*i%MOD; } int ksm(int a,int k) { int ret=1; for(;k;k>>=1) { if(k&1) ret=(ret*a)%MOD; a*=a; a%=MOD; } return ret; } #define calc_inv(p) (ksm(p,MOD-2)) int comb(int n,int m) { return pre[n]*calc_inv(pre[m]*pre[n-m]%MOD)%MOD; } int Lucas(int n,int m) { int ret=1,_,__; while(n&&m&&ret) { _=n%MOD; __=m%MOD; if(_<__) return 0; ret*=comb(_,__); ret%=MOD; n/=MOD; m/=MOD; } return ret; } int main() { int t,n,m; init(); for(read(t);t;t--) { read(n); read(m); printf("%d\n",Lucas(n,m)); } return 0; } |
FFT—-学习笔记
先上几个好的教程
- 某不知名大佬的教程 简直良心治好了我一直没搞清楚的FFT:-D
- zky大佬的FFT教程
- kry大佬的板子:-D
[手动分割]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #define ll long long #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read(T &x) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 1<<22 int n,m; int pos[N]; int k,j; const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0){ r=_r; i=_i; } comp operator+(const comp&x) { return comp(r+x.r,i+x.i); } comp operator-(const comp&x) { return comp(r-x.r,i-x.i); } comp operator*(const comp&x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() {return comp(r,-i);} }a[N],b[N]; void fft(comp a[],int n,int t) { for(int i=1;i<n;i++) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++) { int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(int j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=w*A; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { freopen("BZOJ2179FFT.in","r",stdin); read(n); read(m); for(k=1;k<=n||k<=m;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1) pos[i]=pos[i>>1]>>1|((i&1)<<j); // For(i,0,k-1) printf("%d\n",pos[i]); For(i,0,n) read(j),a[i].r=j; For(i,0,m) read(j),a[i].i=j; fft(a,k,1); For(i,0,k-1) { j=(k-i)&(k-1); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); For(i,0,n+m) printf("%d ",(int)(b[i].r+0.5)); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <cmath> #define ll long long #define db double #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } template <class T>void rd( T &x ) { cc=getchar(); while(!p(cc)) cc=getchar(); x=cc-'0'; } using namespace std; #define N 1<<17 const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0) { r=_r; i=_i; } comp operator+ (const comp &x) { return comp(r+x.r,i+x.i); } comp operator- (const comp &x) { return comp(r-x.r,i-x.i); } comp operator* (const comp &x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() { return comp(r,-i); } }a[N],b[N]; int n,k,j,pos[N]; ll c[N]; char na[N]; void fft(comp a[],int n,int t) { For(i,0,n-1) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int d=0;(1<<d)<n;d++) { int m=1<<d,m2=m<<1; double o=pi*2/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=A*w; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { read(n); n--; for(k=1;k<=n;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1) pos[i]=(pos[i>>1]>>1)|((i&1)<<j); For(i,0,n) rd(j),a[i].r=j; For(i,0,n) rd(j),a[i].i=j; fft(a,k,1); For(i,0,k-1) { j=(k-i)&(k-1); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); For(i,0,n*2) c[i]=(ll)(b[i].r+0.4); bool flag=false; int a=0,tot=0; for(int i=n*2;i>=0;i--) { a+=c[i]; na[tot++]=(char)(a%10); a/=10; } if(a) na[tot++]=(char)a; for(;tot;putchar(na[--tot]+'0')); return 0; } |
BZOJ2194
好像就是反过来？
挺裸的:-D
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <cmath> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define N 1<<21 const double pi=acos(-1.0); struct comp { double r,i; comp(double _r=0,double _i=0) { r=_r; i=_i; } comp operator+ (const comp &x) { return comp(r+x.r,i+x.i); } comp operator- (const comp &x) { return comp(r-x.r,i-x.i); } comp operator* (const comp &x) { return comp(r*x.r-i*x.i,r*x.i+i*x.r); } comp conj() { return comp(r,-i); } }a[N],b[N]; int k,j,n; int pos[N]; void fft(comp a[],int n,int t) { For(i,0,n-1) if(pos[i]>i) swap(a[i],a[pos[i]]); for(int k=0;(1<<k)<n;k++) { int m=1<<k,m2=m<<1; double o=2*pi/m2*t; comp _w(cos(o),sin(o)); for(int i=0;i<n;i+=m2) { comp w(1,0); for(j=0;j<m;j++) { comp &A=a[i+j+m],&B=a[i+j],t=A*w; A=B-t; B=B+t; w=w*_w; } } } if(t==-1) For(i,0,n-1) a[i].r/=n; } int main() { read(n); n--; for(k=1;k<=n;k<<=1); k<<=1; j=__builtin_ctz(k)-1; For(i,0,k-1)pos[i]=(pos[i>>1]>>1)|((i&1)<<j); For(i,0,n){ read(j); a[i].r=j; read(j); a[n-i].i=j; } fft(a,k,1); For(i,0,k-1) { j=(k-1)&(k-i); b[i]=(a[i]*a[i]-(a[j]*a[j]).conj())*comp(0,-0.25); } fft(b,k,-1); for(int i=n;i<=n*2;i++) printf("%d\n",(int)(b[i].r+0.5)); return 0; } |
[代码施工中]
BZOJ1834
嘛……几万年没好好写过网络流了……
gap优化真的强，把我的1s的代码降成了0.05s
相信前面榜上的就是gap的吧……
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 |
/************************************************************** Problem: 1834 User: OceanEYe Language: C++ Result: Accepted Time:56 ms Memory:1948 kb ****************************************************************/ #include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <vector> #include <queue> #include <set> #define p(x) ('0'<=x&&x<='9') #define INF 100000000 char cc; int C; template <class T> void read(T &x) { cc=getchar(); C=1; x=0; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) x=x*10+cc-48,cc=getchar(); x*=C; } template <class T> void MN(T &x,T y) { x>y?x=y:x=x; } using namespace std; #define N 1005 #define E 10010 struct Tedge { int from,to,cap,flow; int val; }edge[E<<2]; #define TO edge[i].to #define VAL edge[i].val #define SIZ (edge[i].cap-edge[i].flow) #define CAP edge[i].cap int fst[N],NXT[E<<2],e_tot; void add_e(int _,int __,int ___,int ____) { edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].from=_; edge[e_tot].val=____; NXT[e_tot]=fst[_]; fst[_]=e_tot++; edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; edge[e_tot].from=__; edge[e_tot].val=-____; NXT[e_tot]=fst[__]; fst[__]=e_tot++; } int S,T; struct rec { int a,b,c,d; rec(int _,int __,int ___,int ____): a(_),b(__),c(___),d(____) {} }; vector <rec> R; int n,m,k; void init1() { read(n); read(m); read(k); S=1; T=n; int _,__,___,____; memset(fst,-1,sizeof(fst)); for(int i=1;i<=m;i++) { read(_); read(__); read(___); read(____); add_e(_,__,___,0); R.push_back(rec(_,__,___,____)); } } // bool vis[N]; int d[N],cnt[N],p[N],pre[N],ans; int Augment() { int r=T,c=INF,i; while(r!=S) { i=pre[r]; MN(c,CAP-SIZ); r=TO; } r=T; while(r!=S) { i=pre[r]; edge[i].flow-=c; edge[i^1].flow+=c; r=TO; } return c; } void ISAP() { int node=S,c; for(int i=1;i<=n;i++) p[i]=fst[i]; bool flag; while(d[S]<=n) { if(node==T) { ans+=Augment(); node=S; } //solve flag=false; for(int i=p[node];~i;i=NXT[i]) { if(d[TO]!=d[node]-1||SIZ==0) continue; p[node]=i; pre[TO]=i^1; node=TO; flag=true; break; } if(flag) continue; c=n+10; for(int i=fst[node];~i;i=NXT[i]) { if(!SIZ) continue; MN(c,d[TO]+1); } if(--cnt[d[node]]==0) { printf("%d ",ans); return; } cnt[d[node]=c]++; p[node]=fst[node]; if(node!=S)node=edge[pre[node]].to; //retreat } printf("%d ",ans); } queue<int> Q; void bfs() { int x; memset(vis,0,sizeof(vis)); d[T]=1; Q.push(T); vis[T]^=1; while(!Q.empty()) { x=Q.front(); Q.pop(); cnt[d[x]]++; for(int i=fst[x];~i;i=NXT[i]) { if(vis[TO]||SIZ) continue; d[TO]=d[x]+1; Q.push(TO); vis[TO]^=1; } } } // int dis[N],cost; void init2() { int _,__,___,____; for(int i=0;i<m;i++) { _=R[i].a; __=R[i].b; ____=R[i].d; add_e(_,__,INF,____); } } int Augment2() { int r=T,c=0,i; while(r!=S) { i=pre[r]; edge[i].flow--; edge[i^1].flow++; c+=edge[i^1].val; r=TO; } return c; } void SPFA() { memset(dis,0x7f,sizeof(dis)); memset(vis,false,sizeof(vis)); dis[S]=0; Q.push(S); vis[S]=true; int x,i; while(!Q.empty()) { x=Q.front(); Q.pop(); vis[x]=false; for(i=fst[x];~i;i=NXT[i]) { if(!SIZ) continue; if(dis[TO]<=dis[x]+VAL) continue; dis[TO]=dis[x]+VAL; pre[TO]=i^1; if(vis[TO]) continue; vis[TO]=true; Q.push(TO); } } cost+=Augment2(); } // int main() { init1(); bfs(); ISAP(); init2(); for(int i=1;i<=k;i++) SPFA(); printf("%d\n",cost); return 0; } |