题意：有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;
}

题意：一棵树，点i上有ai个石头，每次操作可以选择一条两个叶子之间的简单路径，并从路径上每个节点都移除一个石头。求是否可以经过一些操作之后移除所有石头。

从下往上dp，设点i子树中需要通过该点的路径数和为sum，那么就有sum-ai条路径跨过i点，2ai-sum条路径经过ai父亲。设需要通过该点的路径数最大的子树需要通过该点的路径数为mx，那么如果sum-mx<sum-ai则无解。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
int n,tot,root;
int a[N],head[N],nex[N<<1],to[N<<1];
int du[N],rem[N];
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void quit(){puts("NO");exit(0);}
void dfs(int x,int y)
{
    if(du[x]==1)
    {
        rem[x]=a[x];
        return;
    }
    int mx=0,sum=0;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
        {
            dfs(to[i],x);
            sum+=rem[to[i]];
            mx=max(mx,rem[to[i]]);
        }
    int v1=sum-a[x],v2=a[x]-v1;
    if(v1<0||v2<0)quit();
    if(sum-mx<v1)quit();
    rem[x]=v2;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        du[x]++;du[y]++;
    }
    if(n==2)return puts(a[1]==a[2] ? "YES" : "NO"),0;
    root=1;
    while(du[root]==1)root++;
    dfs(root,0);
    if(rem[root])quit();
    puts("YES");
    return 0;
}

题意：一棵n个点的树，其中一些点已经有值，需要给所有没有值的点赋值，使任意相邻的两个点相差恰好为1，求是否可行，可行求一组解。

对所有有值的点建一棵虚树，每个儿子会对父亲的取值范围和奇偶性有一个限制，从下往上dp，如果出现不合法的情况无解。之后虚树上没有值的点会有一个取值范围。从上往下dp，虚树上每个点取范围内任意一个满足奇偶性的值，并对虚树边上的点赋值，最后对不在虚树边上的点赋值。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
const int inf=1e9;
int n,tot,m,cnt,top;
int head[N],nex[N<<1],to[N<<1];
int fa[N][21],deep[N];
int val[N],L[N],R[N],pos[N],a[N],st[N],sig[N];
vector<int>vec[N];
void quit(){puts("No");exit(0);}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    fa[x][0]=y;
    for(int i=1;i<=20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    deep[x]=deep[y]+1;
    pos[x]=++cnt;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
            dfs(to[i],x);
}
int cmp(int x,int y){return pos[x]<pos[y];}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs1(int x)
{
    L[x]=-inf;R[x]=inf;sig[x]=-1;
    for(int i=0,t,d,v;i<vec[x].size();i++)
    {
        dfs1(t=vec[x][i]);
        d=deep[t]-deep[x];
        v=(R[t]+d)&1;
        L[x]=max(L[x],L[t]-d);
        R[x]=min(R[x],R[t]+d);
        if(sig[x]==-1)sig[x]=v;
        else if(sig[x]!=v)quit();
    }
    if(L[x]>R[x])quit();
    if(val[x]!=val[0])
    {
        if(val[x]<L[x]||val[x]>R[x])quit();
        if(sig[x]!=-1&&(val[x]&1)!=sig[x])quit();
        L[x]=R[x]=val[x];
    }
}
void dfs2(int x)
{
    for(int i=0,t,d,d1;i<vec[x].size();i++)
    {
        t=vec[x][i];
        d=deep[t]-deep[x];
        val[t]=max(L[t],val[x]-d);
        d1=(val[x]+d-val[t])/2;
        int now=val[t],p=t;
        for(int j=1;j<=d1;j++)
            val[fa[p][0]]=val[p]+1,p=fa[p][0];
        for(int j=1;j<d-d1;j++)
            val[fa[p][0]]=val[p]-1,p=fa[p][0];
        dfs2(t);
    }
}
void dfs3(int x,int y)
{
    if(val[x]==val[0])
        val[x]=val[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)dfs3(to[i],x);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    memset(val,-0x3f,sizeof(val));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        scanf("%d",&val[a[i]]);
    }
    dfs(1,0);
    sort(a+1,a+1+m,cmp);
    st[top=1]=1;
    for(int i=1,t;i<=m;i++)
    {
        while((t=lca(a[i],st[top]))!=st[top])
        {
            if(deep[t]>deep[st[top-1]])
            {
                vec[t].push_back(st[top]);
                st[top]=t;
            }
            else
            {
                vec[st[top-1]].push_back(st[top]);
                top--;
            }
        }
        if(st[top]!=a[i])
            st[++top]=a[i];
    }
    for(int i=top;i>1;i--)
        vec[st[i-1]].push_back(st[i]);
    dfs1(1);
    val[1]=L[1];
    dfs2(1);
    dfs3(1,0);
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%d\n",val[i]);
    return 0;
}