RC-07 题解

feecle6418 · 2022-12-30 16:27:33 · 个人记录

本次比赛中，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<n)，满足 a_i=1，再选择位置 j\ (i\le j<n)，把 a_i\sim a_{j} 都异或上 1。不能操作的人输。[游戏 1]

我们断言，这个游戏的结果等价于以下游戏：

A,B 轮流作如下操作：选择一个位置 i\ (i<n)，满足 a_i\ge 1，再选择位置 j\ (i\le j<n)，把 a_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;
}