题目链接

A. Koxia and Whiteboards

注意每一步替换操作都是强制的，而不是可选的。所以就用一个multiset维护所有的数，每次选一个最小的替换掉即可。

时间复杂度\(O(nlogn)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL t,n,m,a[110],b[110];

int main()
{
  fileio();

  cin>>t;
  rep(tn,t)
  {
    scanf("%lld%lld",&n,&m);
    multiset <LL> st;
    rep(i,n) scanf("%lld",&a[i]),st.insert(a[i]);
    rep(i,m)
    {
      scanf("%lld",&b[i]);
      //if(*st.begin()<b[i])
      {
        st.erase(st.begin());
        st.insert(b[i]);
      }
    }
    LL ans=0;
    for(auto it:st) ans+=it;
    printf("%lld\n",ans);
  }

  termin();
}

B. Koxia and Permutation

k=1的情况，输出任意排列都可以。k>1时，发现一个包含数n的长度为k的字段的权值至少为n+1，盲猜存在一种排法使得最大权值就是n+1。其实下面的排法就满足要求：\(n,1,n-1,2,n-2,3\cdots\)。比如n=7时，排列就是\(7,1,6,2,5,3,4\)。在这种排法下，如果一个子段的最大值\(x>\frac n2\)，由于它右边的数是\(n+1-x\)，左边的数是\(n-x\)，所以子段的权值绝对不会超过\(n+1\)。子段的最大值\(\le \frac n2\)时权值不可能达到\(n+1\)。所以这种构造是正确的。

时间复杂度\(O(n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

int t,n,k;

int main()
{
  fileio();

  cin>>t;
  rep(tn,t)
  {
    cin>>n>>k;
    int lb=1,ub=n;
    while(lb<ub) printf("%d %d ",ub--,lb++);
    if(lb==ub) cout<<lb;
    cout<<endl;
  }

  termin();
}

C. Koxia and Number Theory

我们先\(O(n^2)\)地枚举数组中的每对数(a,b)，看看如果要求\(gcd(a+x,b+x)=1\)的话x需要满足什么条件。如果a=b显然无解。否则令a,b中较小的为c，较大的为c+d。则我们要求\(gcd(c+x,d)=1\)，也就是对于d的每个质因数，c+x都不能是这个质因数的倍数，也就是对于任意\(e|d,e是质数\)，满足\(x \neq -c (mod \ e)\)。枚举了所有\(O(n^2)\)对数之后我们会得到若干个限制，如果存在某个质数p，我们要求\(x\ mod \ p\neq 0,x\ mod\ p\neq 1\cdots x\ mod\ p\neq p-1\)，也就是所有p个限制都占满了，那肯定无解；否则根据中国剩余定理一定有解。

但是在上面枚举的过程中，\(d\)的数据范围是1e18，没法分解质因数。注意到一共只会产生\(\frac{n(n-1)}2\)个限制，所以在\(p>\frac{n(n-1)}2\)的情况下是不可能占满p个限制导致无解的，故只需考虑这个范围内的质数。

时间复杂度没仔细算，反正肯定是能过的。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

LL t,n,a[110],cnt[800][6000],lim;
vector <LL> pri;

bool isp(LL x)
{
  for(LL i=2;i*i<=x;++i) if(x%i==0) return false;
  return true;
}
void precalc()
{
  for(LL i=2;i<=6000;++i)
    if(isp(i)) pri.pb(i);
}

int main()
{
  fileio();

  precalc();
  cin>>t;
  repn(tn,t)
  {
    cin>>n;
    rep(i,n) cin>>a[i];
    LL tot=(n+1)*n/2+10;
    lim=0;
    rep(i,pri.size()) if(pri[i]<=tot) ++lim;
    bool bad=false;
    rep(i,n)
    {
      for(int j=i+1;j<n;++j)
      {
        LL bas=min(a[i],a[j]),sub=llabs(a[i]-a[j]);
        if(sub==0){bad=true;break;}
        rep(k,lim) if(sub%pri[k]==0)
        {
          LL x=(pri[k]-bas%pri[k])%pri[k];
          cnt[k][x]=tn;
        }
      }
      if(bad) break;
    }
    if(!bad)
    {
      rep(i,lim)
      {
        bool good=false;
        rep(j,pri[i]) if(cnt[i][j]!=tn){good=true;break;}
        if(!good){bad=true;break;}
      }
    }
    puts(bad ? "NO":"YES");
  }

  termin();
}

D. Koxia and Game

按照游戏的过程正着分析看不出什么，我们倒着看看。方便起见把删数的那个人称为K，选数的那个人称为M。考虑这三个序列的最后一个数组成的multiset\(\{a_n,b_n,c_n\}\)，如果K删掉了某个元素使得剩下的两个元素不相等，那K是不可能赢的，因为M总能找出一个元素使得最后形成的序列不是排列。所以\(a_n,b_n,c_n\)三个数不能全不同，至少得有两个相同的，且K一定是留下两个相同的数。倒数第二个位置同理，顺着推下去其实前面的每个位置都同理。

所以现在问题变成了这样：有两个数列a和b，对于每个i你可以在\(a_i,b_i\)中选恰好一个数，要求最后选出的序列是排列，求方案数。对于\(a_i=b_i\)的位置，会额外有\(n\)的方案数(因为原问题中\(c_i\)在这里可以乱选)。如果有解的话，最后把这个额外的方案数乘上就行了，下面的思考过程忽略这个额外的方案数。

转化成图论问题：把每个数看成一个点，对于每个i，在\(a_i,b_i\)之间连一条无向边。这个图中可能有自环和重边。建完图之后发现图是由一些连通块组成的。如果一个连通块内的点数和边数不相等，显然无解。否则这个连通块就是一个基环树，我们需要为每个点选一条相邻的边与其匹配，使得每条边恰好被匹配一次，并求出方案数。如果基环是一个自环，那显然只有1种方案。否则有两种方案，因为基环有两种匹配的方向。所以每个连通块的方案数都是1或2，全部乘起来就行了。

时间复杂度\(O(nlogn)\)，因为要使用并查集维护图(其实直接搜也可以O(n))。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const LL MOD=998244353;

LL t,n,a[100010],b[100010],cnt[100010],fa[100010],sc[100010],sz[100010];

LL Find(LL x){return fa[x]==x ? x:fa[x]=Find(fa[x]);}

int main()
{
  fileio();

  cin>>t;
  rep(tn,t)
  {
    cin>>n;
    rep(i,n) scanf("%lld",&a[i]);
    rep(i,n) scanf("%lld",&b[i]);
    repn(i,n) cnt[i]=sc[i]=0,fa[i]=i,sz[i]=1;
    LL mul=1;
    rep(i,n)
    {
      if(a[i]==b[i]) ++sc[a[i]],++cnt[a[i]],(mul*=n)%=MOD;
      else
      {
        ++cnt[a[i]];
        if(Find(a[i])!=Find(b[i])) fa[Find(a[i])]=Find(b[i]);
      }
    }
    repn(i,n) if(Find(i)!=i) cnt[Find(i)]+=cnt[i],sc[Find(i)]+=sc[i],++sz[Find(i)];
    bool bad=false;
    repn(i,n) if(Find(i)==i)
    {
      if(cnt[i]!=sz[i]){bad=true;break;}
      if(sc[i]==0) (mul*=2)%=MOD;
    }
    if(bad) puts("0");
    else printf("%lld\n",mul);
  }

  termin();
}

E. Koxia and Tree

我一开始想的是：对每个点求出进行完所有操作后这个位置包含蝴蝶的概率，然后用这个概率加权求出两两之间的距离和。不幸的是这么做是错的，因为每个点包含蝴蝶的概率并不独立，它们之间是有关联的，比如k=1时答案应该是0，这个方法算出的答案就不是0。

换一种思路。先把1定为树的根。对于每个子树，我们想求出从它的根到其父亲的那条边，在画出蝴蝶两两之间路径时期望被走了多少次。把所有边的这个值加起来就得到了蝴蝶两两之间距离和的期望，除以蝴蝶对数就得到答案了。对于点i，令\(sz_i=\)初始状态下(没开始操作的时候)i的子树内的蝴蝶数量。发现所有操作做完后i子树内的蝴蝶数量只有三种可能：\(sz_i-1,sz_i,sz_i+1\)，因为每条边最多运送一只蝴蝶，也最多只有一只蝴蝶能被运进或运出子树。如果能分别求出这三种情况发生的概率，也就能求出最终答案了。比如子树内蝴蝶数量为\(sz_i\)的概率是p，则对蝴蝶两两之间距离和的期望的贡献是\(sz_i\cdot(n-sz_i)\cdot p\)。这里我们计算期望时只有一个变量，不存在什么独立性的问题，所以正确性是有的。

对于一个点i，假设从它连向父亲的边的编号为j。如果我们知道在进行了j-1次操作后点i有蝴蝶的概率(p)与点i的父亲有蝴蝶的概率(q)，那就能求出上面说的三个概率了。这里p和q是独立的、没有关联的，因为前j-1次操作都是在这条边两侧的两个连通块内进行的，互不影响。所以这么做是有正确性的。

从前到后依次进行操作，并同时维护每个点有蝴蝶的概率，这点也是很容易做到的。假设当前边连接(x,y)，则令\(p_x=p_y=np,其中np=\frac{p_x+p_y}2\)即可，按照题目定义推一推就能得到。

时间复杂度\(O(n)\)。

点击查看代码 
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if(a&1) (ret*=res)%=MOD;
		a>>=1;
		(res*=res)%=MOD;
	}
	return ret;
}

LL n,k,a[300010],inv2=qpow(2,MOD-2),ans=0,dep[300010],sz[300010];
vector <LL> g[300010];
vector <pii> e;

LL dfs(LL pos,LL par)
{
  sz[pos]=a[pos];
  rep(i,g[pos].size()) if(g[pos][i]!=par)
  {
    dep[g[pos][i]]=dep[pos]+1;
    sz[pos]+=dfs(g[pos][i],pos);
  }
  return sz[pos];
}

int main()
{
  fileio();

  cin>>n>>k;
  LL x;rep(i,k){scanf("%lld",&x);a[x]=1;}
  LL y;
  rep(i,n-1)
  {
    scanf("%lld%lld",&x,&y);
    e.pb(mpr(x,y));
    g[x].pb(y);g[y].pb(x);
  }
  dfs(1,0);
  rep(i,n-1)
  {
    x=e[i].fi;y=e[i].se;

    if(dep[x]>dep[y]) swap(x,y);//x上y下
    LL pls=a[x]*(1LL-a[y]+MOD)%MOD*inv2%MOD,sub=a[y]*(1LL-a[x]+MOD)%MOD*inv2%MOD,mid=(1LL-pls-sub+MOD+MOD)%MOD;
    (ans+=sz[y]*(k-sz[y])%MOD*mid)%=MOD;
    (ans+=(sz[y]+1)*(k-sz[y]-1)%MOD*pls)%=MOD;
    (ans+=(sz[y]-1)*(k-sz[y]+1)%MOD*sub)%=MOD;

    LL sum=(a[x]+a[y])%MOD;
    (sum*=inv2)%=MOD;
    a[x]=a[y]=sum;
  }
  LL tot=(k-1)*k/2%MOD;
  (ans*=qpow(tot,MOD-2))%=MOD;
  cout<<ans<<endl;

  termin();
}