一.题目大意

Snuke王国有$$n$$座城镇，标号为$$1$$到$$n$$，城镇$$1$$为首都。
王国中每一座城镇有一个传送器：一个立即将人传送到另一个地方的设施。城镇$$i$$的传送目的地为$$a_i(1\le a_i \le N)$$，保证一个人可以在任意城镇使用几次传送器到达首都。
国王Snuke喜爱数字$$K$$，这个自私的国王想要修改传送器的目的地使其满足如下条件：
$$\bullet$$ 一个人可以从任意城镇开始经过恰好$$K$$次传送后到达首都。

求要满足条件需要修改目的地的传送器个数的最小值。

$$2\le N\le 10^5$$
$$1\le a_i\le N$$
$$1\le K\le 10^9$$

二.解题报告

将城市看成点，每个城市向该城市的传送目的地连边，初始时由于每个点出度都为$$1$$且都可以到达$$1$$点，因此这个图为一棵基环内向树，且$$1$$点在环上。

修改后的图同样为基环内向树，为了满足从任意城镇经过恰好$$K$$次传送后到达首都，环必须为$$1$$点的自环，且树的深度小于等于$$K+1$$。

首先将$$1$$点的传送目的地改为自身。不考虑这个自环，将图看成一棵以$$1$$点为根的树，现在需要将一些点的父亲修改，使树的深度小于等于$$K+1$$。

显然将父亲修改为其他点不会比修改为$$1$$点更优，因此可以采用如下的贪心策略：从叶节点向上进行树形dp，到一个点时如果该点子树中深度最大的叶子到该点距离为$$K-1$$，那么将该点的父亲修改为$$1$$点。

易证这个贪心策略的正确性，因为修改深度小的点的父亲显然比修改深度大的点的父亲更优。

时间复杂度$$O(n)$$

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,K,ans;
int a[N];
vector<int>vec[N];
int dfs(int x)
{
    int ret=0;
    for(int i=0;i<vec[x].size();i++)
    {
        int t=dfs(vec[x][i]);
        if(t==K)ans++;
        else ret=max(ret,t);
    }
    return ret+1;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i!=1)vec[a[i]].push_back(i);
    }
    ans=(a[1]!=1);
    for(int i=0;i<vec[1].size();i++)
        dfs(vec[1][i]);
    printf("%d\n",ans);
    return 0;
}

题意：一条路上有n个店，有m张票，票i可以在店j获得$$d_{ji}$$的收益，从店i走到店i+1有$$a_i$$的花费。求从任意一个店开始能获得的最大收益。

一定不会走重复的路径
暴力：对于每一张票j，求每一家店的最大值覆盖区间，设店i的区间为[L[i],R[i]]，那么将起点在[L[i],i]终点在[i,R[i]]的路径$$+d_{ij}$$,用二维树状数组维护，小范围暴力

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
const int bnd = 200;
int n,m,top;
int a[N],b[M][N],st[N],L[M][N],R[M][N];
ll sum[N],tr[N][N],ans;
void insert(int x,int y,int v)
{
    for(int i=x;i;i-=i&-i)
        for(int j=y;j;j-=j&-j)
            tr[i][j]+=v;    
}
ll query(int x,int y)
{
    ll ret=0;
    for(int i=x;i<=n;i+=i&-i)
        for(int j=y;j<=n;j+=j&-j)
            ret+=tr[i][j];
    return ret;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    for(int i=1;i<=m;i++)
    {
        top=0;st[top]=0;
        for(int j=1;j<=n;j++)
        {
            while(top&&b[i][j]>b[i][st[top]])top--;
            L[i][j]=st[top]+1;
            st[++top]=j;
        }
        top=0;st[top]=n+1;
        for(int j=n;j>=1;j--)
        {
            while(top&&b[i][j]>=b[i][st[top]])top--;
            R[i][j]=st[top]-1;
            st[++top]=j;
        }
    }
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)>=bnd)
            {
                insert(j,R[i][j],b[i][j]);
                insert(L[i][j]-1,j-1,b[i][j]);
                insert(L[i][j]-1,R[i][j],-b[i][j]);
                insert(j,j-1,-b[i][j]);
            }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            tr[i][j]=query(i,j);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if((j-L[i][j]+1)*(R[i][j]-j+1)<bnd)
            {
                for(int k=L[i][j];k<=j;k++)
                    for(int w=j;w<=R[i][j];w++)
                        tr[k][w]+=b[i][j];
            }
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            ans=max(ans,tr[i][j]-(sum[j-1]-sum[i-1]));
    printf("%lld\n",ans);
    return 0;
}

正解：设以i为起点的最优路径终点为p[i]，那么随着i的递增p[i]单调不减。因此可以rmq预处理，设solve(l1,r1,l2,r2)表示求解起点在[l1,r1]内终点可行区间为[l2,r2]的路径。然后求出l1,r1中点mid的最优路径终点，递归处理。

#include <bits/stdc++.h>
using namespace std;
#define M 210
#define N 5100
#define ll long long
int n,m;
int a[N],b[M][N],mx[M][N][16],bir[N];
ll sum[N],ans;
int query(int x,int l,int r)
{
    int t=bir[r-l+1];
    return max(mx[x][l][t],mx[x][r-(1<<t)+1][t]);
}
void solve(int l1,int r1,int l2,int r2)
{
    if(l1>r1)return;
    int mid=(l1+r1)>>1;
    ll v=0,p=max(l2,mid);
    for(int i=max(l2,mid);i<=r2;i++)
    {
        ll t=0;
        for(int j=1;j<=m;j++)
            t+=query(j,mid,i);
        t-=sum[i-1]-sum[mid-1];
        if(t>v)v=t,p=i;
    }
    ans=max(ans,v);
    solve(l1,mid-1,l2,p);
    solve(mid+1,r1,p,r2);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
        sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&b[j][i]);
    bir[1]=0;
    for(int i=2;i<=n;i++)
        bir[i]=bir[i>>1]+1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)mx[i][j][0]=b[i][j];
        for(int j=1;j<=bir[n];j++)
            for(int k=1;k+(1<<j)-1<=n;k++)
                mx[i][k][j]=max(mx[i][k][j-1],mx[i][k+(1<<j-1)][j-1]);
    }
    solve(1,n,1,n);
    printf("%lld\n",ans);
    return 0;
}

题意：有n个整数，gcd为1，每次可以把一个大于1的数减1，并把所有数除以当前所有数的gcd。两个人轮流操作，无法操作者输，求是否先手必胜。

当n=1时先手必败。
当没有除所有数gcd时，如果有奇数个偶数先手必胜，否则后手必胜。
当有除gcd操作时，定义状态1：有奇数个偶数，至少一个奇数。
状态2：有偶数个偶数，至少2个奇数。状态3：有偶数个偶数，1个奇数。
所有数都为1的状态属于状态2，为先手必败态。
状态1时对一个偶数-1，此时gcd为奇数，因此不改变奇偶性。转移到状态2。状态2时不管如何操作操作后gcd为1，因此只能转移到状态1。所以状态1为先手必胜态，状态2为先手必败态。
状态3如果选一个偶数，会转移到状态2，因此只能选一个奇数。此时gcd至少为2。因此如果初始时为状态3，直接递归。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,num;
int a[N];
int main()
{
    scanf("%d",&n);
    if(n==1)return puts("Second"),0;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    while(1)
    {
        int odd=0,even=0,pos;
        for(int i=1;i<=n;i++)
        {
            if(a[i]&1)odd++,pos=i;
            else even++;
        }
        if(even&1)break;
        if(odd>=2){num++;break;}
        if(a[pos]==1){num++;break;}
        a[pos]--;int t=a[1];
        for(int i=2;i<=n;i++)t=__gcd(t,a[i]);
        for(int i=1;i<=n;i++)a[i]/=t;
        num++;
    }
    puts(num&1 ? "Second" : "First");
    return 0;
}

题意：n只蚂蚁在周长为L的圆上，延顺时针或逆时针以速度1移动，相遇时两只蚂蚁同时调转方向。求T秒后每只蚂蚁的位置。

相遇后调转方向相当于两只蚂蚁不改变方向，只交换编号，因此可以求出最终蚂蚁的位置集合，又由于相对位置不变，因此只需确定一只蚂蚁的位置。考虑第一只蚂蚁相遇次数即为编号改变次数（顺时针+1，逆时针-1）。因此可以确定一只蚂蚁的位置。
注意最终两只蚂蚁位置相同的情况。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
#define ll long long
ll n,L,T;
ll a[N],b[N],p[N<<1],ans[N];
int main()
{
    scanf("%lld%lld%lld",&n,&L,&T);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    for(ll i=1;i<=n;i++)
    {
        if(b[i]==1)p[i]=(a[i]+T)%L;
        else p[i]=((a[i]-T)%L+L)%L;
    }
    ll tp=p[1];
    sort(p+1,p+1+n);
    for(ll i=1;i<=n;i++)p[i+n]=p[i];
    ll sum=0;
    for(ll i=2;i<=n;i++)
        if(b[i]!=b[1])
        {
            ll t;
            if(b[1]==1)t=a[i]-a[1];
            else t=L-(a[i]-a[1]);
            t=T*2-t-1;
            if(t<0)continue;
            sum+=t/L+1;
        }
    ll tar,p1;
    if(b[1]==2)tar=(1-sum%n+n)%n;
    else tar=(1+sum%n)%n;
    if(tar==0)tar=n;
    if(b[1]==1)
        p1=upper_bound(p+1,p+1+n,tp-1)-p;
    else 
        p1=upper_bound(p+1,p+1+n,tp)-p-1;
    for(ll i=1;i<=n;i++)
    {
        ans[tar]=p[p1];
        p1++;tar++;
        if(tar>n)tar=1;
    }
    for(ll i=1;i<=n;i++)
        printf("%lld\n",ans[i]);
    return 0;
}

题意：给出一棵n个点的树和K，从树中选出K个点，设点集为S，设f(S)为将这个点集中的点在树中联通联通块的最小点数。对于1到n的每一个K，求$$C_n^K$$种选法的f(S)之和。

对于每条边计算贡献，设边的一边有ai个点，那么贡献为$$C_n^K-C_{ai}^K-C_{n-ai}^K$$，$$C_n^K$$直接计算，$$C_{n-ai}^K$$与$$C_{ai}^K$$计算同理。
$$C_{ai}^K=\\frac{ai!}{K!(ai-K)!}$$
其中$$\\frac{1}{K!}$$可以最后乘，$$\frac{ai!}{(ai-K)!}$$将分母翻转成为卷积的形式。NTT处理即可

#include <bits/stdc++.h>
using namespace std;
#define N 210000
#define mod 924844033
#define ll long long
#define g 5
int n,tot,len;
int head[N],nex[N<<1],to[N<<1];
int size[N],jc[N],njc[N],ans[N];
int a[N<<2],b[N<<2],c[N<<2];
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=n;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[n]=qpow(jc[n],mod-2);
    for(int i=n-1;i>=1;i--)njc[i]=(ll)njc[i+1]*(i+1)%mod;
    for(len=1;len<(n+1)*2;len<<=1);
}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    size[x]=1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs(to[i],x);
            size[x]+=size[to[i]];
        }
}
int C(int x,int y){return (ll)jc[x]*njc[y]%mod*njc[x-y]%mod;}
void NTT(int *a,int len,int type)
{
    for(int i=0,t=0;i<len;i++)
    {
        if(i<t)swap(a[i],a[t]);
        for(int j=len>>1;(t^=j)<j;j>>=1);
    }
    for(int i=2;i<=len;i<<=1)
    {
        int wn=qpow(g,(mod-1)/i);
        for(int j=0;j<len;j+=i)
        {
            int w=1,t;
            for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
            {
                t=(ll)w*a[j+k+(i>>1)]%mod;
                a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
            }
        }
    }
    if(type==-1)
    {
        for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
        int t=qpow(len,mod-2);
        for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    init();
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)
        ans[i]=(ll)n*C(n,i)%mod;
    for(int i=2;i<=n;i++)(a[size[i]]+=jc[size[i]])%=mod;
    for(int i=0;i<=n;i++)b[i]=njc[n-i];
    NTT(a,len,1);NTT(b,len,1);
    for(int i=0;i<len;i++)c[i]=(ll)a[i]*b[i]%mod;
    NTT(c,len,-1);
    for(int i=1;i<=n;i++)
    {
        c[n+i]=(ll)c[n+i]*njc[i]%mod;
        ans[i]=(ans[i]-c[n+i]+mod)%mod;
    }

    memset(a,0,sizeof(a));
    for(int i=2;i<=n;i++)
    {   
        size[i]=n-size[i];
        (a[size[i]]+=jc[size[i]])%=mod;
    }
    NTT(a,len,1);
    for(int i=0;i<len;i++)c[i]=(ll)a[i]*b[i]%mod;
    NTT(c,len,-1);
    for(int i=1;i<=n;i++)
    {
        c[n+i]=(ll)c[n+i]*njc[i]%mod;
        ans[i]=(ans[i]-c[n+i]+mod)%mod;
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}