本次比赛中，ABD 的代码长度均不超过 800 byte，是当之无愧的小清新比赛！
A
先考虑 $B=2$。首先，二进制表示全部是 1 的数肯定全都是满足要求的。
还有什么数可能满足要求？注意到，如果二进制表示里只有一位不是 1，也是满足要求的。
而容易发现只有这两种数满足要求，直接计算即可。
推广，当 $B$ 任意时，容易发现 x(B-1)(B-1)(B-1)(B-1)(B-1) 满足要求，并且把其中任意一个 $B-1$ 换成 $B-2$ 也满足要求。
怎么计算满足要求的数 $x$ 的个数呢？
- 如果 $x$ 的位数小于 $n$ 的，都满足要求，容易直接 $O(1)$ 计算。
- 如果 $x$ 的位数等于 $n$ 的，但是首位小于 $n$，也满足要求，容易直接 $O(1)$ 计算。
- 如果 $x$ 的位数等于 $n$，首位等于 $n$，找到 $n$ 除了首位之外最长的一段 $B-1$，如果 $B-2$ 在这之前都可以；还要特判一下恰好在分界这里可不可以。
时间复杂度 $O(\log n)$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> ve;
const int mod=998244353;
ll n,B,a[70];
void Solve(){
scanf("%lld%lld",&n,&B);
ll tn=n,ans=0;
int s=0;
while(tn)a[++s]=tn%B,tn/=B;
for(int i=1;i<s;i++)ans+=(B-1)*i;
ans+=(a[s]-1)*s;
int lst=0;
for(int i=s-1;i>=1;i--){
if(a[i]<B-1){
lst=i;
break;
}
}
if(lst==0)ans+=s;
else {
ans+=s-1-lst;
if(a[lst]==B-2){
bool ok=1;
for(int i=lst-1;i>=1;i--)if(a[i]<B-1)ok=0;
if(ok)ans++;
}
}
cout<<ans<<'\n';
}
int main(){
int t;
scanf("%d",&t);
while(t--)Solve();
}
B
这题曾经想放进我和 gyh 出的月赛。但是好像因为结论过于简单而且可以用各种方法得出换掉了。
结论是：设 1 的位置为 $a_1,\dots,a_m$，若 $(n-a_i)$ 的异或和为 0 则后手赢否则先手赢。
首先给序列做前缀和（把原序列看成差分，那么在新序列上的操作就是区间异或），游戏变为：
- A,B 轮流作如下操作：选择一个位置 $i\ (i
我们断言，这个游戏的结果等价于以下游戏：
- A,B 轮流作如下操作：选择一个位置 $i\ (i减一、$a_{i+1}\sim a_j$ 都加上一（这时序列不一定总是 01 序列了）。不能操作的人输。[游戏 2]
证明：注意到在游戏二中每一单位 $a_i$ 是独立的（把 $a_i$ 看成 $n$ 堆石子分别的石子数，则一个石子的操作不影响另一石子），所以游戏可以看成 $\sum a_i$ 个游戏的和。所以游戏的 SG 是每个石子的单位游戏的 xor。所以把游戏二中的 $a_i$ 在 mod 2 意义下操作不影响结果。所以游戏二等价于游戏一。
那么只需要解决游戏二。可以归纳证明在第 $i$ 堆石子里的一颗石子 SG 值等于 $lowbit(n-i)$，那么整个题就化为（注意，最开始给的是差分）：
- 给出某些区间 $[l,r]$，求 $lowbit(l)\sim lowbit(r)$ 的异或。
容易在 $O(m\log n)$ 时间内求出，已经可以过了。
进一步讨论可以发现这就等价于最开始的结论（留作练习）。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m;
ll n;
void Solve(){
cin>>n>>m;
assert(2<=m),assert(m<=n),assert(m%2==0);
ll sum=0,x,lst=0;
for(int i=1;i<=m;i++)scanf("%lld",&x),sum^=n-x,assert(x>lst),assert(x<=n),lst=x;
if(!sum)puts("TIN");
else puts("NIT");
}
int main(){
int t;
cin>>t;
while(t--)Solve();
}
C
当然，经过很多常数优化的标程能在时限（5s）内跑出所有数据。但是作为参赛者，你不需要关心常数！理论上，只要有一个能在合理时间内（几分钟）跑出来的做法，就能 AC 这道题，因为可以写个高精度，预处理所有答案不取模的值，然后打表。所以我们的目标就是得到一个做法，不关心时间复杂度。
考虑设计一个暴力 dp。设 $f(n,m,l,r)$ 表示有多少个符合要求的长度为 $n$ 的排列的 $m$ 元组，且逆序对数在 $[l,r]$ 之间，且逆序对数最小的恰好有 $l$ 个逆序对。转移时，将这 $m$ 个排列按照第一个元素划分为 $n$ 段，枚举每段的分界线位置的排列有几个逆序对，可以再用一个 dp 来合并。
标程的实现是 $O(n^{10}m^3)$ 的。（这个复杂度酷炫！）
感谢验题人 @Alex_Wei 的加强，他给出了一种 $O(n^8m^2)$ 的实现。
下面是标程。
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using L = __uint128_t;
constexpr int N = 15 + 5;
constexpr int M = 30 + 5;
constexpr int I = 110 + 5;
int n, m, mod, f[N][M][I][I];
struct FastMod {
ull b, m;
FastMod(ull b): b(b), m(ull((L(1) << 64) / b)) {}
ull reduce(ull a) {
ull q = ull((L(m) * a) >> 64), r = a - q * b;
return r >= b ? r - b : r;
}
};
void add(int &x, int y) {x += y, x >= mod && (x -= mod);}
int main() {
#ifdef ALEX_WEI
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> mod;
FastMod F(mod);
if(mod == 1) puts("0"), exit(0);
f[1][1][0][1] = 1;
for(int i = 2; i <= n; i++) {
int iv = i * (i - 1) / 2 + 1;
static int s[M][I][I];
memset(s, 0, sizeof(s));
for(int c = 1; c < m; c++)
for(int r = 1; r <= iv; r++)
for(int l = 0; l <= r; l++) {
s[c][r][l] = f[i - 1][c][l][r];
if(l) add(s[c][r][l], s[c][r][l - 1]);
}
for(int l = 0; l < iv; l++) {
static int g[M][I], h[M][I];
memset(g, 0, sizeof(g));
memset(h, 0, sizeof(h));
g[0][l] = h[0][l] = 1;
for(int j = i - 1; ~j; j--) {
for(int c = 0; c < m; c++)
for(int k = 0; k < iv; k++)
if(g[c][k])
for(int d = 1; d + c <= m; d++)
for(int r = max(j + 1, k + 1); r <= iv; r++) {
int coef;
if(c) {
coef = s[d][r - j][r - j];
if(k > j) add(coef, mod - s[d][r - j][k - j - 1]);
}
else {
if(k < j) continue;
coef = f[i - 1][d][k - j][r - j];
}
if(coef) add(h[c + d][r], F.reduce(1ll * g[c][k] * coef));
}
memcpy(g, h, sizeof(g));
}
for(int c = 1; c <= m; c++)
for(int r = 1; r <= iv; r++)
f[i][c][l][r] = g[c][r];
}
}
for(int u = 1; u <= n; u++) {
for(int t = 1; t <= m; t++) {
int ans = 0;
for(int l = 0; l < I; l++)
for(int r = l + 1; r < I; r++)
add(ans, f[u][t][l][r]);
cout << ans << " ";
}
cout << "\n";
}
return 0;
}
D
这个题出题的时候是找规律找出来的，但我一直不会证明。
答案等于
$$
\dfrac{\prod_{S\ne \varnothing,S\subseteq \{1,2,\dots,n\}}\left(\sum_{i\in S}a_i\right)^{\prod_{i\in S}(a_i-1)}}{\prod a_i}
$$
某一天我在浏览集训队论文的时候，发现 2020 年潘佳奇论文里的一个结论直接就证明了上述公式！读者可以参考《浅谈线性代数与图论的关系》中例题 5.4.2。
具体地，我们给出的超立方体上的图，实际上是 $n$ 张完全图，分别为 $a_1,\dots,a_n$ 个点，的 Cartesian 积。而它的生成树个数，就等于 Laplace 矩阵所有非零特征值的积除以点数。而 Cartesian 积 Laplace 矩阵的特征值，就是每个图的特征值集合里取一个相加的所有可能值。注意 $x$ 个点完全图 Laplace 矩阵 的特征值集合就是一个 $0$，$x-1$ 个 $x$，这就证明了上述结论。
容易用背包计算上面的式子（体积是 $\sum a_i$，价值是 $\prod (a_i-1)$），注意背包算的是指数和，应该对 $mod-1$ 取模。时间复杂度 $O(n^2\max a_i)$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<ll,2> pr;
typedef vector<int> ve;
const int mod=998244353;
int n,f[500005],prod=1,s=0;
int Power(int x,int y){
int r=1;
while(y){
if(y&1)r=1ll*r*x%mod;
x=1ll*x*x%mod,y>>=1;
}
return r;
}
int main(){
cin>>n,f[0]=1;
for(int i=1,x;i<=n;i++){
cin>>x,prod=1ll*prod*Power(x,mod-2)%mod;
for(int j=s;j>=0;j--)f[j+x]=(f[j+x]+1ll*f[j]*(x-1))%(mod-1);
s+=x;
}
for(int i=1;i<=s;i++)prod=1ll*prod*Power(i,f[i])%mod;
cout<<prod;
}
