camp训练day3

F dp

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int mod=1e9+7;
const int maxn=1e4+10;
LL f[105][maxn];
//LL  quickMod(LL a, LL p, LL mod)
//{
//    a%=mod;
//    LL base=1;
//    while(p)
//    {
//        if(p&1) base=base*a%mod;
//        a=a*a%mod;
//        p>>=1;
//    }
//    return base;
//}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
//    if(m*k<=n)
//    {
//        int ans=quickMod(k+1,m,mod);
//        printf("ans=%d
",ans);
//        ans-=(k+1);
//        printf("%d
",(ans+mod)%mod);
//    }
//    else
//    {
    for(int i=0; i<=k; i++)
    {
        if((n-i)<0) continue;
        f[1][n-i]=1;
    }
    for(int i=2; i<=m; i++)
        for(int j=0; j<=k; j++)
            for(int l=0; l<=n; l++)
            {
                if((l-j)<0) continue;
                f[i][l-j]=(f[i][l-j]+f[i-1][l])%mod;
//                printf("%d
",f[i][l]);
            }
    LL ans=0;
    for(int i=0; i<=n; i++)
        ans=(ans+f[m][i])%mod;
//    printf("%lld??
",ans);
    if(m*k<=n)
        ans=ans-k-1;
    else
        ans=ans-(n/m)-1;
    printf("%lld",(ans+mod)%mod);


//    }

}

View Code

I lca

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
int f[maxn][20],d[maxn],dist[maxn];
int head[maxn],ver[2*maxn],nxt[2*maxn],edge[2*maxn];
int tot,t;
int n;
queue<int> q;
void add(int u,int v,int w)
{
    ver[++tot]=v;
    edge[tot]=w;
    nxt[tot]=head[u];
    head[u]=tot;
}
void bfs()
{
    q.push(1);
    d[1]=1;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x]; i; i=nxt[i])
        {
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            dist[y]=dist[x]+edge[i];
            f[y][0]=x;
            for(int j=1; j<=t; j++)
                f[y][j]=f[f[y][j-1]][j-1];
            q.push(y);
        }
    }
}
int lca(int x,int y)
{
    if(d[x]>d[y]) swap(x,y);
    for(int i=t; i>=0; i--)
        if(d[f[y][i]]>=d[x]) y=f[y][i];
    if(x==y) return x;
    for(int i=t; i>=0; i--)
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    int n;
    scanf("%d",&n);
    t=(int)(log(n)/log(2))+1;
    for(int i=1; i<=n-1; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v,1);
        add(v,u,1);
    }
    bfs();
    ll ans=0;
    for(int i=1; i<=n; i++)
        for(int j=2; j*i<=n; j++)
        {
            int k=i*j;
            ans+=dist[i]+dist[k]-2*dist[lca(i,k)]+1;
        }
    printf("%lld",ans);
}

View Code