Codeforces Round #563 (Div. 2) 划水记

网太卡只好做划水选手，只做EF。

E

很容易发现第一个数是2或者是3*2，因为消去因子次数要尽可能多，然后可以直接dp一发转移还剩几个2/3即可，写起来有些麻烦

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+,mod=1e9+;

int n,k,ans,a[][],f[N][][];

int count(int x)

{

    int ret=;

    while(x%==)ret++,x/=;

    return ret;

}

int main()

{

    scanf("%d",&n);

    if(n<=){puts("");return ;}

    for(int i=;i;i--)if((<<i)<=n){k=i;break;}

    for(int i=;i<=n;i++)a[count(i)][]++;

    for(int i=k-;~i;i--)a[i][]+=a[i+][];

    f[][k][]=;

    for(int i=;i<=n;i++)

    for(int j=;j<=k;j++)

    {

        f[i][j][]=(f[i][j][]+1ll*f[i-][j+][]*(a[j][]-a[j+][]))%mod;

        f[i][j][]=(f[i][j][]+1ll*f[i-][j][]*(a[j][]-i+))%mod;

    }

    ans=f[n][][];

    if((<<k-)*<=n)

    {

        memset(f,,sizeof f);

        memset(a,,sizeof a);

        for(int i=;i<=n;i++)a[count(i)][i%==]++;

        for(int i=k-;~i;i--)a[i][]+=a[i+][],a[i][]+=a[i+][];

        f[][k-][]=;

        for(int i=;i<=n;i++)

        for(int j=;j<k;j++)

        {

            f[i][j][]=(f[i][j][]+1ll*f[i-][j+][]*(a[j][]-a[j+][]))%mod;

            f[i][j][]=(f[i][j][]+1ll*f[i-][j][]*(a[j][]-i+))%mod;

            f[i][j][]=(f[i][j][]+1ll*f[i-][j+][]*(a[j][]+a[j][]-a[j+][]-a[j+][]))%mod;

            f[i][j][]=(f[i][j][]+1ll*f[i-][j][]*(a[j][]+a[j][]-i+))%mod;

            f[i][j][]=(f[i][j][]+1ll*f[i-][j][]*a[j][])%mod;

        }

        ans=(ans+f[n][][])%mod;

    }

    printf("%d",ans);

}

F

可以考虑树剖，然后询问时，若询问的lca不在重儿子上，则大小/2，反之下logn次即可，容易证明这个询问次数是log级别的

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

int n,dis,dep[N],sz[N],son[N],ed[N];

vector<int>G[N];

void dfs(int u,int fa)

{

    sz[u]=;

    for(int i=;i<G[u].size();i++)

    if(G[u][i]!=fa)

    {

        dep[G[u][i]]=dep[u]+,dfs(G[u][i],u),sz[u]+=sz[G[u][i]];

        if(sz[G[u][i]]>sz[son[u]])son[u]=G[u][i];

    }

    ed[u]=son[u]?ed[son[u]]:u;

}

int askd(int x)

{

    printf("d %d\n",x),fflush(stdout);

    scanf("%d",&x);

    return x;

}

int asks(int x)

{

    printf("s %d\n",x),fflush(stdout);

    scanf("%d",&x);

    return x;

}

int solve(int u)

{

    if(dep[u]==dis)return u;

    if(dis-dep[u]==)return asks(u);

    int lca=dep[ed[u]]+dis-askd(ed[u])>>;

    if(dep[u]==lca)return solve(asks(u));

    while(dep[u]!=lca&&dep[u]!=dis)u=son[u];

    return solve(u);

}

int main()

{

    scanf("%d",&n);

    for(int i=,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x);

    dfs(,),dis=askd();

    printf("! %d",solve());

}