[SZKOpuł ben][AMPPZ2014]Petrol

aji波兰题!(迫真)

啊波兰题真好康(一转)

考虑怎么去除非加油站的影响……对于每两个加油站,取他们的最短路,然后建出来一个图,这个图的MST上的路径的走法就事最优走法。

但这样显然会凉……因为\(s\)肥肠巨大,会T。然后我们考虑多源最短路,并且给每个点标记到它最近的加油站(称为来源)。那么考虑两条加油站间的路径,上面一定有一条边满足边两个端点不一样(证明考虑……如果所有边两边端点的来源都一样,那么所有边的来源会同时事那两个加油站)。

然后一个小问题事,如果一个点有多个来源,只考虑一个会出事吗?这个事不会的。比如说有三个加油站\(a\)、\(b\)、\(c\),如果说三者到一个点的最短路都一样,那么我们考虑只取\(a\)。如果\(b\)和\(c\)本来能连一条边,但现在因为这个连不了了,那他们还是能同时各和\(a\)连一条长度和原来的那条边长度一样的边,所以事实上没有什么笋丝。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 200005, maxm = 400005;
int first[maxn];
int next[maxm], to[maxm], dist[maxm];
bool dir[maxm];
void add_edge(int u, int v, int w, bool d = true) {
  static int cnt = 0;
  cnt ++; next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = w; dir[cnt] = d;
}
void ins_edge(int u, int v, int w) {
  add_edge(u, v, w); add_edge(v, u, w, false);
}

using ll = long long;
using pii = std::pair<ll, int>;
int n; std::vector<int> V;
ll d[maxn]; int src[maxn];
bool vis[maxn];
void dij() {
  memset(d, 0x1f, sizeof(d));
  std::priority_queue<pii, std::vector<pii>, std::greater<pii> > Q;
  for(auto p : V) {
    d[p] = 0; src[p] = p;
    Q.push(std::make_pair(0LL, p));
  }
  while(!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if(vis[u]) continue;
    vis[u] = true;
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(d[u] + (ll(dist[i])) < d[v]) {
        d[v] = d[u] + (ll(dist[i]));
        src[v] = src[u];
        Q.push(std::make_pair(d[v], v));
      }
    }
  }
}

int p[maxn], rk[maxn];
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return (p[x] = get_fa(p[x]));
  }
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  x = get_fa(x); y = get_fa(y);
  if(x != y) link_set(x, y);
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
void init_set() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i;
  }
}

struct Edge {
  int u, v; ll w;
  Edge(int a = 0, int b = 0, ll c = 0) {
    u = a; v = b; w = c;
  }
  bool operator <(const Edge &res) const {
    return w < res.w;
  }
};
int m; Edge E[maxm];
int ecnt;
void process() {
  dij(); ecnt = 0;
  for(int i = 1; i <= n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(dir[j] && src[i] != src[v]) {
        E[++ ecnt] = Edge(src[i], src[v], (ll(dist[j])) + d[i] + d[v]);
      }
    }
  }
  std::sort(E + 1, E + 1 + ecnt);
}
bool ans[maxm];
void solve() {
  int q; scanf("%d", &q);
  init_set(); int cur = 0;
  std::vector<std::pair<Edge, int> > Q;
  for(int i = 1; i <= q; i ++) {
    int u, v; ll w; scanf("%d%d%lld", &u, &v, &w);
    Q.push_back(std::make_pair(Edge(u, v, w), i));
  }
  std::sort(Q.begin(), Q.end());
  for(auto x : Q) {
    Edge e = x.first;
    while(cur < ecnt && E[cur + 1].w <= e.w) {
      cur ++;
      merge_set(E[cur].u, E[cur].v);
    }
    ans[x.second] = is_same(e.u, e.v);
  }
  for(int i = 1; i <= q; i ++) {
    if(ans[i]) {
      puts("TAK");
    } else {
      puts("NIE");
    }
  }
}

int main() {
  int s; scanf("%d%d%d", &n, &s, &m);
  for(int i = 1; i <= s; i ++) {
    int x; scanf("%d", &x);
    V.push_back(x);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process(); solve();
  return 0;
}

[SZKOpuł sol][POI2009]Elephants

aji波兰题!(直球)

这个题显然就是对那个排列乘上一个置换,然后置换的每一个循环事独立的,于是分别考虑每一个循环。

然后每一个循环有一种显然的构造方法就是从一个点开始,逆着边不停的交换两个点。这样的话有一个点会对答案做\(s - 1\)次贡献(\(s\)为循环大小),其他点都会只做一次循环。显然那个点选权值最小的点事坠吼的。

还有一种构造就是把全局最小值和循环最小值换一下,然后用上面的手段构造,最后再把全局最小值和循环最小值换回来。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 1000005;
int next[maxn];

using ll = long long;
ll m[maxn];
int A[maxn], B[maxn], ma[maxn];
bool vis[maxn];

int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%lld", &m[i]);
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]); ma[A[i]] = i;
  }
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &B[i]);
    next[ma[B[i]]] = i;
  }
  ll ans = 0LL; ll tv = *std::min_element(m + 1, m + 1 + n);
  for(int i = 1; i <= n; i ++) {
    if(next[i] != i && !vis[i]) {
      int p = i; ll sumv = 0LL, minv = 0x7fffffffLL;
      ll cnt = 0;
      do {
        vis[p] = true; cnt ++;
        sumv += m[A[p]]; minv = std::min(minv, m[A[p]]);
        p = next[p];
      } while(p != i);
      ll delta = sumv + std::min(minv * (cnt - 2LL), minv + tv * (cnt + 1LL));
      ans += delta;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

[LibreOJ 2182][SDOI2015]寻宝游戏

很多人说事动态虚树……其实也不算是吧,虽然这个东西用力虚树的思路惹。

第一个想到的思路……就事动态的维护虚树,然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序(严格来说事欧拉序)排序,所以我们大致可以认为,虚树上做欧拉回路的本质就事按照DFS序扫描,换言之就事DFS一遍,然后进入和回溯事都把边记录到答案里,这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和(首尾也要额外算一遍)。

然后这样一来,我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA,然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点,问题就简单了许多……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
  G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
  add_edge(u, v, w); add_edge(v, u, w);
}

int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
  anc[x][0] = fa; dfn[x] = ++ dcnt;
  for(auto &e : G[x]) {
    int v = e.first; ll w = e.second;
    if(v != fa) {
      dep[v] = dep[x] + 1;
      dis[v] = dis[x] + w;
      dfs(v, x);
    }
  }
}
int n;
void process() {
  memset(anc, -1, sizeof(anc)); dfs(1);
  for(int j = 1; (1 << j) < n; j ++) {
    for(int i = 1; i <= n; i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
      }
    }
  }
}
int lca(int u, int v) {
  if(dep[u] < dep[v]) std::swap(u, v);
  for(int j = 16; j >= 0; j --) {
    int a = anc[u][j];
    if(a != -1 && dep[a] >= dep[v]) {
      u = a;
    }
  }
  if(u == v) return u;
  for(int j = 16; j >= 0; j --) {
    int a1 = anc[u][j], a2 = anc[v][j];
    if(a1 != -1 && a2 != -1 && a1 != a2) {
      u = a1; v = a2;
    }
  }
  return anc[u][0];
}
ll calc_dist(int u, int v) {
  return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}

// template <typename T>
struct Comp {
  bool operator ()(const int &a, const int &b) const {
    return dfn[a] < dfn[b];
  }
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.begin()) {
    auto pre = -- suc; ++ suc;
    now += calc_dist(*pre, p);
    if(suc != S.end()) {
      now -= calc_dist(*pre, *suc);
    }
  }
  if(suc != S.end()) {
    now += calc_dist(*suc, p);
  }
  S.insert(p);
}
void del(int p) {
  auto suc = S.upper_bound(p);
  if(suc != S.end()) {
    now -= calc_dist(*suc, p);
  }
  if((*S.begin()) != p) {
    -- suc; -- suc;
    int prev = *suc;
    now -= calc_dist(prev, p);
    ++ suc; ++ suc;
    if(suc != S.end()) {
      now += calc_dist(prev, *suc);
    }
  }
  S.erase(p);
}
ll query() {
  if(S.size() <= 1) return 0LL;
  ll ret = now;
  auto las = S.end(); -- las;
  ret += calc_dist(*S.begin(), *las);
  return ret;
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    ins_edge(u, v, w);
  }
  process();
  while(m --) {
    int x; scanf("%d", &x);
    if(sta[x]) {
      del(x);
    } else {
      add(x);
    }
    sta[x] = !sta[x];
    printf("%lld\n", query());
  }
  return 0;
}

[UOJ 333][NOIP2017]宝藏

啊啊啊爽到力,,,

过去太池沼力,没有做出来惹。现在看了看可能比较简单罢……

定义状态\(d_{i, S}\)表示当前已经被覆盖的点集为\(S\),然后当前的生成树已经考虑到了第\(i\)层,转移看起来很毒……

所以预处理一个点集到另一个点集只走一步边来扩展,最优解是多少,然后转移就方便力……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
const int maxn = 12;
int G[15][15];
const int INF = 0x3f3f3f3f;
void add_edge(int u, int v, int d) {
  G[u][v] = std::min(G[u][v], d);
  G[v][u] = std::min(G[v][u], d);
}

int n;
int g1[(1 << maxn)][15], g2[(1 << maxn)][(1 << maxn)];
void process() {
  for(int s = 1; s < (1 << n); s ++) {
    for(int i = 1; i <= n; i ++) {
      g1[s][i] = INF;
      for(int j = 0; j < n; j ++) {
        if((1 << j) & s) {
          g1[s][i] = std::min(g1[s][i], G[j + 1][i]);
        }
      }
    }
  }
  for(int s = 1; s < (1 << n); s ++) {
    int k = (1 << n) - 1; k = k & (~s);
    for(int t = k; t > 0; t = (t - 1) & k) {
      g2[s][t] = 0;
      for(int i = 1; i <= n; i ++) {
        if((1 << (i - 1)) & t) {
          if(g1[s][i] == INF) {
            g2[s][t] = INF; break;
          }
          g2[s][t] += g1[s][i];
        }
      }
    }
  }
}

using ll = long long;
ll d[14][(1 << maxn)];
ll dp() {
  for(int s = 0; s < (1 << n); s ++) {
    d[1][s] = INF;
  }
  for(int i = 0; i < n; i ++) {
    d[1][(1 << i)] = 0;
  }
  for(int i = 2; i <= n; i ++) {
    for(int s = 1; s < (1 << n); s ++) {
      d[i][s] = INF;
      for(int t = (s - 1) & s; t != 0; t = (t - 1) & s) {
        d[i][s] = std::min(d[i][s], d[i - 1][t] + (ll(i - 1)) * g2[t][s ^ t]);
      }
    }
  }
  ll ans = INF;
  for(int i = 1; i <= n; i ++) {
    ans = std::min(ans, d[i][(1 << n) - 1]);
  }
  return ans;
}

int main() {
  memset(G, 0x3f, sizeof(G));
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v, w; scanf("%d%d%d", &u, &v, &w);
    add_edge(u, v, w);
  }
  process(); printf("%lld\n", dp());
  return 0;
}

[SZKOpuł raj][POI2014]Rally

我从未见过有像SZKOpuł这样迷的OJ……

很好玩的一道题qwq

首先多源最短路太不好处理,我们搞一个超级源一个超级汇,分别和所有点连边。然后转成求超级源和超级汇的最长路。

我们不妨将这张图拓扑排序。然后我们思考对于拓扑排序得到的序列\(A\),如果我们删除\(A_i\)的话,哪些路径不会收到影响?如果说有一个路径有一条边\((u, v)\),满足\(u\)和\(v\)在拓扑排序中分别位于\(A_i\)的两侧,那么这条路径不会受到影响。

反过来考虑每条边\((u, v)\),过这条边最优的路径一定是从源到\(u\)的最长路加上1再加上从\(v\)到汇的最长路(用两遍DP就能搞出来),他能影响的点在拓扑排序中显然事一段区间。

然后问题变成区间取max了,然后不需要在线,所以随便做了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int maxn = 500005;
const int maxm = 750005;
std::vector<int> G[maxn], RG[maxn];
int inv[maxn], outv[maxn];
void add_edge(int u, int v) {
  inv[v] ++; outv[u] ++;
  G[u].push_back(v);
  RG[v].push_back(u);
}

int T[maxn], ma[maxn];
void toposort() {
  std::queue<int> Q; Q.push(0);
  int num = 0;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    T[++ num] = u; ma[u] = num;
    for(auto v : G[u]) {
      inv[v] --;
      if(inv[v] == 0) Q.push(v);
    }
  }
}

int n, m;
int f[maxn], g[maxn];
int dp1(int x) {
  if(x == n + 1) return 0;
  if(f[x] != -1) return f[x];
  f[x] = 0;
  for(auto v : G[x]) {
    f[x] = std::max(f[x], dp1(v) + 1);
  }
  return f[x];
}
int dp2(int x) {
  if(x == 0) return 0;
  if(g[x] != -1) return g[x];
  g[x] = 0;
  for(auto v : RG[x]) {
    g[x] = std::max(g[x], dp2(v) + 1);
  }
  return g[x];
}

struct Interval {
  int l, r, v;
  bool operator <(const Interval &res) const {
    return v < res.v;
  }
};
int E[maxm][2]; std::vector<Interval> I;
void pro_I() {
  memset(f, -1, sizeof(f));
  memset(g, -1, sizeof(g));
  for(int u = 0; u <= n + 1; u ++) {
    for(auto v : G[u]) {
      int l = ma[u], r = ma[v];
      l ++; r --;
      if(l <= r) {
        Interval seg;
        seg.l = l; seg.r = r;
        seg.v = dp2(u) + dp1(v) + 1;
        I.push_back(seg);
      }
    }
  }
  std::sort(I.begin(), I.end());
}

const int maxno = maxn << 2;
int setv[maxno];
void pushdown(int o) {
  if(setv[o] != -1) {
    int lc = o << 1, rc = o << 1 | 1;
    setv[lc] = setv[o]; setv[rc] = setv[o];
    setv[o] = -1;
  }
}
int ql, qr, v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    setv[o] = v;
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
  }
}
int ans[maxn];
void dfs(int o, int L, int R) {
  if(L == R) {
    ans[L] = setv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    dfs(o << 1, L, M);
    dfs(o << 1 | 1, M + 1, R);
  }
}

int main() {
  memset(setv, -1, sizeof(setv));
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    add_edge(E[i][0], E[i][1]);
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(0, i);
    }
  }
  for(int i = 1; i <= n; i ++) {
    if(true) {
      add_edge(i, n + 1);
    }
  }
  toposort(); pro_I();
  for(auto &seg : I) {
    ql = seg.l, qr = seg.r, v = seg.v;
#ifdef LOCAL
    printf("(%d, %d) -> %d\n", ql, qr, v);
#endif
    modify(1, 1, n + 2);
  }
  dfs(1, 1, n + 2);
  int cho = 1, ret = 0x7fffffff;
  for(int i = 2; i <= n + 1; i ++) {
    if(ans[i] < ret) {
      cho = T[i]; ret = ans[i];
    }
  }
  printf("%d %d\n", cho, ret - 2);
  return 0;
}

[LibreOJ 6436][PKUSC2018]神仙的游戏

考场上写炸了FFT的zzs事野蛮人(确信)

兄啊这题怎么还卡常啊!

不妨设\(n = |S|\)。那么如果串有一个长度为$i$的border,就意味着串有一个长度为\(n - i\)的循环节。

那么考虑有两个非?的位置\(i\)和\(j\)(不妨设\(i < j\)),且\(S_i\neq S_j\)。那么我们设\(l = j - i\),则\(l\)的约数都不能成为循环节的长度,否则会出现矛盾(一个位置又要是0又要是1)。

那么考虑对于所有可能的\(l\)判定是否存在这种不合法的\(i\)与\(j\)。我们利用编辑距离函数:

\[f_l = \sum_{i} A_i A_{i + l}(A_i - A_{i + l})^2\]

这里\(A_i\)相当于\(S_i\)的一个重编码,\(S_i\)为?时应当为0,其他情况一种为1一种为2。这个函数不方便我们卷积,所以我们考虑把\(A\)翻转一下(新的序列称为\(B\)):

\[
\begin{aligned}
f_l &= \sum_{i} B_{n - i - 1} A_{i + l}(B_{n - i - 1} A_{i + l})^2\\
&= \sum_{i} B_{n - i - 1}^3 A_{i + l} - 2B_{n - i - 1}^2 A_{i + l}^2 + B_{n - i - 1}A_{i + l}^3
\end{aligned}\]

然后问题变成了三个卷积。FFT一下就行了(请注意IDFT只需要一次……否则会被卡常)。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <vector>
using R = double;
struct C {
  R x, y;
  C(R xx = 0.00, R yy = 0.00) {
    x = xx; y = yy;
  }
  R real() {
    return x;
  }
};
C operator +(const C &a, const C &b) {
  return C(a.x + b.x, a.y + b.y);
}
C operator -(const C &a, const C &b) {
  return C(a.x - b.x, a.y - b.y);
}
C operator *(const C &a, const C &b) {
  return C(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}

using ll = long long;
constexpr R pi = acos(-1);
int flip(int bi, int x) {
  int ret = 0;
  for(int i = 0; i < bi; i ++) {
    if(x & (1 << i)) {
      ret += (1 << (bi - i - 1));
    }
  }
  return ret;
}
void FFT(C *A, int bi, R flag = 1.00) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(i < v) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    R rd = pi / (R(L));
    C xi_n(cos(rd), sin(flag * rd));
    for(int j = 0; j < n; j += (L << 1)) {
      C xi(1.00, 0.00);
      for(int i = j; i < j + L; i ++) {
        C x = A[i], y = A[i + L];
        A[i] = x + xi * y;
        A[i + L] = x - xi * y;
        xi = xi * xi_n;
      }
    }
  }
}

const int maxn = 500005;
R tot[maxn];
C T[maxn << 2], TT[maxn << 2], D[maxn << 2];

char S[maxn];
inline int conv(char c) {
  if(c == '1') return 2;
  if(c == '0') return 1;
  return 0;
}
int A[maxn], B[maxn];
bool boom[maxn];
int main() {
  scanf("%s", S); int n = strlen(S);
  for(int i = 0; i < n; i ++) {
    A[i] = B[n - 1 - i] = conv(S[i]);
  }
  
  int len = 1, bi = 0;
  while(len < (2 * n)) {
    len <<= 1; bi ++;
  }
  
  C z(0.00, 0.00);
  // std::fill(T, T + len, z);
  // std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i] * A[i]; TT[i] = B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i] * A[i]; TT[i] = B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + C(-2.00, 0.00) * (T[i] * TT[i]);
  }
  
  std::fill(T, T + len, z);
  std::fill(TT, TT + len, z);
  for(int i = 0; i < n; i ++) {
    T[i] = A[i]; TT[i] = B[i] * B[i] * B[i];
  }
  FFT(T, bi); FFT(TT, bi);
  for(int i = 0; i < len; i ++) {
    D[i] = D[i] + (T[i] * TT[i]);
  }
  FFT(D, bi, -1.00);
  
  for(int i = 1; i < n; i ++) {
    if(fabs(D[n - 1 + i].real() / (R(len))) > 0.99) {
      boom[i] = true;
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = i * 2; j <= n; j += i) {
      boom[i] = (boom[i] || boom[j]);
    }
  }
  ll ret = 0LL;
  for(int i = 1; i <= n; i ++) {
    if(!boom[n - i]) {
      ret ^= (ll(i)) * (ll(i));
    }
  }
  printf("%lld\n", ret);
  return 0;
}

[BZOJ 5358][Lydsy1805月赛]口算训练

后几页有我会做的题……很好,我很安详,,,

考虑将所有数质因数分解。那么询问\([l, r]\)中所有数的积是否是\(d\)的倍数的本质就是对于\(d\)的每一类质因子,询问区间中该类质因子的指数之和是否不小于\(d\)中的。

考虑到数的范围都很小(不超过100000),我们可以先线性筛预处理,这样一次分解质因数的复杂度就降为了\(O(\log n)\)。至于维护区间每类质因子的指数和这种事……就用主席树处理吧。

代码:

/**************************************************************
    Problem: 5358
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2804 ms
    Memory:68408 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
const int maxn = 100005;
int minp[maxn], mint[maxn], minh[maxn];
int prm[maxn], pcnt;
bool vis[maxn];
void sieve() {
  const int N = 100000;
  vis[1] = true; pcnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[++ pcnt] = i;
      minp[i] = pcnt; mint[i] = 1;
      minh[i] = i;
    }
    for(int j = 1; j <= pcnt && i * prm[j] <= N; j ++) {
      int v = i * prm[j];
      vis[v] = true; minp[v] = j;
      if(i % prm[j] == 0) {
        mint[v] = mint[i] + 1; minh[v] = minh[i] * prm[j];
        break;
      } else {
        mint[v] = 1; minh[v] = prm[j];
      }
    }
  }
}
 
const int bufsiz = 64 * 1024 * 1024;
char buf[bufsiz]; char *cur;
void init_buf() {
  cur = buf;
}
void *alloc(size_t size) {
  if(cur + size - buf > bufsiz) {
    return malloc(size);
  } else {
    char *ret = cur; cur += size;
    return ret;
  }
}
 
struct Node {
  int v; Node *lc, *rc;
};
Node *build_tree(int L, int R) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = 0; 
  if(L == R) {
    ret -> lc = ret -> rc = NULL;
  } else {
    int M = (L + R) / 2;
    ret -> lc = build_tree(L, M);
    ret -> rc = build_tree(M + 1, R);
  }
  return ret;
}
Node *add_p(Node *o, int L, int R, int p, int v) {
  Node *ret = (Node*)alloc(sizeof(Node));
  ret -> v = o -> v;
  ret -> lc = o -> lc; ret -> rc = o -> rc;
  if(L == R) {
    ret -> v += v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      ret -> lc = add_p(ret -> lc, L, M, p, v);
    } else {
      ret -> rc = add_p(ret -> rc, M + 1, R, p, v);
    }
  }
  return ret;
}
int query(Node *o, int L, int R, int p) {
  if(L == R) {
    return o -> v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      return query(o -> lc, L, M, p);
    } else {
      return query(o -> rc, M + 1, R, p);
    }
  }
}
 
Node *rt[maxn];
void solve() {
  init_buf();
  int n, m; scanf("%d%d", &n, &m);
  rt[0] = build_tree(1, pcnt);
  for(int i = 1; i <= n; i ++) {
    rt[i] = rt[i - 1];
    int x; scanf("%d", &x);
    while(x > 1) {
      int p = minp[x], t = mint[x];
      rt[i] = add_p(rt[i], 1, pcnt, p, t);
      x /= minh[x];
    }
  }
  while(m --) {
    int l, r, d; scanf("%d%d%d", &l, &r, &d);
    bool ok = true;
    while(d > 1) {
      int p = minp[d], t = mint[d];
      int st = query(rt[r], 1, pcnt, p) - query(rt[l - 1], 1, pcnt, p);
      if(st < t) {
        ok = false; break;
      }
      d /= minh[d];
    }
    if(ok) {
      puts("Yes");
    } else {
      puts("No");
    }
  }
}
 
int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    solve();
  }
  return 0;
}

[BZOJ 4403]序列统计

老早做的题……

一看单调不降就想去用差分……但差分不好推(比下面的颓法要多一步……)。其实我们发现,只要给\([L, R]\)里每种整数分配出现次数,原序列就可以唯一确定了。

因此我们把\([L, R]\)中每个整数的出现次数当做一个变量,他们加起来应该等于一个\([1, n]\)中的整数。用隔板法很容易退出来式子是(令\(l = R - L + 1\)):

\[\sum_{i = 1}^n \binom{i + l - 1}{l - 1}\]

看起来玩不动了……但是我们给式子加上一个\(\binom{l}{l}\)(其实就是1),然后我们会发现式子可以用杨辉三角的递推式合并成一个组合数,即\(\binom{n + l}{l}\)。然后求这个组合数还需要Lucas定理……

代码:

/**************************************************************
    Problem: 4403
    User: danihao123
    Language: C++
    Result: Accepted
    Time:908 ms
    Memory:16448 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
typedef long long ll;
const ll ha = 1000003LL;
const int maxn = 1000003;
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 f[maxn], g[maxn];
void process() {
  f[0] = 1LL;
  for(int i = 1; i < maxn; i ++) {
    f[i] = (f[i - 1] * (ll(i))) % ha;
  }
  g[maxn - 1] = pow_mod(f[maxn - 1], ha - 2LL);
  for(int i = maxn - 2; i >= 0; i --) {
    g[i] = (g[i + 1] * (ll(i + 1))) % ha;
  }
}
 
ll C(int a, int b) {
  if(a < b) return 0LL;
  return (((f[a] * g[b]) % ha) * g[a - b]) % ha;
}
ll calc(int a, int b) {
  if(a < b) return 0LL;
  if(b == 0) return 1LL;
  if(a < ha && b < ha) {
    return C(a, b);
  } else {
    int as = a % ha, bs = b % ha;
    return (C(as, bs) * calc(a / ha, b / ha)) % ha;
  }
}
 
int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int n, l, r; scanf("%d%d%d", &n, &l, &r);
    int len = r - l + 1;
    printf("%lld\n", (calc(n + len, len) - 1LL + ha) % ha);
  }
  return 0;
}

[Tsinsen A1300]JZPKIL

卡常的题见过,这么变态的卡常题……可能出题人过于文明,,,下面是卡常记录的一部分:

卡常记录(三分之一)

下面开始颓式子:

继续阅读

[BZOJ 3601]一个人的数论

本来想做JZPKIL的……但卡常太恶心了

上来先颓式子:

\[
\DeclareMathOperator{\id}{id}
\begin{aligned}
f_d(n) &= \sum_{i = 1}^n [(i, n) = 1]i^d\\
&= \sum_{i = 1}^n i^d\sum_{k | n, k | i}\mu(k)\\
&= \sum_{k | n}\mu(k)\sum_{i = 1}^{\frac{n}{k}} (ik)^d\\
&= \sum_{k | n}\mu(k)k^d h_d(\frac{n}{d})\\
&= ((\mu\cdot\id^k)\ast h_d)
\end{aligned}
\]

其中\(h_d\)表示指数为\(d\)时的等幂求和函数。然后我们可能会想,如果这个函数是积性函数,那么我们可以对质因数分解的每一种质因数都求一遍答案,而由于\(\mu\)的存在(对于质数的幂\(p^k\)的因数,只有\(1\)和\(p\)的莫比乌斯函数值不为0),所以需要处理的情况只有两种。

不过很可惜,\(h_d\)显然不是积性函数,所以最后的整个卷积也不是积性函数。但是我们注意到\(h_d\)事一个\(d + 1\)次多项式,所以我们可以把多项式每一项都当成单独的函数,然后每个单独函数卷出来都是一个积性函数。至于求多项式每一项的系数,用伯努利数即可。

代码:

/**************************************************************
    Problem: 3601
    User: danihao123
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:948 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
typedef long long ll;
ll ha = 1000000007LL;
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);
}
 
const int maxn = 105;
ll C[maxn][maxn];
void process_C() {
  C[0][0] = 1LL;
  for(int i = 1; i < maxn; i ++) {
    C[i][0] = C[i][i] = 1LL;
    for(int j = 1; j < i; j ++) {
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % ha;
    }
  }
}
ll B[maxn];
void process_B() {
  B[0] = 1LL;
  for(int i = 1; i <= 101; i ++) {
    B[i] = 1LL;
    for(int j = 0; j < i; j ++) {
      ll d = (((C[i][j] * B[j]) % ha) * inv(i - j + 1)) % ha;
      B[i] = (B[i] - d + ha) % ha;
    }
  }
}
 
const int maxw = 1005;
typedef std::pair<ll, ll> pii;
pii P[maxw]; ll dv[maxw][3];
int d, w;
void process_dv() {
  for(int i = 1; i <= w; i ++) {
    ll p = P[i].first, t = P[i].second;
    p %= ha;
    dv[i][0] = pow_mod(p, t);
    dv[i][1] = pow_mod(p, t - 1LL);
    dv[i][2] = pow_mod(p, d);
  }
}
ll calc(ll k, int z) {
  ll ans = k;
  for(int i = 1; i <= w; i ++) {
    ll p = P[i].first, t = P[i].second;
    p %= ha;
    ll f1 = pow_mod(dv[i][0], z), f2 = pow_mod(dv[i][1], z);
    ll v1 = (f1 - (dv[i][2] * f2) % ha + ha) % ha;
    ans = (ans * v1) % ha;
  }
#ifdef LOCAL
  printf("Case (%lld, %d) : %lld\n", k, z, ans);
#endif
  return ans;
}
 
int main() {
  process_C(); process_B();
  scanf("%d%d", &d, &w);
  for(int i = 1; i <= w; i ++) {
    scanf("%lld%lld", &P[i].first, &P[i].second);
  }
  process_dv();
  ll ans = 0LL;
  for(int i = 0; i <= d; i ++) {
    ll g = calc((((C[d + 1][i] * B[i]) % ha) * inv(d + 1)) % ha, d + 1 - i);
    ans = (ans + g) % ha;
  }
  printf("%lld\n", ans);
  return 0;
}