杂题（四）

大家好！欢迎收看杂题（四）！《杂题》系列陪伴大家度过了很久的时光，这真是神奇呢

syc437 树形dp

http://119.28.3.174/contest/138/problem/437

我看错题了！我以为可以不连续的播放！

那么，一个点开始的时间，一定是从他开始的一条路径的点权和。对此$dp$即可。

复杂度$O(n^2logn)$。

syc435 交互/思维/随机

http://119.28.3.174/contest/138/problem/435

一点也不会！

最优方法是插值！自己定一个模数，看成$16$次多项式。

http://119.28.3.174/submission/58050

题解就是，对于随机集合，求出他们的异或和。如果把所代表的集合插进线性基，增秩的概率很高。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const unsigned int s = (1 << 16) - 1;
//
vector<int> encode(vector<int> v, int lim) {
  mt19937 rnd(time(0));
  vector<int> ans;
  vector<unsigned int> vv;
  rep(i, 8) {
    vv.emplace_back((unsigned int)v[i] >> 16);
    vv.emplace_back((unsigned int)v[i] & s);
  }
  int c = 0;
  for (unsigned int &to : vv) to = (to << 16) + (1 << (c++));
  rep(tt, 1000) {
    unsigned now = 0;
    for (unsigned int to : vv) if (rnd() & 1) now ^= to;
    if (!now) { --tt; continue; }
    ans.emplace_back(now);
  }
  return ans;
}
vector<int> decode(int (*const arr)(int), int n, int lim) {
  int rnk = 0;
  unsigned int b[16];
  memset(b, 0, sizeof(b));
  int *seed = new int;
  mt19937 rnd(time(0) + (ll)seed);
  rep(tt, lim) {
    unsigned int x = arr(rnd() % n);
    rep(i, 16) if (x >> i & 1) {
      if (!b[i]) {
        b[i] = x;
        ++rnk;
        break;
      }
      x ^= b[i];
    }
    if (rnk == 16) {
      for (int i = 15; i >= 0; i--) {
        for (int j = i - 1; j >= 0; j--) {
          if (b[j] >> i & 1) {
            b[j] ^= b[i];
          }
        }
      }
      vector<int> res;
      rep(i, 16) b[i] >>= 16;
      rep(i, 8) {
        res.emplace_back((b[i << 1] << 16) | b[i << 1 | 1]);
      }
      return res;
    } 
  }
  return vector<int>(8);
}

还有什么问题吗，欢迎在评论区和小编讨论哦！