Preface
不管怎么说，最后还是被我苟上橙名了（虽然刚好2100整，不多不少）
感觉我在1900~2100之间卡了好久好久，反观我的队友都是打上紫名后随便两三场就打上橙了，狠狠地羞辱我这个铁混子
由于暑假集训打的校内排名比较高，作为新队伍也拿到了今年的一场CCPC+一场ICPC的名额，虽然要自费出行但还是让人很期待的说
这场其实也没啥亮点，就中规中矩地把A~B2写完，剩下一个小时对着C发呆就结束了
比赛最后几分钟徐神点醒我C题的正解，但我是完全没往那方面想，看来计数这么久了还是一点不会的说
A. Fill in the Matrix
简单构造题，首先特判掉\(m=1\)的情况
考虑要让\(\operatorname{MEX}\)尽量大，相当于要贪心地先让\(0\)出现，再让\(1\)出现，依此类推
那我们就像这样贪心地构造列，稍微手玩一下很容易发现可以用如下的构造方法（以\(n=8,m=5\)为例）：
5 0 1 2 3 4
4 5 0 1 2 3
3 4 5 0 1 2
2 3 4 5 0 1
1 2 3 4 5 0
1 2 3 4 5 0
1 2 3 4 5 0
1 2 3 4 5 0
即我们可以用\(m-1\)行构造出最后答案为\(m\)的情况，然后要注意下如果\(n\ge m\)那么多出来的行不能乱填，随便复制前面的某一行即可
而如果行数比较少的话就只能构造出答案为\(n+1\)的情况
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,m; vector <int> a[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%d",&t);t;--t)
{
RI i,j; if (scanf("%d%d",&n,&m),m==1)
{
for (puts("0"),i=1;i<=n;++i) puts("0"); continue;
}
for (i=1;i<=n;++i) a[i].resize(m+1);
for (i=1;i<=min(n,m-1);++i)
{
for (j=1;j<=i;++j) a[i][j]=j+m-1-i;
for (j=i+1;j<=m;++j) a[i][j]=j-(i+1);
}
for (i=m;i<=n;++i) a[i]=a[m-1];
for (printf("%d\n",min(n+1,m)),i=1;i<=n;++i) for (j=1;j<=m;++j)
printf("%d%c",a[i][j]," \n"[j==m]);
}
return 0;
}
B1. Candy Party (Easy Version)
首先排除掉显然无解的情况，然后求出序列的平均数\(avg\)
考虑枚举每个数\(a_i\)，因为所有数都要给出一次并收入一次，因此每个数都可以枚举一个二元组\((j,k)\)，表示\(a_i+2^j-2^k=avg\)
显然如果某个数找不到这个合法的二元组就直接无解了，不然可以证明这样的二元组一定是唯一的
那么我们只要按位把加上的数和减去的数扔进桶里，然后看下是否每一位对应的都相同即可
注意对于那些初始时就有\(a_i=avg\)的数我们可以直接忽略，因为我们可以把它们当作类似于中转站一样的作用，扔进去什么然后吐出来什么到原来想去的地方即可
而至于最后从哪个点开始以及具体怎么操作可以完成这个过程，感性体会一下会发现一定是存在一种构造方法的
总复杂度\(O(n\log^2 a_i)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],c1[35],c2[35];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j,k; int avg=0; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),avg+=a[i];
if (avg%n) { puts("No"); continue; } else avg/=n;
for (i=0;i<=32;++i) c1[i]=c2[i]=0;
bool flag=1; for (i=1;i<=n&&flag;++i) if (a[i]!=avg)
{
bool sign=0; for (j=0;j<=32&&!sign;++j) for (k=0;k<=32&&!sign;++k)
if (a[i]+(1LL<<j)-(1LL<<k)==avg) ++c1[j],++c2[k],sign=1;
if (!sign) flag=0;
}
for (i=0;i<=32&&flag;++i) if (c1[i]!=c2[i]) flag=0;
puts(flag?"Yes":"No");
}
return 0;
}
B2. Candy Party (Hard Version)
B2和B1的区别就在于B1强制每个数只能分成两份，而B2允许某个数只分出一份
显然这样的数只有满足\(|a_i-avg|=2^k\)的那些数，并且这些数最后可以选择保留贡献到第\(k\)位或者拆成\(\pm2^{k+1}\mp2^k\)的形式
我们可以把这样的数的个数（正负分开）单独记录下来，而那些只能拆成两位的数还是和之前一样先统计好
贪心地从高位到低位处理，在处理第\(i\)位时先看第\(i+1\)位确定的是否相等，如果不等的话就分裂这一位保证\(i+1\)位相等，不难证明这样一定是最优的
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int t,n,a[N],c1[35],c2[35],d1[35],d2[35];
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t);t;--t)
{
RI i,j,k; int avg=0; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]),avg+=a[i];
if (avg%n) { puts("No"); continue; } else avg/=n;
for (i=0;i<=32;++i) c1[i]=c2[i]=d1[i]=d2[i]=0;
bool flag=1; for (i=1;i<=n&&flag;++i) if (a[i]!=avg)
{
bool sign=0; for (j=0;j<=32&&!sign;++j)
{
if (a[i]+(1LL<<j)==avg) ++d1[j],sign=1;
if (a[i]-(1LL<<j)==avg) ++d2[j],sign=1;
}
for (j=0;j<=32&&!sign;++j) for (k=0;k<=32&&!sign;++k)
if (a[i]+(1LL<<j)-(1LL<<k)==avg) ++c1[j],++c2[k],sign=1;
if (!sign) flag=0;
}
for (i=31;i>=0&&flag;--i)
{
if (c1[i+1]==c2[i+1])
{
c1[i]+=d1[i]; c2[i]+=d2[i]; continue;
}
if (c1[i+1]<c2[i+1])
{
int dlt=c2[i+1]-c1[i+1];
if (dlt>d1[i]) { flag=0; continue; }
d1[i]-=dlt; c1[i+1]+=dlt; c2[i]+=dlt; c1[i]+=d1[i]; c2[i]+=d2[i];
}
if (c1[i+1]>c2[i+1])
{
int dlt=c1[i+1]-c2[i+1];
if (dlt>d2[i]) { flag=0; continue; }
d2[i]-=dlt; c2[i+1]+=dlt; c1[i]+=dlt; c1[i]+=d1[i]; c2[i]+=d2[i];
}
}
for (i=0;i<=32&&flag;++i) if (c1[i]!=c2[i]) flag=0;
puts(flag?"Yes":"No");
}
return 0;
}
C. Travel Plan
唉铸币了并没有想到有用的状态只有\(O(\log n)\)种，失策失策
首先考虑转换题意，假设我们知道了二叉树中长度为\(i\)的路径的条数\(c_i\)（由于这个是平衡二叉树所以路径长度是\(\log n\)级别的），那么可以直接枚举路径上的最大值\(k\)，则贡献为：
\[k\times [k^i-(k-1)^i]\times m^{n-i}
\]
显然如果已知\(\{c_i\}\)就可以\(O(m\log n)\)地计算答案了，很容易想到DP，设\(f_{i,j}\)表示以\(i\)为端点，长度为\(j\)的路径条数，\(g_{i,j}\)表示经过\(i\)（排除以\(i\)为端点的情况），长度为\(j\)的路径条数，显然转移就是合并两个子树，但我们不可能像这样显式地遍历整棵树
稍作思考会发现其实我们根本不关心树根的编号是什么，只要知道子树的大小那么它的贡献就已经确定了
同时很容易证明其实合法的子树大小只有\(O(\log n)\)种，因此直接写个记搜就可以通过了，这部分的复杂度是\(O(\log^3 n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int M=100005,mod=998244353;
int t,n,m,coef[130],pw[M][130]; map <int,int> f;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI m)
{
for (RI i=1,j;i<=m;++i)
for (pw[i][0]=1,j=1;j<130;++j)
pw[i][j]=1LL*pw[i][j-1]*i%mod;
}
inline int DP(int n)
{
if (!n) return 0; if (n==1) return coef[1];
if (f.count(n)) return f[n];
static int c1[65],c2[65]; RI i,j; int tmp=n,ret=0;
memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2));
for (c1[0]=c2[0]=1,--n,i=0;n;++i)
{
int dlt=min(n,1LL<<i); c1[i+1]+=dlt; n-=dlt;
dlt=min(n,1LL<<i); c2[i+1]+=dlt; n-=dlt;
}
for (i=0;i<65;++i) for (j=0;j<65;++j)
(ret+=coef[i+j+1]*(c1[i]%mod)%mod*(c2[j]%mod)%mod)%=mod;
int sum1=-1,sum2=-1; for (i=0;i<65;++i) sum1+=c1[i],sum2+=c2[i];
return f[tmp]=(ret+DP(sum1)+DP(sum2))%mod;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
for (scanf("%lld",&t),init(100000);t;--t)
{
RI i,j; for (scanf("%lld%lld",&n,&m),i=1;i<=min(n,129LL);++i)
{
for (coef[i]=0,j=1;j<=m;++j)
(coef[i]+=(pw[j][i]-pw[j-1][i]+mod)*j%mod)%=mod;
(coef[i]*=quick_pow(m,n-i))%=mod;
}
f.clear(); printf("%lld\n",DP(n));
}
return 0;
}
Postscript
打上橙后可以安心小号摆烂了，咱也没那个实力和精力冲红名的说