ZJT's Blog

大変に気分がいい~

多项式欢乐测速

2017-9-20 23:392017-9-24 1:27
FFT生成函数卡常待填坑

欢乐测速时间!

时间单位为跑一次次数为$2*10^5$的FFT所需时间。

以下时间都是大概的值,跑得时候可能出现玄学情况。

以及我的常数跟屎一样。。。各位dalao写的话可能会快不少。

  • 多项式乘法:6.3 (关于为啥不是3左右,因为我的乘法和FFT传进的多项式次数都是n,所以乘法需要扩2倍)
  • 多项式求逆:12
  • 多项式求ln:18.5
  • 多项式求exp:46.5 41(换了写法,具体看下面)

待测:

  • 多项式开根
  • 多项式取模
  • 其他多项式乱搞

有时间就测测吧。

更新:exp的写法改了,把每步乘法的范围缩小了一倍,快了一点。代码已经更新了。

测试用代码:

const LL P=998244353;
LL inv_v[MAXN],w_v[MAXN];

LL getPow(LL x,LL y){
    LL res=1;
    while(y){
        if(y&1) res=res*x%P;
        x=x*x%P;
        y>>=1;
    }
    return res;
}

void FFT(LL *a,int len,int flag){
    static int rev[MAXN];
    rev[0]=0;
    for(int i=1;i<len;i++)
        rev[i]=rev[i>>1]>>1|((i&1)?(len>>1):0);
    for(int i=0;i<len;i++)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int l=2;l<=len;l<<=1){
        LL wn=w_v[l];
        int l2=l>>1;
        for(int i=0;i<len;i+=l){
            LL temp=1;
            for(int j=0;j<l2;j++){
                LL t1=a[i+j],t2=a[i+j+l2]*temp%P;
                a[i+j]=(t1+t2)%P;
                a[i+j+l2]=(t1-t2)%P;
                temp=temp*wn%P;
            }
        }
    }
    if(flag==-1){
        LL invn=getPow(len,P-2);
        for(int i=0;i<len;i++) a[i]=a[i]*invn%P;
        for(int i=1;i<len;i++)
            if(i<len-i) swap(a[i],a[len-i]);
    }
}

void mul(LL *a,LL *b,LL *c,int len){
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++){
        t1[i]=a[i]; t2[i]=b[i];
        t1[i+len]=t2[i+len]=0;
    }
    FFT(t1,len<<1,1);
    FFT(t2,len<<1,1);
    for(int i=0;i<(len<<1);i++) t1[i]=t1[i]*t2[i]%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<(len<<1);i++) c[i]=t1[i];
}

void getInv(LL *a,LL *b,int len){
    if(len==1){
        b[0]=getPow(a[0],P-2);
        return;
    }
    getInv(a,b,len>>1);
    for(int i=(len>>1);i<len;i++) b[i]=0;
    static LL t1[MAXN],t2[MAXN];
    for(int i=0;i<len;i++){
        t1[i]=a[i]; t2[i]=b[i];
        t1[i+len]=t2[i+len]=0;
    }
    FFT(t1,len<<1,1); FFT(t2,len<<1,1);
    for(int i=0;i<(len<<1);i++)
        t1[i]=(2*t2[i]-t1[i]*t2[i]%P*t2[i])%P;
    FFT(t1,len<<1,-1);
    for(int i=0;i<len;i++) b[i]=t1[i];
}

void getln(LL *a,LL *b,int len){
    assert(a[0]==1);
    static LL t1[MAXN],t2[MAXN];
    for(int i=1;i<len;i++) t1[i-1]=a[i]*i%P;
    t1[len-1]=0;
    getInv(a,t2,len);
    mul(t1,t2,t1,len);
    for(int i=1;i<len;i++) b[i]=t1[i-1]*inv_v[i];
    b[0]=0;
}

void getExp(LL *a,LL *b,int len){
    if(len==1){
        assert(a[0]==0);
        b[0]=1;
        return;
    }
    static LL t1[MAXN],t2[MAXN],t3[MAXN],t4[MAXN];
    getExp(a,t1,len>>1);
    for(int i=0;i<(len>>1);i++) t4[i]=t1[i];
    getln(t1,t2,len);
    for(int i=0;i<(len>>1);i++)
        t3[i]=(t2[i+(len>>1)]-a[i+(len>>1)])%P;
    FFT(t1,len,1); FFT(t3,len,1);
    for(int i=0;i<len;i++) t3[i]=t1[i]*t3[i]%P;
    FFT(t3,len,-1);
    for(int i=0;i<(len>>1);i++){
        b[i]=t4[i];
        b[i+(len>>1)]=-t3[i];
    }
}

int n,sizew;

void init(){
    scanf("%d",&n);
    for(sizew=1;sizew<n;sizew<<=1);
    inv_v[1]=1;
    for(int i=2;i<=sizew*2;i++)
        inv_v[i]=-(P/i)*inv_v[P%i]%P;
    for(int l=1;l<MAXN;l<<=1)
        w_v[l]=getPow(3,(P-1)/l);
}

各位dalao发现我写得挫了或者有什么可以优化的地方,欢迎评论指出。

查看详细内容

清华集训2016 Day4

2017-9-19 16:302017-9-21 16:38
清华集训智力康复待填坑

因为以前做过Day3,所以先跳过了,先来做一做没看过的Day4。


T1

传送门

好像是思博题?直接套一个lucas定理变成了数位dp,然后乱做即可。

不知道为什么清华集训会有这种题。

代码:

#include <cstdio>
#include <cstring>
#define MAXN 110
#define LL long long

int n,k;
const LL P=1000000007;
int a[MAXN],b[MAXN];
LL f[MAXN][8],g[MAXN][8];

void init(){
    memset(a,0,sizeof a);
    memset(b,0,sizeof b);
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    LL _n,_m;
    scanf("%lld%lld",&_n,&_m);
    n=1;
    while(_n || _m){
        a[n]=_n%k;
        b[n]=_m%k;
        _n/=k; _m/=k;
        n++;
    }
}

void dp(){
    for(int j=0;j<8;j++) g[0][j]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<8;j++){
            int s1=j&1,s2=j&2,s3=j&4;
            int limi=s1?k-1:a[i],limj=s2?k-1:b[i];
            for(int vi=0;vi<=limi;vi++)
                for(int vj=0;vj<=limj;vj++){
                    if(!s3 && vi<vj) break;
                    int t1=(s1||vi<limi)?1:0;
                    int t2=(s2||vj<limj)?2:0;
                    int t3=(s3||vi>vj)?4:0;
                    int t4=t1|t2|t3;
                    if(vi<vj) f[i][j]=(f[i][j]+g[i-1][t4])%P;
                    else f[i][j]=(f[i][j]+f[i-1][t4])%P;
                    g[i][j]=(g[i][j]+g[i-1][t4])%P;
                }
        }
    }
    printf("%lld\n",f[n][0]);
}

void solve(){
    init();
    dp();
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
    int T;
    scanf("%d%d",&T,&k);
    while(T--) solve();
    return 0;
}

无压力1A。


T2

传送门

我们把所有边权都减$k$,然后就便乘了找一条链使得平均值的绝对值最小。看起来一脸分数规划,然后就想到二分答案。

我们考虑二分的过程中,需要判断答案是否小于$c$。大概就是要找一条链,使得$$-c<\frac{\sum_{i\in S}w_i}{|S|}<c$$

我们变一下形,就变成了$$\sum_{i\in S}w_i-c<0,\sum_{i\in S}w_i+c>0$$

然后点分一下,把第一个不等式作为约束条件,用一个数据结构维护第二个东西的max,然后就能做啦!

不过似乎有什么不对。。。这个做法复杂度好像是3个log??

然后yww就告诉我这题正解就是3个log。。。然后就不虚了,大力写了一个3个log的乱搞。为了优化常数,把点分的时候要搞的动态开点线段树改成了每次离散化之后用二分+树状数组来搞。

为了锻炼1A能力(雾),所以过了大样例就直接交了!(好吧其实是懒得对拍)结果45分WA了。。。感觉任何稍微有点难度的题都无法1A啊??药丸啊?

看了看发现四个dfs中的第四个里面调用的是第三个dfs的函数。。。原因竟是写dfs4的时候直接复制的dfs3,然后忘记改了。。我去这也能有45分,这都啥数据啊。。。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

const LL INF=1LL<<62;

struct edge{
    int to,next;
    LL w;
    edge(int _to=0,int _next=0,LL _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,numb;
int g[MAXN],nume=0;
int size[MAXN],maxs[MAXN],root,sums;
int visit[MAXN],numvisit,pt[MAXN];
int rk[MAXN];
LL lim,s1[MAXN],s2[MAXN];
pair<LL,int> b[MAXN];

namespace Fenwick{
    LL c[MAXN];

    void init(){ for(int i=0;i<MAXN;i++) c[i]=-INF; }

    void insert(int x,LL y){
        while(x<=numb){
            if(y>c[x]) c[x]=y;
            x+=x&(-x);
        }
    }

    LL max(int x){
        LL res=-INF;
        while(x){
            if(c[x]>res) res=c[x];
            x-=x&(-x);
        }
        return res;
    }

    void undo(int x){
        while(x<=numb){
            c[x]=-INF;
            x+=x&(-x);
        }
    }
}

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void findRoot(int x,int p){
    size[x]=1; maxs[x]=0;
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && !visit[e[i].to]){
            findRoot(e[i].to,x);
            size[x]+=size[e[i].to];
            if(size[e[i].to]>maxs[x]) maxs[x]=size[e[i].to];
        }
    if(sums-size[x]>maxs[x]) maxs[x]=sums-size[x];
    if(maxs[x]<maxs[root]) root=x;
}

void build(int x){
    pt[visit[x]=++numvisit]=x;
    findRoot(x,0);
    for(int i=g[x];~i;i=e[i].next)
        if(!visit[e[i].to]){
            sums=size[e[i].to];
            root=0;
            findRoot(e[i].to,0);
            build(root);
        }
}

void dfs1(int x,int p,int limw){
    b[++numb]=make_pair(s1[x],x);
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=limw && e[i].to!=p){
            s1[e[i].to]=s1[x]+e[i].w-lim;
            s2[e[i].to]=s2[x]+e[i].w+lim;
            dfs1(e[i].to,x,limw);
        }
}

bool dfs2(int x,int p,int limw){
    if(b[1].first+s1[x]<0){
        int l=1,r=numb;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(b[mid].first+s1[x]<0) l=mid;
            else r=mid-1;
        }
        if(s2[x]+Fenwick::max(l)>0) return 1;
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            if(dfs2(e[i].to,x,limw)) return 1;
    return 0;
}

void dfs3(int x,int p,int limw){
    Fenwick::insert(rk[x],s2[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            dfs3(e[i].to,x,limw);
}

void dfs4(int x,int p,int limw){
    Fenwick::undo(rk[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to!=p && visit[e[i].to]>=limw)
            dfs4(e[i].to,x,limw);
}

bool gao(int x){
    s1[x]=s2[x]=0;
    numb=0;
    dfs1(x,0,visit[x]);
    sort(b+1,b+numb+1);
    for(int i=1;i<=numb;i++) rk[b[i].second]=i;
    Fenwick::insert(rk[x],0);
    bool flag=0;
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=visit[x]){
            if(dfs2(e[i].to,x,visit[x])){
                Fenwick::undo(rk[x]);
                for(int j=g[x];(~j) && (i^j);j=e[j].next)
                    if(visit[e[j].to]>=visit[x])
                        dfs4(e[j].to,x,visit[x]);
                return 1;
            }
            dfs3(e[i].to,x,visit[x]);
        }
    Fenwick::undo(rk[x]);
    for(int i=g[x];~i;i=e[i].next)
        if(visit[e[i].to]>=visit[x])
            dfs4(e[i].to,x,visit[x]);
    return 0;
}

bool gao_tot(LL _lim){
    lim=_lim;
    for(int i=1;i<=n;i++) if(gao(pt[i])) return 1;
    return 0;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("B.in","r",stdin);
#endif
    Fenwick::init();
    memset(g,-1,sizeof g);
    LL avg;
    scanf("%d%lld",&n,&avg);
    LL maxans=0;
    for(int i=1;i<n;i++){
        int u,v;
        LL w;
        scanf("%d%d%lld",&u,&v,&w);
        addEdge(u,v,w-avg);
        addEdge(v,u,w-avg);
        if(abs(w-avg)>maxans) maxans=abs(w-avg);
    }
    maxs[0]=0x7FFFFFFF;
    root=0; sums=n;
    findRoot(1,0);
    build(root);
    LL l=0,r=maxans+1;
    while(l<r){
        LL mid=(l+r)>>1;
        if(gao_tot(mid)) r=mid;
        else l=mid+1;
    }
    printf("%lld\n",l-1);
    return 0;
}

然后就悲剧地没有成功1A。。。感觉自己不仅实力弱,而且做题的时候还经常池沼。。。这样下去真的要完啊。


T3

(待续。。。)

查看详细内容

清华集训2016 Day3

2017-9-19 16:292017-9-24 1:9
清华集训智力康复待填坑

占坑。。。

因为以前做过这套题,所以就先跳过了,最后再来再过一遍。

ps.因为集训队作业来了,所以可能会无限期延迟。。。

查看详细内容