@OceanEye7年前
08/7
16:03
@OceanEye7年前
06/17
21:52
生日攻击
请手动google
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <cstdio> #include <ctime> #include <cstdlib> using namespace std; #define N 100000 int main() { printf("%d %d\n",N,20); for(int i=1;i<=N;i++) putchar(rand()%26+'a'); puts(""); return 0; } |
BZOJ3098
@OceanEye7年前
05/24
21:29
代码
无脑用Lucas化简 分类后分段递归处理
|
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 <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; // lucas C(n/m)%p = C(n/p,m/p)*C(n%p,m%p)%p #define MOD 2333 #define M MOD+100 int sum[M][M],c[M][M]; void Dec(int &x) { while(x>=MOD) x-=MOD; } void pre() { c[0][0]=sum[0][0]=1; For(i,1,MOD-1) sum[0][i]=1; For(i,1,MOD-1) { c[i][0]=sum[i][0]=1; for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j]+c[i-1][j-1]),Dec(c[i][j]); for(int j=1;j<MOD;j++) sum[i][j]=(sum[i][j-1]+c[i][j]),Dec(sum[i][j]); } } int calc_single(ll n,ll m) { if(m<0||n<m) return 0; if(m<MOD&&n<MOD) return c[n][m]; int ret=1,_,__; for(;n&&m&&ret;n/=MOD,m/=MOD) { _=n%MOD; __=m%MOD; if(_<__) return 0; ret*=c[_][__]; ret%=MOD; } return ret; // return calc_single(n/MOD,m/MOD)*c[n%MOD][m%MOD]%MOD; } int calc(ll n,ll k) { if(k<0) return 0; return (calc(n/MOD,k/MOD-1)*sum[n%MOD][MOD-1]%MOD+sum[n%MOD][k%MOD]*calc_single(n/MOD,k/MOD)%MOD)%MOD; } int main() { ll t,n,k; pre(); for(read(t);t;t--) { read(n); read(k); printf("%d\n",calc(n,k)); } return 0; } |
BZOJ4591
@OceanEye7年前
05/24
13:18
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; } |
BZOJ2982
@OceanEye7年前
05/21
13:46
先上几个好的教程
- 某不知名大佬的教程 简直良心治好了我一直没搞清楚的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; } |
[代码施工中]
FFT—-学习笔记
@OceanEye7年前
05/3
18:56
期望DP
和班上的一个物理大佬一起搞了二十分钟吧……然后发现这个期望(R,B)只和(R-1,B)以及(R,B-1)相关
然后就一个for循环再用一下滚动数组就可以了
dp[r][b]=(dp[r][b-1]-1)*b/(r+b) + (dp[r-1][b]+1)*r/(r+b)
|
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 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') 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; int R,B; double dp[2][5050]; #define now i&1 #define pre now^1 int main() { read(R); read(B); for(int i=0;i<=B;i++) { for(int j=1;j<=R;j++) dp[now][j]=max(0.0,((dp[pre][j]-1)*((double)i/(i+j)))+((dp[now][j-1]+1)*((double)j/(i+j)))); } printf("%.6f",dp[B&1][R]-5e-7); return 0; } |