题解：P9174 [COCI 2022/2023 #4] Bojanje

· · 题解

通过读题可知是 dp 题，考察的是对状态的压缩，题目说 n 种颜色我们不能记录下每个小球的颜色，由于取球是随机的，所以位置是不重要的，我们就可以对每种颜色记录有几个，因为我们对于每种颜色具体是什么也不关心，只关心有几个球，所以可以进一步压缩。

vector<vector<int>> S;
vector<int> vec;
map<vector<int>, int> mp;
void dfs(int x) {
  if (x == 0) {
    S.push_back(vec);
    mp[vec] = S.size() - 1;
    return;
  }
  if (vec.size() && vec.back() > x) {
    return;
  }
  rep(i, (vec.size() ? vec.back() : 1), x) {
    vec.push_back(i);
    dfs(x - i);
    vec.pop_back();
  }
}

类似的压缩套路还有 AT_abc215_g。

然后我们按照状态转移可以拿到 sub2 36 分，拼上 sub1 就能拿到 64 分。

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = (l); i <= (int)(r); i++)
#define per(i, l, r) for (int i = (r); i >= (int)(l); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define max(a, b)  (!((a) < (b)) ? (a) : (b))
#define min(a, b)  ((a) < (b) ? (a) : (b))
using namespace std;
using i64 = long long;
#define int i64
const int maxn = 1000050, mod = 1e9 + 7, B = 700;
i64 power(i64 a, int b) {
  i64 res = 1;
  for (; b; a = (a * a) % mod, b /= 2){
    if (b % 2 == 1) {
      res = (res * a) % mod;
    }
  }
  return res;
}
vector<vector<int>> S;
vector<int> vec;
map<vector<int>, int> mp;
void dfs(int x) {
  if (x == 0) {
    S.push_back(vec);
    mp[vec] = S.size() - 1;
    return;
  }
  if (vec.size() && vec.back() > x) {
    return;
  }
  rep(i, (vec.size() ? vec.back() : 1), x) {
    vec.push_back(i);
    dfs(x - i);
    vec.pop_back();
  }
}
vector<int> change(vector<int> now, int a, int b) {
  vector<int> to = now;
  if (a == b) {
    return to;
  }
  if (now[a] != 1) {
    to[a]--;
    to[b]++;
  }
  if (now[a] == 1) {
    to[b]++;
    to.erase(to.begin() + a);
  }
  sort(to.begin(), to.end());
  return to;
}
int dp[1050][100];
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n, t, k;
  cin >> n >> t >> k;
  dfs(n);
  dp[0][0] = 1;
  int INV = power(n * n, mod - 2);
  rep(i, 1, t) {
    rep(j, 0, S.size() - 1) {
      if (dp[i - 1][j] == 0) {
        continue;
      }
      dp[i - 1][j] %= mod;
      vector<int> st = S[j];
      rep(a, 0, st.size() - 1) {
        rep(b, 0, st.size() - 1) {
          vector<int> nst = change(st, a, b);
          dp[i][mp[nst]] += dp[i - 1][j] * st[a] % mod * st[b] % mod * INV % mod;
        }
      }
    }
  }
  int ans = 0;
  rep(i, 0, S.size() - 1) {
    if (S[i].size() >= k) {
      ans += dp[t][i];
    }
  }
  cout << ans % mod << "\n";
  return 0;
}

然后的是套路的矩阵乘法优化。

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = (l); i <= (int)(r); i++)
#define per(i, l, r) for (int i = (r); i >= (int)(l); i--)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define max(a, b)  (!((a) < (b)) ? (a) : (b))
#define min(a, b)  ((a) < (b) ? (a) : (b))
using namespace std;
using i64 = long long;
#define int i64
const int maxn = 1000050, mod = 1e9 + 7;
i64 power(i64 a, int b) {
  i64 res = 1;
  for (; b; a = (a * a) % mod, b /= 2){
    if (b % 2 == 1) {
      res = (res * a) % mod;
    }
  }
  return res;
}
vector<vector<int>> S;
vector<int> vec;
map<vector<int>, int> mp;
void dfs(int x) {
  if (x == 0) {
    S.push_back(vec);
    mp[vec] = S.size() - 1;
    return;
  }
  if (vec.size() && vec.back() > x) {
    return;
  }
  rep(i, (vec.size() ? vec.back() : 1), x) {
    vec.push_back(i);
    dfs(x - i);
    vec.pop_back();
  }
}
vector<int> change(vector<int> now, int a, int b) {
  vector<int> to = now;
  if (a == b) {
    return to;
  }
  if (now[a] != 1) {
    to[a]--;
    to[b]++;
  }
  if (now[a] == 1) {
    to[b]++;
    to.erase(to.begin() + a);
  }
  sort(to.begin(), to.end());
  return to;
}
struct node {
  int a[50][50];
  int n, m;
} A, B1, B;
node mul(node a, node b) {
  node c = {{}};
  c.n = a.n, c.m = b.m;
  rep(i, 0, a.n - 1) {
    rep(j, 0, b.m - 1) {
      rep(k, 0, a.m - 1) {
        c.a[i][j] += a.a[i][k] * b.a[k][j] % mod;
      }
      c.a[i][j] %= mod;
    }
  }
  return c;
}
int n, t, k;
void initB() {
  int INV = power(n * n, mod - 2);
  rep(i, 0, S.size() - 1) {
    vector<int> st = S[i];
    rep(a, 0, st.size() - 1) {
      rep(b, 0, st.size() - 1) {
        vector<int> nst = change(st, a, b);
        (B.a[mp[nst]][i] += st[a] * st[b]  * INV % mod) %= mod;
      }
    }
  }
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  cin >> n >> t >> k;
  dfs(n);
  A.n = S.size();
  A.m = 1;
  B.n = B.m = S.size();
  initB();
  A.a[0][0] = 1;
  t-=1;
  B1 = B;
  for (; t; B1 = mul(B1, B1), t /= 2){
    if (t % 2 == 1) {
      B = mul(B, B1);
    }
  }
  A = mul(B, A);
  int ans = 0;
  rep(i, 0, S.size() - 1) {
    if ((int)S[i].size() >= k) {
      ans += A.a[i][0];
    }
  }
  cout << ans % mod << "\n";
  return 0;
}