[UOJ 62][UR #5]怎样跑得更快

一年前看的反演神题……(然后现在才A

继续阅读

[CodeChef BWGAME]Black-white Board Game

ao劲啊这题,,,

看到那个逆序对奇偶性就想到了行列式(考虑行列式的定义)……其实最后要判定的就是该矩阵行列式的正负性(或者是0)。

这个东西肯定可以高消搞成上三角,然后行列式就很好求了。但高消事\(O(n^3)\)的,会T掉。

考虑怎么去优化这个高消。首先在消元顺序合理的情况下,一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式,就是考虑从小到大对每个变量进行消元的时候,包含该变量的方程很多,并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。

考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置,所以可以考虑使用可并堆维护各个方程。同时,为了求每个方程当前最靠左的1的位置,我搞了个并查集(逃

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0.00) {
      return -1;
    } else {
      return 1;
    }
  }
}
 
int seg[maxn][2];
namespace BF {
  R A[105][105];
  inline int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      int r = i;
      for(int j = i + 1; j <= n; j ++) {
        if(fabs(A[j][i]) > fabs(A[i][i])) {
          r = j;
        }
      }
      if(r != i) {
        flag *= -1;
        for(int j = i; j <= n; j ++) {
          std::swap(A[i][j], A[r][j]);
        }
      } else {
        if(sign(A[i][i]) == 0) {
          return 0;
        }
      }
      for(int j = i + 1; j <= n; j ++) {
        if(sign(A[j][i]) == 0) continue;
        double f = A[j][i] / A[i][i];
        for(int k = i; k <= n; k ++) {
          A[j][k] -= A[i][k] * f;
        }
      }
    }
    int ret = flag;
    for(int i = 1; i <= n; i ++) {
      ret *= sign(A[i][i]);
    }
    return ret;
  }
  inline void solve(int n) {
    for(int i = 1; i <= n; i ++) {
      int L = seg[i][0], R = seg[i][1];
      for(int j = 1; j <= n; j ++) {
        if(L <= j && j <= R) {
          A[i][j] = 1;
        } else {
          A[i][j] = 0;
        }
      }
    }
    int v = (det(n));
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
namespace CT {
  /*
  struct Node {
    int l, r, id;
    bool operator <(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id < res.id;
        } else {
          return r < res.r;
        }
      } else {
        return l < res.l;
      }
    }
    bool operator >(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id > res.id;
        } else {
          return r > res.r;
        }
      } else {
        return l > res.l;
      }
    }
    bool operator ==(const Node &res) const {
      return (l == res.l) && (r == res.r) && (id == res.id);
    }
  };
  */
  struct N2 {
    int r, id;
    N2() {
      r = 0; id = 0;
    }
    N2(int x, int y) {
      r = x; id = y;
    }
    bool operator <(const N2 &res) const {
      if(r == res.r) {
        return id < res.id;
      } else {
        return r < res.r;
      }
    }
    bool operator >(const N2 &res) const {
      if(r == res.r) {
        return id > res.id;
      } else {
        return r > res.r;
      }
    }
    bool operator ==(const N2 &res) const {
      return (r == res.r) && (id == res.id);
    }
  };
  
  /* struct Node {
    Node *fa, *ch[2];
    N2 v; int l;
    int setv;
    int d() {
      return ((this == fa -> ch[1]) ? 1 : 0);
    }
    void sc(Node *c, int dir) {
      ch[dir] = c;
      c -> fa = this;
    }
    int cmp(const N2 &v2) const {
      if(v == v2) {
        return -1;
      } else {
        if(v2 < v) {
          return 0;
        } else {
          return 1;
        }
      }
    }
    void paint(int x) {
      if(l == -1) return;
      l = x; setv = x;
    }
    void pushdown(int x) {
      if(setv != -1) {
        ch[0] -> paint(setv);
        ch[1] -> paint(setv);
        setv = -1;
      }
    }
  };
  Node pool[maxn]; std::queue<int> FQ;
  Node *nil, *cur;
  void init_pool() {
    nil = cur = pool;
    nil -> l = nil -> setv = -1;
    nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  }
  Node *alloc_node(N2 x, int L) {
    Node *ret;
    if(FQ.empty()) {
      ret = ++ cur;
    } else {
      ret = FQ.front(); FQ.pop();
    }
    ret -> v = x;
    ret -> l = L; ret -> setv = -1;
    ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
    return ret;
  }
  
  inline bool is_root(Node *o) {
    return (o -> fa == nil)
  }
  inline void zig(Node *x) {
    int d = x -> d(); Node *y = x -> fa;
    if(is_root(y)) {
      x -> fa = y -> fa;
    } else {
      y -> fa -> sc(x, y -> d());
    }
    y -> sc(x -> ch[d ^ 1], d);
    x -> sc(y, d ^ 1);
  }
  void pdw_path(Node *x) {
    if(!is_root(x)) pdw_path(x -> fa);
    x -> pushdown();
  }
  inline void splay(Node *x) {
    pdw_path(x);
    while(!is_root(x)) {
      Node *y = x -> fa;
      if(!is_root(y)) {
        if((x -> d()) ^ (y -> d())) {
          zig(x);
        } else {
          zig(y);
        }
      }
      zig(x);
    }
  }
  Node *insert(Node *o, Node *x) {
    if(o == nil) return x;
    Node *last = o;
    int d;
    while(o != nil) {
      o -> pushdown(); last = o;
      d = o -> cmp(x -> v);
      o = o -> ch[d];
    }
    x -> ch[0] = x -> ch[1] = nil;
    last -> sc(x, d);
    splay(x); return x;
  }
  Node *top(Node *x) {
    Node *ret = x;
    while(x -> ch[0] == 0) {
      x -> paint
    }
  } */
  
  int par[maxn * 2];
  int get_fa(int x) {
    if(par[x] == x) return x;
    else return (par[x] = get_fa(par[x]));
  }
  void merge(int dir, int src) {
    dir = get_fa(dir); src = get_fa(src);
    if(dir == src) return;
    par[src] = dir;
  }
  bool is_same(int x, int y) {
    return (get_fa(x) == get_fa(y));
  }
  
  using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
  heap Q[maxn];
  int id[maxn], mp[maxn];
  int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      Q[i].clear();
    }
    for(int i = 1; i <= 2 * n; i ++) {
      par[i] = i;
    }
    for(int i = 1; i <= n; i ++) {
      id[i] = mp[i] = i;
      int L = seg[i][0], R = seg[i][1];
      Q[L].push(N2(R, i));
      merge(L, n + i);
    }
    for(int i = 1; i <= n; i ++) {
      if(Q[i].empty()) {
        return 0;
      }
      int p = id[i];
      if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
        flag *= -1;
        int np = (Q[i].top()).id;
#ifdef LOCAL
        printf("Swaping %d and %d.\n", p, np);
#endif
        int nv = mp[np];
        std::swap(id[i], id[nv]);
        std::swap(mp[np], mp[p]);
      }
      p = id[i];
      Q[i].pop();
      int r = seg[p][1];
      if(Q[i].size() > 0 && (Q[i].top()).r == r) {
        return 0;
      }
      if(r < n) {
        Q[r + 1].join(Q[i]);
        merge(r + 1, i);
      }
    }
    return flag;
  }
  void solve(int n) {
    int v = det(n);
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%d%d", &seg[i][0], &seg[i][1]);
    }
    if(n <= 100) {
      BF::solve(n);
    } else {
      CT::solve(n);
    }
  }
  return 0;
}

[BZOJ 3456]城市规划

aji多项式求逆毁我青春,,,

设\(f_i\)表示\(i\)个点的有标号无向联通图,考虑所有可能的图(记\(F_i\)为\(i\)个点的有标号无向图,显然\(F_i = 2^{\binom{i}{2}}\))和\(f\)的关系(使用图计数的经典套路:枚举1所在的联通块大小):

\[F_n = \sum_{i = 1}^n \binom{n-1}{i-1} f_i F_{n - i}\]

看起来事卷积?但是这个卷积没有办法直接用FFT/NTT求(当然分离一下项啊,移下项就可以分治NTT力)。

考虑进一步化简柿子。完全展开后会发现右边有个非常碍眼的\((n-1)!\),所以两边除一下:

\[\frac{F_n}{(n-1)!} =\sum_{i = 1}^n \frac{f_i}{(i-1)!}\cdot \frac{F_{n - i}}{(n - i)!}\]

然后这个问题就很毒瘤了:我们要求的答案多项式(除上那个阶乘)和一个已知多项式做卷积,可以得到另一个已知多项式……这样就需要多项式除法了,于是乎多项式逆元派上了用场。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const int maxn = 1020010;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a % ha;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x,  ha - 2LL);
}
 
int flip(int bi, int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi = inv(xi);
    for(int i = 0; i < n; i += (L << 1)) {
      ll w = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll v1 = A[j], v2 = A[j + L];
        A[j] = (v1 + (w * v2) % ha) % ha;
        A[j + L] = (v1 - (w * v2) % ha + ha) % ha;
        w = (w * xi) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B, int bi, ll *C) {
  static ll T1[maxn], T2[maxn];
  int n = (1 << bi);
  std::copy(A, A + n, T1);
  std::copy(B, B + n, T2);
  NTT(T1, bi); NTT(T2, bi);
#ifdef LOCAL
  puts("poly_mul :");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", A[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", B[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T1[i]);
  }
  puts("");
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T2[i]);
  }
  puts("");
#endif 
  for(int i = 0; i < n; i ++) {
    T1[i] = (T1[i] * T2[i]) % ha;
  }
#ifdef LOCAL
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", T1[i]);
  }
  puts("");
#endif 
  NTT(T1, bi, true);
  ll inv_n = inv(n);
  for(int i = 0; i < n; i ++) {
    T1[i] = (T1[i] * inv_n) % ha;
  }
  std::copy(T1, T1 + n, C);
#ifdef LOCAL
  for(int i = 0; i < (n); i ++) {
    printf("%lld ", C[i]);
  }
  puts("");
#endif 
}
 
void poly_inv(int mod, ll *B, ll *BB) {
  if(mod == 1) {
    BB[0] = inv(B[0]);
  } else {
    poly_inv((mod + 1) >> 1, B, BB);
    int bi = 0, sz = 1;
    while(sz <= ((mod * 2) + 1)) {
      bi ++; sz <<= 1;
    }
    ll inv_sz = inv(sz);
    static ll tmp[maxn];
    std::copy(B, B + mod, tmp);
    std::fill(tmp + mod, tmp + sz, 0LL);
    NTT(tmp, bi); NTT(BB, bi);
    for(int i = 0; i < sz; i ++) {
      tmp[i] = (tmp[i] * BB[i]) % ha;
      tmp[i] = (tmp[i] * (ha - 1LL)) % ha;
      tmp[i] = (tmp[i] + 2LL) % ha;
      tmp[i] = (tmp[i] * BB[i]) % ha;
    }
    NTT(tmp, bi, true);
    for(int i = 0; i < sz; i ++) {
      tmp[i] = (tmp[i] * inv_sz) % ha;
    }
    std::copy(tmp, tmp + mod, BB);
    std::fill(BB + mod, BB + sz, 0LL);
  }
}
 
int main() {
  static ll fac[maxn], A[maxn], B[maxn], BB[maxn];
  int n; scanf("%d", &n);
  int bi = 0, sz = 1;
  while(sz <= n + 1) {
    bi ++; sz <<= 1;
  }
  fac[0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  B[0] = 1LL;
  for(int i = 1; i <= n; i ++) {
    B[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
    B[i] = (B[i] * inv(fac[i])) % ha;
  }
  for(int i = 1; i <= n; i ++) {
    A[i] = pow_mod(2LL, (ll(i)) * (ll(i - 1)) / 2LL);
    A[i] = (A[i] * inv(fac[i - 1])) % ha;
  }
  poly_inv(n + 1, B, BB);
  poly_mul(A, BB, bi, A);
  printf("%lld\n", (A[n] * fac[n - 1]) % ha);
  return 0;
}

[BZOJ 3328]PYXFIB

又学了个新套路呢qwq

题面要求的其实是:

\[\sum_{i = 0}^n [k|i]\binom{n}{i} F_i\]

不考虑那个\([k|i]\),式子是非常像一个二项式展开的……

考虑构造矩阵的二项式展开,可以发现(其中\(A\)是斐波那契数列的二项式展开):

\[(I + A)^n = \sum_{i = 0}^n \binom{n}{i} A^i\]

然后\(k=1\)的情况我们就会做辣!接下来的问题是,如何取出一个生成函数中次数为\(k\)倍数的项求和?

然后我们发现单位根有个非常优良的性质:

\[\frac{1}{k} \sum_{i=1}^{k} \xi_k^{ni} = [k|n]\]

这里的\(n\)是一个常数,但是其实可以对应到原式里的某一项的次数。至于证明……满足\(k|n\)的情况左边显然是一堆1取平均值,其他情况可以通过等比数列求和证明左边为0。

于是可以构造多项式\((I+xA)^n\),把所有\(k\)次单位根做为\(x\)(求这个的话,可以利用原根)带入,对结果取平均值即可。

代码:

/**************************************************************
    Problem: 3328
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9080 ms
    Memory:832 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
typedef long long ll;
typedef ll Mat[2][2];
ll p; int k;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a % p;
  while(b) {
    if(1LL & b) ans = (ans * res) % p;
    res = (res * res) % p;
    b /= 2LL;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, p - 2LL);
}
 
void factor(int x, std::vector<int> &V) {
  int bd = sqrt(x + 0.5);
  for(int i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
  }
  if(x > 1) V.push_back(x);
}
int get_phi() {
  if(p == 2LL) return 1LL;
  std::vector<int> V;
  factor(p - 1LL, V);
  for(int i = 2; i <= (p - 1); i ++) {
    bool flag = true;
    for(int j = 0; j < V.size(); j ++) {
      int up = (p - 1) / V[j];
      if(pow_mod(i, up) == 1LL) {
        flag = false; break;
      }
    }
#ifdef LOCAL
    if(flag) printf("xi : %d\n", i);
#endif
    if(flag) return i;
  }
}
 
void mat_mul(const Mat &A, const Mat &B, int n, int m, int t, Mat &C) {
  Mat D; memset(D, 0, sizeof(D));
  for(int i = 0; i < n; i ++) {
    for(int j = 0; j < t; j ++) {
      for(int k = 0; k < m; k ++) {
        D[i][j] = (D[i][j] + (A[i][k] * B[k][j]) % p) % p;
      }
    }
  }
  memcpy(C, D, sizeof(D));
}
void mat_pow(const Mat &A, int n, ll b, Mat &ret) {
  Mat C, res;
  memset(C, 0, sizeof(C));
  for(int i = 0; i < n; i ++) C[i][i] = 1LL;
  memset(res, 0, sizeof(res));
  memcpy(res, A, sizeof(res));
  while(b) {
    if(1LL & b) mat_mul(C, res, n, n, n, C);
    mat_mul(res, res, n, n, n, res);
    b /= 2LL;
  }
  memcpy(ret, C, sizeof(C));
}
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    ll n;
    scanf("%lld%d%lld", &n, &k, &p);
    ll xi = pow_mod(get_phi(), (p - 1) / k);
    ll w = 1LL;
    ll ans = 0;
    for(int i = 0; i < k; i ++) {
      Mat X;
      memset(X, 0, sizeof(X));
      X[0][0] = X[1][0] = X[0][1] = w;
      X[0][0] = (X[0][0] + 1LL) % p;
      X[1][1] = (X[1][1] + 1LL) % p;
      mat_pow(X, 2, n, X);
#ifdef LOCAL
      puts("X : ");
      for(int i = 0; i < 2; i ++) {
        for(int j = 0; j < 2; j ++) {
          printf("%lld ", X[i][j]);
        }
        puts("");
      }
#endif
      ans = (ans + X[0][0]) % p;
      w = (w * xi) % p;
    }
    ans = (ans * inv(k)) % p;
    printf("%lld\n", ans);
  }
  return 0;
}

[BZOJ 4919][Lydsy1706月赛]大根堆

ao神啊这题,,,

很显然的思路是设计状态,然后线段树合并或者线段树启发式合并转移来优化一下,但是真的不好写……

考虑求LIS的那个二分+单调数组来做,那个东西的本质其实就是维护了一堆各种长度的断点一样的东西(考虑答案为\(n\),\(n - 1\)……的情况,在值的选取上各个情况之间会有断点)。那么我们就用一个multiset来维护断点,然后启发式合并即可。

考虑一棵子树,把根的子树进行合并,根加进来之后对断点会有何影响?那么考虑现在那个multiset里那个东西的后继(要lower_bound,因为如果有和根权值一样的点的话拐点不会发生变化。这里讨论有后继的情况),如果要取到那个点的长度的LIS的话,现在只需要小于等于根的权值的点就行了,取到这个点也不会使LIS变大(它不能和根共存),所以那个点就不是拐点了。并且无论是否出现这种情况,根那个点都会成为一个新的拐点。

然后DFS一遍就行啦。

代码:

/**************************************************************
    Problem: 4919
    User: danihao123
    Language: C++
    Result: Accepted
    Time:992 ms
    Memory:25648 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
const int maxn = 200005;
std::vector<int> G[maxn];
 
std::multiset<int> *st[maxn];
void merge(int x, int y) {
  if(st[x] -> size() < st[y] -> size()) std::swap(st[x], st[y]);
  while(st[y] -> size() > 0) {
    std::multiset<int>::iterator it = st[y] -> begin();
    int v = *it; st[y] -> erase(it);
    st[x] -> insert(v);
  }
}
int d[maxn];
void dfs(int x) {
  for(int i = 0; i < G[x].size(); i ++) {
    int v = G[x][i];
    dfs(v);
    merge(x, v);
  }
  std::multiset<int>::iterator it = st[x] -> lower_bound(d[x]);
  if(it != (st[x] -> end())) st[x] -> erase(it);
  st[x] -> insert(d[x]);
}
 
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int f; scanf("%d%d", &d[i], &f);
    G[f].push_back(i);
  }
  for(int i = 1; i <= n; i ++) {
    st[i] = new std::multiset<int>();
  }
  dfs(1);
  printf("%d\n", st[1] -> size());
  for(int i = 1; i <= n; i ++) {
    delete st[i];
  }
  return 0;
}

[洛谷 P4177][CEOI2008]order

啊啊啊只会做水题了……

很显然是最小割吧……长得很像最大权闭合子图,但又不一样的。

那么就把最大权闭合子图中的无穷边(我称之为违约边)的费用改成租用的费用。这样一来,如果选了计划(不割计划)还不购买机器(割去机器),那就只能支付租金了(割违约边)。

这其实也算是一种套路了吧?觉得以前见过很多次但是有很多叫法……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <algorithm>
#include <queue>
const int maxn = 200005;
const int maxm = 2000005;
const int maxe = maxm << 2;
int n, m;
int first[maxn];
int next[maxe], to[maxe], flow[maxe], cap[maxe];
int gcnt = 0;
inline void add_edge(int u, int v, int f) {
  gcnt ++;
  next[gcnt] = first[u];
  first[u] = gcnt;
  to[gcnt] = v;
  flow[gcnt] = 0; cap[gcnt] = f;
}
inline int rev(int i) {
  return (((i - 1) ^ 1) + 1);
}
inline void ins_edge(int u, int v, int f) {
  add_edge(u, v, f);
  add_edge(v, u, 0);
}
 
int d[maxn];
int s, t, tot;
inline bool bfs() {
  static bool vis[maxn];
  std::fill(vis, vis + 1 + tot, false);
  std::fill(d, d + 1 + tot, 0);
  std::queue<int> Q;
  Q.push(s); vis[s] = true; d[s] = 1;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1; vis[v] = true;
        Q.push(v);
      }
    }
  }
  return vis[t];
}
int cur[maxn];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ans = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i];
    int f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ans += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ans;
}
int dinic() {
  int ans = 0;
  while(bfs()) {
    for(int i = 0; i <= tot; i ++) cur[i] = first[i];
    ans += dfs(s, 0x7fffffff);
  }
  return ans;
}

int main() {
  int n, m; scanf("%d%d", &n, &m);
  s = 0; t = tot = n + m + 1;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    int w, p; scanf("%d%d", &w, &p);
    ins_edge(s, i, w); ans += w;
    for(int j = 1; j <= p; j ++) {
      int id, co; scanf("%d%d", &id, &co);
      ins_edge(i, id + n, co);
    }
  }
  for(int i = n + 1; i <= n + m; i ++) {
    int co; scanf("%d", &co);
    ins_edge(i, t, co);
  }
  printf("%d\n", ans - dinic());
  return 0;
}

[LibreOJ 2137][ZJOI2015]诸神眷顾的幻想乡

复习SAM了呢~

那个度数为1的点至多有20个的条件非常神奇……让我们想想怎么用。

我们发现,(钦定根后)在树上有一条路径是弯的这种情况非常不好统计,但如果是直着下来就很好说(把所有从根到一个点的路径扔到SAM里,然后是经典题)。但是,任何一条路一定会在某个度数为1的点为根的情况下是直的(可以意会一下吧(逃

然后我们从那20个点每个点当根DFS一遍,把搞出来的每一条从根开始的路径放前缀Trie里。然后对前缀Trie构一个SAM就行啦~

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int BUFSIZE = 128 * 1024 * 1024;
char buf[BUFSIZE];
void *alloc(size_t size) {
  static char *cur = buf;
  if(cur - buf + size > BUFSIZE) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}

const int maxn = 100005;
std::vector<int> G[maxn];
int deg[maxn];

int ssiz;
struct TNode {
  TNode *ch[10];
};
TNode *alloc_tn() {
  auto ret = (TNode*)alloc(sizeof(TNode));
  memset(ret -> ch, 0, sizeof(ret -> ch));
  return ret;
}
TNode *step(TNode *o, int c) {
  if(!(o -> ch[c])) {
    o -> ch[c] = alloc_tn();
  }
  return (o -> ch[c]);
}
TNode *trt;
int col[maxn];
void dfs(int x, int fa, TNode *last) {
  TNode *np = step(last, col[x]);
  for(auto v : G[x]) {
    if(v != fa) {
      dfs(v, x, np);
    }
  }
}

struct Node {
  int len; Node *fa;
  Node *ch[10];
};
std::vector<Node*> pool;
Node *alloc_node(int len = 0, Node *fa = NULL) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> len = len; ret -> fa = fa;
  memset(ret -> ch, 0, sizeof(ret -> ch));
  pool.push_back(ret);
  return ret;
}
Node *rt;
Node *extend(int c, Node *last) {
  Node *np = alloc_node(last -> len + 1);
  Node *p = last;
  while(p != NULL && p -> ch[c] == NULL) {
    p -> ch[c] = np; p = p -> fa;
  }
  if(p == NULL) {
    np -> fa = rt;
  } else {
    Node *q = p -> ch[c];
    if(q -> len == p -> len + 1) {
      np -> fa = q;
    } else {
      Node *nq = alloc_node(p -> len + 1, q -> fa);
      memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
      q -> fa = np -> fa = nq;
      while(p != NULL && p -> ch[c] == q) {
        p -> ch[c] = nq; p = p -> fa;
      }
    }
  }
  return np;
}
void dfs_2(TNode *o, Node *last) {
  for(int i = 0; i < ssiz; i ++) {
    TNode *v = o -> ch[i];
    if(!v) continue;
    Node *np = extend(i, last);
    dfs_2(v, np);
  }
}

using ll = long long;
int main() {
  int n; scanf("%d%d", &n, &ssiz);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &col[i]);
  }
  trt = alloc_tn();
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
    deg[u] ++; deg[v] ++;
  }
  for(int i = 1; i <= n; i ++) {
    if(deg[i] == 1) {
      dfs(i, 0, trt);
    }
  }
  rt = alloc_node();
  dfs_2(trt, rt);
  ll ans = 0;
  for(auto p : pool) {
    if(p -> fa) {
      ans += p -> len - p -> fa -> len;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

[LibreOJ 2034][SDOI2016]排列计数

我这种池沼只会做水题陶冶身心了……

考虑用\(f_i\)表示长为\(i\)的完全错位全排列的个数,那么有\(i\)个错位的长度为\(n\)的全排列的数量就是\(\binom{n}{i} f_i\)。从这一点出发,可以得到一个式子(枚举错位的有几个):

\[n! = \sum_{i = 0}^n \binom{n}{i} f_i\]

考虑使用二项式反演,得到:

\[
\begin{aligned}
f_n &= \sum_{i = 0}^n (-1)^{n - i}\binom{n}{i} i!\\
&= \sum_{i = 0}^n (-1)^{n - i}\frac{n!}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^{n - i}}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^i}{i!}
\end{aligned}
\]

后面的和式可以预处理,然后就做完啦~

代码:

#include <cstdio>
#include <cstring>
using ll = long long;
const ll ha = 1000000007LL;
inline ll pow_mod(const ll &a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
inline ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

const int N = 1000000;
const int maxn = N + 5;
ll fac[maxn], f[maxn];
inline void process() {
  fac[0] = 1LL;
  for(int i = 1; i <= N; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  for(int i = 0; i <= N; i ++) {
    f[i] = (i % 2 == 1) ? (ha - 1LL) : 1LL;
    f[i] = (f[i] * inv(fac[i])) % ha;
    if(i > 0) f[i] = (f[i - 1] + f[i]) % ha;
  }
}

int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    int p = n - m;
    ll bs = (fac[p] * f[p]) % ha;
    ll C = (fac[n] * inv((fac[p] * fac[m]) % ha)) % ha;
    printf("%lld\n", (bs * C) % ha);
  }
  return 0;
}

[BZOJ 5093][Lydsy1711月赛]图的价值

统计的时候,考虑每个店对每个图的贡献,可以看出答案是:

\[n2^{\tfrac{(n - 1)(n - 2)}{2}}\,\sum_{i = 0}^{n - 1} \binom{n - 1}{i} i^k\]

求和号前面还好说,主要看求和号后面的咋搞。

后面的那一部分是个经典题吧……但我还是来推导一番吧:

\[
\begin{aligned}
\sum_{i = 0}^{m} \binom{m}{i} i^k&= \sum_{i = 0}^{m} \binom{m}{i}\sum_{j = 0}^k S(k, j) j!\binom{i}{j}\\
&= \sum_{j = 0}^k S(k, j) j! \sum_{i = 0}^m \binom{m}{i}\binom{i}{j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} \sum_{i = 0}^{m} \binom{n - j}{i - j} \\
&= \sum_{j = 0}^k S(k, j) m^{\underline{j}} 2^{m - j}
\end{aligned}
\]

然后如果我们能高效的求出某一行的第二类斯特林数,那么问题就迎刃而解了。

考虑斯特林反演(这本质上是一个容斥,用二项式反演也可以推导):

\[S(k, j) = \sum_{i = 0}^j \frac{(-1)^{j - i}}{(j - i)!} \cdot \frac{i^k}{i!}\]

这个东西很显然是一个卷积……而且模数还很友好(UOJ模数),用NTT求出一行的第二类斯特林数即可。

代码:

/**************************************************************
    Problem: 5093
    User: danihao123
    Language: C++
    Result: Accepted
    Time:22632 ms
    Memory:25824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 998244353LL;
const ll bs = 3LL;
inline ll pow_mod(const ll &a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
inline ll inv(const ll &x) {
  return pow_mod(x, ha - 2LL);
}
 
inline int flip(const int &bi, const int &x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans |= (1 << (bi - i - 1));
    }
  }
  return ans;
}
inline void ntt(ll *A, const int &bi, const int &len, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi = pow_mod(bs, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi = inv(xi);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        A[j] = (x + (w * y) % ha) % ha;
        A[j + L] = (x - (w * y) % ha + ha) % ha;
        w = (w * xi) % ha;
      }
    }
  }
}
 
const int maxn = 800005;
ll A[maxn], B[maxn];
ll fac[maxn], down[maxn];
int main() {
  ll n; int k; scanf("%lld%d", &n, &k);
  if(n == 1) {
    puts("0"); return 0;
  }
  int len = 1, bi = 0;
  while(len <= (2 * k)) {
    len <<= 1; bi ++;
  }
  fac[0] = 1LL;
  for(int i = 1; i <= k; i ++) {
    fac[i] = (fac[i - 1] * (ll(i))) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    A[i] = (inv(fac[i]) * pow_mod(ha - 1LL, i)) % ha;
  }
  for(int i = 0; i <= k; i ++) {
    B[i] = inv(fac[i]);
    B[i] = (B[i] * pow_mod(i, k)) % ha;
  }
  ntt(A, bi, len); ntt(B, bi, len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * B[i]) % ha;
  }
  ntt(A, bi, len, true);
  ll inv_l = inv(len);
  for(int i = 0; i < len; i ++) {
    A[i] = (A[i] * inv_l) % ha;
  }
#ifdef LOCAL
  for(int i = 0; i <= k; i ++) {
    printf("%lld ", A[i]);
  }
  puts("");
#endif
  down[0] = 1LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    down[i] = (down[i - 1] * (n - (ll(i)))) % ha;
  }
  ll ans = 0LL;
  for(int i = 1; i <= std::min(ll(k), n - 1LL); i ++) {
    ll delta = (A[i] * down[i]) % ha;
    delta = (delta * pow_mod(2, n - 1LL - (ll(i)))) % ha;
    ans = (ans + delta) % ha;
  }
  ans = (ans * pow_mod(2LL, (n - 1LL) * (n - 2LL) / 2LL)) % ha;
  ans = (ans * n) % ha;
  printf("%lld\n", ans);
  return 0;
}

[HDU 5780]gcd

有个很好康的结论:

\[\gcd(x^a - 1, x^b - 1) = x^{\gcd(a, b)} - 1\]

然后尝试去用常见套路(枚举gcd)化简柿子,得到:

\[\sum_{k = 1}^n (x^k - 1)\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\]

推到这里了,看到那个\(\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\)可能很多同学准备直接上莫比乌斯函数了……其实并不需要,其实那个柿子就是:

\[2\sum_{i = 1}^{\lfloor \tfrac{n}{k}\rfloor} \varphi (i) - 1\]

这个意义还是很显然的……更好的一点是这个柿子可以预处理出来,然后整除分块直接搞一波即可。

代码:

#include <cstdio>
typedef long long ll;
const ll ha = 1000000007LL;
const int maxn = 1000005;
const int N = 1000000;
ll phi[maxn], phi_S[maxn];
void sieve() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  phi[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[cnt ++] = i;
      phi[i] = i - 1;
    }
    int v;
    for(int j = 0; j < cnt && (v = i * prm[j]) <= N; j ++) {
      vis[v] = true;
      if(i % prm[j] == 0) {
        phi[v] = (phi[i] * (ll(prm[j]))) % ha;
        break;
      } else {
        phi[v] = (phi[i] * phi[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = (phi_S[i - 1] + phi[i]) % ha;
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = ((2LL * phi_S[i]) % ha - 1LL + ha) % ha;
  }
}

ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll pre_sum(ll x, ll r) {
  ll p = pow_mod(x, r);
  p = (p - 1LL + ha) % ha;
  p = (p * inv(x - 1LL)) % ha;
  return p;
}
ll seg_sum(ll x, int a, int b) {
  if(x == 1LL) return 0;
  ll len = b - a + 1;
  ll ret = (pre_sum(x, b + 1) - pre_sum(x, a) + ha) % ha;
  ret = (ret - len + ha) % ha;
  return ret;
}
ll calc(ll x, int n) {
  ll ans = 0;
  for(int i = 1; i <= n;) {
    int v = n / i;
    int nx = n / v;
    ll delta = (seg_sum(x, i, nx) * phi_S[v]) % ha;
    ans = (ans + delta) % ha;
    i = nx + 1;
  }
  return ans;
}

int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    int x, n; scanf("%d%d", &x, &n);
    printf("%lld\n", calc(x, n));
  }
  return 0;
}