4
11
2016
0

[BZOJ4318] OSU!

一道简单的期望DP题。。但是我这种题还要看别人的题解。。毕竟DP能力太差

考虑我们已经确定好了前k-1位的期望得分，那么当前第k位有两种情况:

1.操作成功为1，这么做的贡献就等于前面连续1的个数加上1后再三次方的得分然后减去前面的得分期望

2.操作失败为0，那么贡献为0

然后我们需要维护x,x2两个量，然后因为期望的线性性，我们每一次直接加上就好了

?
bzoj 4318
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
 
int n;
double a[100005],x[100005],x2[100005],dp[100005];
 
int main(){
freopen("4318.in","r",stdin);
freopen("4318.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
for(int i=1;i<=n;i++){
    x[i]=(x[i-1]+1)*a[i];
    x2[i]=(x2[i-1]+2*x[i-1]+1)*a[i];
    dp[i]=dp[i-1]+(3*x2[i-1]+3*x[i-1]+1)*a[i];
}
printf("%.1lf\n",dp[n]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
11
2016
0

[BZOJ3993] [SDOI2015]星际战争

二分时间，跑实数网络流就可以了

貌似速度还很快- -

?
bzoj 3993
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
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
 
const int INF=2100000000;
const double eps=1e-6;
 
int n,m,level[5005],h[5005],cur[5005],S,T,en,Mt[55][55];
double A[55],B[55],Sum;
queue<int> Q;
 
struct Edge{
int b,back,next;
double f;
}e[100005];
 
double Abs(double x){return x>0?x:-x;}
 
void AddEdge(int sa,int sb,double sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}
 
int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(e[i].f<eps || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
    }
}
return level[T];
}
 
double DFS(int u,double flow){
if(u==T)return flow;
double f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    double fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))>eps){
        f-=fl;
        e[i].f-=fl;
        e[e[i].back].f+=fl;
        if(f<eps)return flow;
    }
}
return flow-f;
}
 
double Dinic(){
double ans=0;
while(BFS()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=DFS(S,(double)INF);}
return ans;
}
 
bool Test(double Ts){
memset(h,0,sizeof(h));
en=0;
S=n+m+1;
T=n+m+2;
for(int i=1;i<=m;i++)AddEdge(S,i,Ts*B[i]);
for(int i=1;i<=n;i++)AddEdge(i+m,T,A[i]);
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        if(Mt[i][j])AddEdge(i,j+m,INF);
    }
}
return Abs(Dinic()-Sum)<eps;
}
 
double Div(){
double l=0,r=100000000,ans;
while(r-l>eps){
    double mid=l/2+r/2;
    if(Test(mid)){ans=mid;r=mid;}
    else l=mid;
}
return ans;
}
 
int main(){
freopen("3993.in","r",stdin);
freopen("3993.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%lf",&A[i]);Sum+=A[i];}
for(int i=1;i<=m;i++){scanf("%lf",&B[i]);}
for(int i=1;i<=m;i++){
    for(int j=1;j<=n;j++){
        scanf("%d",&Mt[i][j]);
    }
}
printf("%lf\n",Div());
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
11
2016
0

AHOI2016 Bless all

还有几天就AHOI了呢。。

虽然进队希望=0，但是还是停课准备了。。

cyd和dhp没有停课，理由是今年进不了队，停课影响文化课，但我其实是不太资瓷这么做的，毕竟省选一年只有一次，高中也只有2次，你不认真对待省选，那么省选也不会认真对待你

不说了。。天天零爆爆底垫垫，今年省选估计要爆0。。

还是不要立flag为好

总之，Bless All!我不会虚度这4天的停课的光阴的！

Category: 随笔 | Tags: 随笔 弱
4
11
2016
0

[BZOJ4407] 于神之怒加强版

一道反演的好题

首先我们需要推一下式子（写在纸上发现不太好写在电脑上）

拍照太烦了……其实就是Claris博客上的公式

然后倒数第二行那个式子的前缀和我不太会。。本来想问Claris的后来自己推了一下就会了

网上题解都好玄学啊

首先对于这么一个式子(用画图画的请见谅……我不会LateX)

我们把这个式子的值用一个函数F(D)表示

然后我们可以发现:对于D为质数，那么d只有两个值：一个是1，一个是D

那么我们可以暴力快速幂乘起来就可以了

如果D不是质数，为了简化我们假设这个D可以由两个质数相乘

那么d的取值可以是:1,第一个质数，第二个质数，两个质数之积

那么我们设f[i]=i是质数则为ik,否则为0

g[i]=这个和数会由哪些质数组成

我们就可得到F[i*pri[j]]=F[pri[j]]*F[i],因为这个F[i*pri[j]]会由F[i]和F[i*pri[j]]组成,那么两个sigma相乘自然就是这个值了

对于两个质数以上的乘积我觉得和上面一样的。。主要分g[i]是否等于i(i是质数)和g[i]不等于i两种情况考虑，就可以了

?
bzoj 4407
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
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=5000000,Mod=1000000007;
 
int T,n,m,k,pri[N/5+1],mu[N+5],tab[N+5],g[N+5],sum[N+5],F[N+5],f[N+5],cnt;
 
int Pow(int x,int y){
int base=x,ans=1;
while(y){
    if(y&1)ans=1ll*ans*base%Mod;
    base=1ll*base*base%Mod;
    y>>=1;
}
return ans;
}
 
void Prepare(){
mu[1]=1;
F[1]=1;
for(int i=2;i<=N;i++){
    if(!tab[i]){pri[++cnt]=i;mu[i]=-1;f[i]=Pow(i,k);F[i]=f[i]-1;g[i]=i;}
    for(int j=1;j<=cnt && i*pri[j]<=N;j++){
        tab[pri[j]*i]=1;
        if(i%pri[j]){
            mu[i*pri[j]]=-mu[i];
            g[i*pri[j]]=pri[j];
            F[i*pri[j]]=1ll*F[pri[j]]*F[i]%Mod;
        }
        else{
            mu[i*pri[j]]=0;
            g[i*pri[j]]=g[i]*pri[j];
            F[i*pri[j]]=g[i]!=i?1ll*F[i/g[i]]*F[g[i]*pri[j]]%Mod:1ll*F[i]*f[pri[j]]%Mod;
            break;
        }
    }
}
for(int i=2;i<=N;i++)F[i]=(F[i-1]+F[i])%Mod;
}
 
int Solve(){
int ans=0,j;
for(int i=1;i<=n && i<=m;i=j+1){
    j=min(n/(n/i),m/(m/i));
    ans=(ans+1ll*(F[j]-F[i-1]+Mod)*(n/i)%Mod*(m/i)%Mod)%Mod;
}
return ans;
}
 
int main(){
freopen("4407.in","r",stdin);
freopen("4407.out","w",stdout);
scanf("%d %d",&T,&k);
Prepare();
while(T--){
    scanf("%d %d",&n,&m);
    printf("%d\n",Solve());
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2809] [Apio2012]dispatching

首先我们确定了领导者和派遣出去的忍着数目就确定了答案

那么我们枚举领导者，每次一定派遣薪水最少的忍者们

然后先DFS，然后每次超过m我们就在可并堆中pop掉薪水最多的忍着

因为薪水是正数，所以这样做是对的

?
bzoj 2809
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,h[100005],en,siz[100005],root[100005],cnt;
long long m,ans,sum[100005];
 
struct Ninja{
int b;
long long c,l;
}ninja[100005];
 
struct Edge{
int b,next;
}e[1000005];
 
struct Heap{
int l,r,dis;
long long v;
}heap[100005];
 
void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=h[sa];
h[sa]=en;
}
 
int Newheap(long long x){
heap[++cnt].v=x;
heap[cnt].l=heap[cnt].r=heap[cnt].dis=0;
return cnt;
}
 
int Merge(int A,int B){
if(!A)return B;
if(!B)return A;
if(heap[A].v<heap[B].v)swap(A,B);
heap[A].r=Merge(heap[A].r,B);
if(heap[heap[A].l].dis<heap[heap[A].r].dis)swap(heap[A].l,heap[A].r);
heap[A].dis=heap[heap[A].r].dis+1;
return A;
}
 
long long Top(int x){return heap[x].v;}
void Pop(int &x){x=Merge(heap[x].l,heap[x].r);}
 
void dfs(int u){
root[u]=Newheap(ninja[u].c);
siz[u]=1;
sum[u]=ninja[u].c;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    dfs(v);
    sum[u]+=sum[v];
    siz[u]+=siz[v];
    root[u]=Merge(root[u],root[v]);
}
while(sum[u]>m){
    sum[u]-=Top(root[u]);
    Pop(root[u]);
    siz[u]--;
}
ans=max(ans,siz[u]*ninja[u].l);
}
 
int main(){
freopen("2809.in","r",stdin);
freopen("2809.out","w",stdout);
scanf("%d %lld",&n,&m);
heap[0].dis=-1;
for(int i=1;i<=n;i++){
    scanf("%d %lld %lld",&ninja[i].b,&ninja[i].c,&ninja[i].l);
    AddEdge(ninja[i].b,i);
}
dfs(1);
printf("%lld\n",ans);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ2733] [HNOI2012]永无乡

首先连通块我们用并查集维护，而查询k大我们用权值线段树维护

建边就是合并两个线段树

查询直接在权值线段树查询就好了

?
bzoj 2733
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
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n,m,q,a[100005],f[100005],v[100005],root[100005],cnt;
 
struct SegTree{
int nl,nr,sum;
}tree[2000005];
 
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
 
void Insert(int &rt,int l,int r,int pos){
if(!rt)rt=++cnt;
if(l==r){tree[rt].sum=1;return;}
int mid=l+r>>1;
if(pos<=mid)Insert(tree[rt].nl,l,mid,pos);
else Insert(tree[rt].nr,mid+1,r,pos);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}
 
int Query(int rt,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(tree[tree[rt].nl].sum>=k)return Query(tree[rt].nl,l,mid,k);
return Query(tree[rt].nr,mid+1,r,k-tree[tree[rt].nl].sum);
}
 
int Merge(int l,int r){
if(!l)return r;
if(!r)return l;
tree[l].nl=Merge(tree[l].nl,tree[r].nl);
tree[l].nr=Merge(tree[l].nr,tree[r].nr);
tree[l].sum=tree[tree[l].nl].sum+tree[tree[l].nr].sum;
return l;
}
 
int main(){
freopen("2733.in","r",stdin);
freopen("2733.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=i;}
for(int i=1;i<=m;i++){
    int tp,tq;
    scanf("%d %d",&tp,&tq);
    tp=Find(tp);tq=Find(tq);f[tp]=tq;
}
for(int i=1;i<=n;i++){Insert(root[Find(i)],1,n,a[i]);v[a[i]]=i;}
scanf("%d",&q);
while(q--){
    char s[5];
    int x,y;
    scanf("%s %d %d",s,&x,&y);
    if(s[0]=='B'){x=Find(x);y=Find(y);if(x!=y){f[x]=y;root[y]=Merge(root[x],root[y]);}}
    if(s[0]=='Q'){x=Find(x);if(tree[root[x]].sum>=y)printf("%d\n",v[Query(root[x],1,n,y)]);else puts("-1");}
}
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
10
2016
0

[BZOJ4444] [Scoi2015]国旗计划

树上倍增

首先剖环成2倍长的链

对于每一个士兵求他的下一个士兵应该选哪一个，记录进Next数组

注意此时Next数组形成了一棵树，然后树上倍增就可以了

?
bzoj 4444
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
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
  
int n,m,Next[400005],cnt,ans[200005],fa[400005][20];
  
struct Soldier{
long long l,r;
int id;
friend bool operator<(Soldier A,Soldier B){return A.l<B.l;}
}sol[400005];
  
int main(){
freopen("4444.in","r",stdin);
freopen("4444.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    int xl,xr;
    scanf("%d %d",&xl,&xr);
    if(xl<xr){
        sol[++cnt].l=xl;sol[cnt].r=xr;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m;
    }
    else {
        sol[++cnt].l=xl;sol[cnt].r=xr+m;
        sol[cnt].id=i;
        sol[++cnt].l=xl+m;sol[cnt].r=xr+m+m;
    }
}
sol[0].r=21000000000000000ll;
sort(sol+1,sol+cnt+1);
int j=0;
for(int i=1;i<=cnt;i++){
    while(j<=cnt && sol[j].l<=sol[i].r)j++;
    Next[i]=j-1;
}
for(int i=cnt-1;i>=1;i--){
    fa[i][0]=Next[i];
    for(j=1;j<=19;j++)fa[i][j]=fa[fa[i][j-1]][j-1];
    if(sol[i].id){
        int tp=i;
        for(j=19;j>=0;j--){if(sol[fa[tp][j]].r-sol[i].l<m){ans[sol[i].id]+=1<<j;tp=fa[tp][j];}}
        ans[sol[i].id]+=2;
    }
}
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
return 0;
}
Category: BZOJ | Tags: OI bzoj
4
6
2016
0

[UOJ164] 【清华集训2015】V

最近集训出了很多SGTB(SeGmentTree Beats!)的题目,所以被迫来学习这个冬令营上的黑科技。。

这题照着其他人写的程序理解了几个小时，然后自己写了一发居然是最快的。。。

记录一下自己对于这题的理解吧

输入的操作分别对应:

1.区间加

2.区间max(0,v)

3.区间赋值

4.询问单点值

5.询问单点历史最值

然后我一开始试图维护十来个标记然后暴力搞。。然后就不会了

然后膜了一下其他人的程序和lzz的冬令营课件，总算有了一点理解了

这题关键在于单点询问，所以我们仅仅把区间当成一整个标记，每次下传后就清零

然后问题在于两个操作：询问历史最值和区间max

我们先不管询问历史最值

其实我们进行一番转化后可以发现,其实123操作都可以对应到一个(x,y)（加上x对y取max）上（这是对于一个区间的标记）

1:区间加v -> (v,INF)

2:区间max(0,v) -> (v,0)

3.区间赋值为v -> (-INF,v);

这很显然吧。。

然后我们考虑两个标记的合并，这里我还是想了一下的

设旧标记为A,新标记为B

那么我们进行合并就变成了(A.x+B.x,max(A.y+B.x,B.y))

为什么是这样呢？

首先我们考虑如果A.x+B.x,那么就直接相当于普通线段树的Add操作，明显可行

而max(A.y+B.x,B.y)则表示如果旧标记产生的最大值为A.y,那么我们最终要取的值要么就是旧标记的A.y加上新标记要加上的值(因为旧标记可能取A.y)，要么就是新标记要取的B.y（感觉我这句话比较意识流啊），当然是在这两个数里面选一个最大值了

于是我们就处理完了没有历史最值询问的操作

但是这题是有历史最值询问的。。好坑啊

那么我们考虑再加上两个标记mx,addmx表示当前区间的历史最值和要加上去的值的历史最值

那么我们继续考虑合并标记

同样，我们设(X,Y)表示mx和addmx两个值（偷懒），那么我们继续设以前的旧标记为A，用来更新旧标记的新标记为B

那么历史最值可以怎么构成？可以由旧标记的历史最值、新标记的历史最值，或者是旧标记的当前值加上新标记的的历史最大加值。

前两个很好理解，但是最后一个是什么意思呢？

首先，新标记的历史最大加值可以用这样一段话来叙述：“这一段区间曾经加过这么大的值”

那么我们每次拿旧标记当前的值加上新标记的历史最大加值，就意味着这个合并后的标记曾经在某个时刻达到了这个可能的最大值

因为每次更新标记时都是自顶向下，那么没有被更新的旧标记的值一定是当前值，如果被更改了那么之前一定在这里下传过标记，所以这样是对的

而我们再考虑addmx可以怎么构成

显然这个值可能的取值为：旧标记的addmx,新标记的addmx加上旧标记的add

为什么又是这么取值呢？

第一种情况显然。第二种情况因为新标记的历史最大加值此时没有经过任何更新，也就是和旧标记一点关联也没有

而因为add的定义和题目的描述(就是上面的小写标记)，add标记一定不会小于0

那么我们当然需要加上这个add值（新标记此前不可能加过add标记），这样能让解更优

那么你可能会问:为什么不能让旧标记的历史最值加上新标记的add呢？

因为新标记是用来更新旧标记的，所以这样可能重复的加所以不行

这仅仅是个人的理解，我觉得真是漏洞百出，具体的证明lzz冬令营课件里面有，反正我没有看太懂。。。

我真是太弱了

这真是一篇意识流的题解

?
uoj 164
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
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
 
int n,m;
long long a[500005];
const long long INF=1000000000000000ll;
 
template<typename T>void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
 
struct SegTree{
int l,r;
long long v,mx,add,addmx;
SegTree(){}
SegTree(long long V,long long MX,long long ADD,long long ADDMX){v=V;mx=MX;add=ADD;addmx=ADDMX;}
SegTree(int L,int R,long long V,long long MX,long long ADD,long long ADDMX){l=L;r=R;v=V;mx=MX;add=ADD;addmx=ADDMX;}
}tree[2000005],tmp;
 
SegTree Update(SegTree A,SegTree B){
return SegTree(A.l,A.r,max(A.v+B.add,B.v),max(max(A.mx,B.mx),A.v+B.addmx),max(A.add+B.add,-INF),max(A.addmx,A.add+B.addmx));
}
 
void Pushdown(int rt){
tree[rt*2]=Update(tree[rt*2],tree[rt]);
tree[rt*2+1]=Update(tree[rt*2+1],tree[rt]);
tree[rt]=SegTree(tree[rt].l,tree[rt].r,0,0,0,0);
}
 
void Build(int rt,int l,int r){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
    tree[rt].addmx=tree[rt].add=tree[rt].v=tree[rt].mx=a[l];
    return;
}
int mid=l+r>>1;
Build(rt*2,l,mid);
Build(rt*2+1,mid+1,r);
}
 
void Change(int rt,int l,int r){
if(l<=tree[rt].l && tree[rt].r<=r){tree[rt]=Update(tree[rt],tmp);return;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(l<=mid)Change(rt*2,l,r);
if(r>mid)Change(rt*2+1,l,r);
}
 
long long Query(int rt,int pos,int id){
if(tree[rt].l==tree[rt].r){return id?tree[rt].mx:tree[rt].v;}
Pushdown(rt);
int mid=tree[rt].l+tree[rt].r>>1;
if(pos<=mid)return Query(rt*2,pos,id);
if(pos>mid)return Query(rt*2+1,pos,id);
}
 
int main(){
freopen("164.in","r",stdin);
freopen("164.out","w",stdout);
Read(n);Read(m);
for(int i=1;i<=n;i++)Read(a[i]);
Build(1,1,n);
for(int i=1;i<=m;i++){
    int opt,l,r,v;
    Read(opt);
    if(opt==1){Read(l);Read(r);Read(v);tmp=SegTree(0,0,v,v);Change(1,l,r);}
    if(opt==2){Read(l);Read(r);Read(v);tmp=SegTree(0,0,-v,-v);Change(1,l,r);}
    if(opt==3){Read(l);Read(r);Read(v);tmp=SegTree(v,v,-INF,-INF);Change(1,l,r);}
    if(opt==4){Read(v);printf("%lld\n",Query(1,v,0));}
    if(opt==5){Read(v);printf("%lld\n",Query(1,v,1));}
}
return 0;
}
Category: 其他OJ | Tags: OI uoj
4
3
2016
0

[BZOJ2179] FFT快速傅立叶

FFT模版题

话说网上对FFT讲的神乎其神，以后我来搞一份小学生都能看懂的FFT入门吧

最好没有公式和严谨的证明，搞一些非常通俗的就比较好

因为我自己也只会模版。。。

?
bzoj 2179
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
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
 
const int SIZE=300005;
const double Pi=acos(-1);
 
int An,Bn,Cn,n,Step,Rev[SIZE],Ans[SIZE];
char s[SIZE];
 
struct Complex{
double a,b;
Complex(double sa=0.0,double sb=0.0){a=sa;b=sb;}
friend Complex operator+(Complex a,Complex b){return Complex(a.a+b.a,a.b+b.b);}
friend Complex operator-(Complex a,Complex b){return Complex(a.a-b.a,a.b-b.b);}
friend Complex operator*(Complex a,Complex b){return Complex(a.a*b.a-a.b*b.b,b.a*a.b+a.a*b.b);}
}A[SIZE],B[SIZE],C[SIZE];
 
void FFT(Complex *x,int flag){
for(int i=0;i<n;i++)if(i<Rev[i])swap(x[i],x[Rev[i]]);
for(int k=1;k<n;k<<=1){
    Complex wk=Complex(cos(Pi/k),flag*sin(Pi/k));
    for(int i=0;i<n;i+=k<<1){
        Complex wkj=Complex(1.0,0.0);
        for(int j=0;j<k;j++){
            Complex a=x[i+j],b=x[i+j+k]*wkj;
            x[i+j]=a+b;
            x[i+j+k]=a-b;
            wkj=wkj*wk;
        }
    }
}
if(flag==-1)for(int i=0;i<n;i++)x[i].a/=n;
}
 
void Init_Solve_Out(){
scanf("%d",&An);
Bn=An;Cn=An+Bn-1;
scanf("%s",s);
for(int i=0;i<An;i++)A[i]=Complex(s[i]-'0');
scanf("%s",s);
for(int i=0;i<Bn;i++)B[i]=Complex(s[i]-'0');
for(n=1,Step=0;n<Cn;n<<=1,Step++);
for(int i=0;i<n;i++)Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(Step-1));
FFT(A,1);FFT(B,1);
for(int i=0;i<n;i++)C[i]=A[i]*B[i];
FFT(C,-1);
for(int i=0;i<Cn;i++)Ans[Cn-i]=(int)(C[i].a+0.5);
for(int i=1;i<=Cn;i++)Ans[i+1]+=Ans[i]/10,Ans[i]%=10;
if(Ans[Cn+1])Cn++;
for(int i=Cn;i>=1;i--)printf("%d",Ans[i]);
}
 
int main(){
freopen("2179.in","r",stdin);
freopen("2179.out","w",stdout);
Init_Solve_Out();
return 0;
}
Category: BZOJ | Tags: OI bzoj

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com