ZOJ Monthly, January 2015
The 12th Zhejiang Provincial Collegiate Programming Contest

The 15th Zhejiang University Programming Contest

zimpha posted @ Mon, 13 Apr 2015 20:57:26 +0800 in ZOJ , 1181 readers
The 15th Zhejiang University Programming Contest - Onsite
A Find the Spy 48.59% (104/214)
B Valid Pattern Lock 18.59% (66/355)
C Intersection 15.55% (7/45)
D Paths on the Tree 0.00% (0/15)
E Quiz for EXO-L 18.60% (8/43)
F Superbot 26.12% (29/111)
G Cylinder Candy 57.14% (36/63)
H Earthstone: Easy Version 53.92% (103/191)
I GCD Expectation 7.14% (1/14)

上面的是现场过题的情况.

The 15th Zhejiang University Programming Contest - Onilne
A Find the Spy 63.48% (433/682)
B Valid Pattern Lock 20.06% (197/982)
C Intersection 32.60% (15/46)
D Paths on the Tree 0.00% (0/5)
E Quiz for EXO-L 2.99% (7/234)
F Superbot 28.09% (93/331)
G Cylinder Candy 32.64% (63/193)
H Earthstone: Easy Version 45.75% (383/837)
I GCD Expectation 26.47% (27/102)

这个是同步赛过题的情况. D题没有人过, I题挺old的, 同步赛过了一大片人, 现场却没几个人过, 其他题目都还好.


Problem A Find the Spy

给出$n$个数, 只有一个是不同的, 找出那个数.

数据规模: $3 \le n \le 100$

应该没人不会做这题吧.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int n; scanf("%d", &n);
    vector<int> A(n);
    for (int i = 0; i < n; ++ i) scanf("%d", &A[i]);
    sort(A.begin(), A.end());
    if (A[0] == A[1]) printf("%d\n", A.back());
    else printf("%d\n", A[0]);
  }
  return 0;
}

Problem B Valid Pattern Lock

给出屏幕锁中$n$个点, 输出所有的pattern lock.

数据规模: $1 \le n \le 9$

应该没人不会做这题吧.

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
const int cor[][2] = {
  {0, 0}, {0, 1}, {0, 2},
  {1, 0}, {1, 1}, {1, 2},
  {2, 0}, {2, 1}, {2, 2}
};

bool check(int a[], int n) {
  static bool vis[3][3];
  memset(vis, 0, sizeof(vis));
  int sx = cor[a[0]][0], sy = cor[a[0]][1];
  vis[sx][sy] = true;
  for (int i = 1; i < n; ++ i) {
    int ex = cor[a[i]][0], ey = cor[a[i]][1];
    int dx = ex - sx, dy = ey - sy, g = __gcd(abs(dx), abs(dy));
    dx /= g; dy /= g;
    while (sx != ex || sy != ey) {
      sx += dx; sy += dy;
      if ((sx != ex || sy != ey) && !vis[sx][sy]) return false;
      vis[sx][sy] = true;
    }
  }
  return true;
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int n, a[10];
    scanf("%d", &n);
    assert(3 <= n && n <= 9);
    for (int i = 0; i < n; ++ i) {
      scanf("%d", a + i); -- a[i];
      assert(0 <= a[i] && a[i] <= 8);
    }
    sort(a, a + n);
    for (int i = 1; i < n; ++ i) assert(a[i] != a[i - 1]);
    vector<VI> ret;
    do {
      if (check(a, n)) ret.push_back(VI(a, a + n));
    } while (next_permutation(a, a + n));
    printf("%d\n", (int)ret.size());
    for (auto &s : ret) {
      for (int i = 0; i < n; ++ i) {
        printf("%d%c", s[i] + 1, " \n"[i == n - 1]);
      }
    }
  }
  return 0;
}

Problem C Intersection

给出$n$条线段, 每次可以选择两个点交换他们的坐标. 要求一个不超过$n+10$步的操作序列, 使得最终没有线段相交.

数据规模: $1 \le n \le 10^5$

我们只要确定了最终每个点的位置之后交换肯定最多需要$n$次. 然后题目有若干限制, 我们可以随便搞.

  • 直接按照$(x,y)$双关键字排序, 相邻两个点组成一条线段
  • 随便选一个点, 极角排序, 相邻两个点组成一条线段, 最后一个点和极角基准点组成一条线段
  • ......
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 200000 + 10;
struct Point {
  int x, y;
  Point() {}
  Point(int a, int b): x(a), y(b) {}
  bool operator < (const Point &rhs) const {
    return x < rhs.x || (x == rhs.x && y < rhs.y);
  }
  bool operator == (const Point &rhs) const {
    return x == rhs.x && y == rhs.y;
  }
  Point operator + (const Point &rhs) const {
    return Point(x + rhs.x, y + rhs.y);
  }
  Point operator - (const Point &rhs) const {
    return Point(x - rhs.x, y - rhs.y);
  }
  LL dot(const Point &rhs) const {
    return (LL)x * rhs.x + (LL)y * rhs.y;
  }
  LL det(const Point &rhs) const {
    return (LL)x * rhs.y - (LL)y * rhs.x;
  }
  LL sqrlen() const {
    return (LL)x * x + (LL)y * y;
  }
} P[MAXN], Q[MAXN];

map<Point, int> mp;
map<LL, vector<Point> > layer;
vector<PII> ret;
int op[MAXN], N;

void change(int a, int b) {
  ret.push_back(PII(a, b));
  swap(P[a], P[b]);
  mp[P[a]] = a; mp[P[b]] = b;
}

void solve() {
  ret.clear();
	sort(Q, Q + 2 * N);
  for (int i = 0; i < N * 2; i += 2) {
    Point &A = Q[i], &B = Q[i + 1];
    int a = mp[A], b = mp[B];
    if (op[a] == b) continue;
    change(op[a], b);
    a = mp[A], b = mp[B];
  }
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d", &N); mp.clear();
    for (int i = 0; i < 2 * N; ++ i) {
      scanf("%d%d", &P[i].x, &P[i].y);
			Q[i] = P[i]; mp[P[i]] = i;
    }
    for (int i = 0; i < N; ++ i) {
      int a, b; scanf("%d%d", &a, &b);
      -- a, -- b; op[a] = b; op[b] = a;
    }
		solve();
    printf("%d\n", (int)ret.size());
    for (auto &v : ret) {
      printf("%d %d\n", v.first + 1, v.second + 1);
    }
  }
  return 0;
}

Problem D Paths on the Tree

给出一棵$n$个节点的树, 问有多少路径对, 公共点不超过$k$个.

数据规模: $1 \le n, k \le 88888$

有两种方法, 树分治和启发式合并. 可以直接做也可以考虑补集. 下面考虑直接做的方法

树分治:

对于每个重心, 有三种情况:

  • 公共部分不经过重心
  • 公共部分很跨重心
  • 公共部分以重心开始

启发式合并:

对于每个根节点, 需要考虑两种情况

  • 公共部分跨过根
  • 公共部分以根节点开始

然后考虑清楚就好了, 具体讲起来实在麻烦, 还是去看代码吧.

公共节点数目是0或者1的时候, 直接搞不好算, 还是推荐利用补集的方法.

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
typedef pair<int, LL> PII;
const int MAXN = 100000 + 10;

struct Edge {
  int v, nx;
  Edge() {}
  Edge(int a, int b): v(a), nx(b) {}
} E[MAXN << 1];

int G[MAXN], sz[MAXN], dep[MAXN];
bool vis[MAXN];
LL sz2[MAXN];
int rt, mins, total;
int N, K;

LL sqr(LL x) {return x * x;}

struct BIT {
  LL u[MAXN]; int n;
  void init(int n) {
    this->n = n;
    for (int i = 0; i <= n; ++ i) u[i] = 0;
  }
  void add(int x, LL v) {
    for (; x <= n; x += ~x & x + 1) u[x] += v;
  }
  LL get(int x) {
    LL r = 0; x = min(x, n);
    for (; x >= 0; x -= ~x & x + 1) r += u[x];
    return r;
  }
} zpt;

void getSize(int u, int f = -1) {
  sz[u] = 1; sz2[u] = 0;
  int mx = 0; dep[u] = 0;
  for (int it = G[u]; ~it; it = E[it].nx) {
    int v = E[it].v; if (vis[v] || v == f) continue;
    getSize(v, u); sz[u] += sz[v];
    mx = max(mx, sz[v]); sz2[u] += sqr(sz[v]);
    dep[u] = max(dep[u], dep[v] + 1);
  }
  mx = max(mx, total - sz[u]);
  if (mx < mins) mins = mx, rt = u;
}

LL S[MAXN], ps1, ps2;
vector<PII> entry;

LL count(int u, int f, int d) {
  LL ret = 0, coef = sqr(sz[u]) - sz2[u];
  ret = coef * zpt.get(K - d - 1);
  entry.push_back(PII(d, coef));
  if (d + 1 <= K) ret += ps2 * coef;
  if (d >= 2) ret += ps1 * coef * (S[d - 1] - S[max(0, d - K)]) * 2;
  for (int it = G[u]; ~it; it = E[it].nx) {
    int v = E[it].v; if (vis[v] || v == f) continue;
    S[d] = S[d - 1] + sz[u] - sz[v];
    ret += count(v, u, d + 1);
  }
  return ret;
}

LL solve(int u, int tot) {
  LL ret = 0; mins = N * 2, total = tot;
  getSize(u); u = rt; vis[u] = true;
  getSize(u); zpt.init(dep[u]); S[0] = 0;
  for (int it = G[u]; ~it; it = E[it].nx) {
    int v = E[it].v; if (vis[v]) continue;
    ps1 = sz[u] - sz[v]; ps2 = sqr(ps1) - sz2[u] + sqr(sz[v]);
    entry.clear();
    ret += count(v, u, 1);
    for (auto &e : entry) zpt.add(e.first, e.second);
  }
  for (int it = G[u]; ~it; it = E[it].nx) {
    int v = E[it].v; if (vis[v]) continue;
    ret += solve(v, sz[v]);
  }
  return ret;
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d%d", &N, &K); int sz = 0;
    for (int i = 0; i < N; ++ i) G[i] = -1;
    for (int i = 1; i < N; ++ i) {
      int u, v; scanf("%d%d", &u, &v); -- u; -- v;
      E[sz] = Edge(v, G[u]); G[u] = sz ++;
      E[sz] = Edge(u, G[v]); G[v] = sz ++;
    }
    for (int i = 0; i < N; ++ i) vis[i] = false;
    LL ret = solve(0, N);
    K = N;
    for (int i = 0; i < N; ++ i) vis[i] = false;
    LL zero = sqr((LL)N * (N - 1) / 2 + N) - solve(0, N);
    ret += zero;
    printf("%llu\n", ret);
  }
  return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const int MAXN = 100000 + 10;
const int INF = ~0U>>1;
struct Node {
  Node *ch[2];
  int key, pri, sz;
  LL sum, val;
  void update() {
    sum = val + ch[0]->sum + ch[1]->sum;
    sz = ch[0]->sz + ch[1]->sz + 1;
  }
} pool[MAXN << 4], *null, *pt;

struct Treap {
  Node *rt;
  map<int, LL> mp;
  static Node* NewNode(int key, LL val) {
    pt->key = key; pt->val = pt->sum = val;
    pt->ch[0] = pt->ch[1] = null;
    pt->sz = 1; pt->pri = rand() - 1; 
    return pt ++;
  }
  int size() {return rt->sz;}
  void rot(Node* &o, int d) {
    Node *k = o->ch[d];
    o->ch[d] = k->ch[!d];
    k->ch[!d] = o;
    o->update(); k->update();
    o = k;
  }
  void ins(Node* &o, int key, LL val) {
    if (o == null) o = NewNode(key, val);
    else {
      if (key == o->key) {
        o->val += val;
        o->sum += val;
        return;
      }
      int d = (key > o->key);
      ins(o->ch[d], key, val);
      if (o->ch[d]->pri < o->pri) rot(o, d);
      else o->update();
    }
    o->update();
  }
  LL get(Node *o, int k) {
    int s = o->ch[0]->sz + 1;
    if (k == s) return o->val + o->ch[0]->sum;
    else if (k < s) return get(o->ch[0], k);
    else return o->val + o->ch[0]->sum + get(o->ch[1], k - s);
  }
  LL get(int k) {
    if (size() == 0 || k <= 0) return 0;
    else return get(rt, min(k, size()));
  }
  void ins(int key, LL val) {
    ins(rt, key, val);
    mp[key] += val;
  }
  void merge(const Treap &rhs) {
    int now = -size();
    for (auto &v : rhs.mp) {
      ins(now ++, v.second);
    }
  }
} tp[MAXN];

vector<int> G[MAXN];
LL sz[MAXN], sz2[MAXN];
int N, K;

void init() {
  pt = pool; null = Treap::NewNode(0, 0);
  null->ch[0] = null->ch[1] = null;
  null->sz = 0; null->pri = INF;
  for (int i = 1; i <= N; ++ i) {
    tp[i].rt = null;
    tp[i].mp.clear();
  }
}

/*Treap& solve(int u, int K, int f = -1) {
  sz[u] = 1; sz2[u] = 0;
  Treap &tu = tp[u];
  vector<PIT> pt;
  for (auto &v : G[u]) if (v != f) {
    Treap &tv = solve(v, K, u);
    pt.push_back(PIT(v, tv));
    sz[u] += sz[v]; sz2[u] += sqr(sz[v]);
  }
  for (size_t i = 0; i < pt.size(); ++ i) {
    int v = pt[i].first;
    Treap &tv = pt[i].second;
    LL coef = sqr(N - sz[v]) - (sz2[u] - sqr(sz[v])) - sqr(N - sz[u]);
    ret += tv.get(K - 1) * coef;
    if (tv.size() > tu.size()) swap(tu, tv);
    int lev = 1;
    for (auto &x : tv.mp) {
      ret += tu.get(K - lev - 1) * x.second;
      ++ lev;
    }
    tu.merge(tv);
  }
  tu.ins(-(tu.size() + 1), sqr(sz[u]) - sz2[u]);
  return tu;
}*/

typedef pair<int, Treap&> PIT;
vector<PIT> cs[MAXN];

inline LL sqr(LL n) {return n * n;}

LL solve(int K) {
  init();
  static int Q[MAXN], vis[MAXN], fa[MAXN];
  LL ret = 0;
  for (int i = 1; i <= N; ++ i) {
    vis[i] = false; sz[i] = sz2[i] = 0;
    cs[i].clear();
  }
  Q[0] = 1; vis[1] = true;
  for (int h = 0, t = 1; h < t; ++ h) {
    int u = Q[h];
    for (auto &v : G[u]) if (!vis[v]) {
      Q[t ++] = v; vis[v] = true;
      fa[v] = u;
    }
  }
  for (int i = N - 1; i >= 0; -- i) {
    int u = Q[i]; sz[u] ++;
    Treap &tu = tp[u];
    for (size_t j = 0; j < cs[u].size(); ++ j) {
      int v = cs[u][j].first;
      Treap &tv = cs[u][j].second;
      LL coef = sqr(N - sz[v]) - (sz2[u] - sqr(sz[v])) - sqr(N - sz[u]);
      ret += tv.get(K - 1) * coef;
      if (tv.size() > tu.size()) swap(tu, tv);
      int lev = 1;
      for (auto &x : tv.mp) {
        ret += tu.get(K - lev - 1) * x.second;
        ++ lev;
      }
      tu.merge(tv);
    }
    sz[fa[u]] += sz[u]; sz2[fa[u]] += sqr(sz[u]);
    tu.ins(-(tu.size() + 1), sqr(sz[u]) - sz2[u]);
    cs[fa[u]].push_back(PIT(u, tu));
  }
  return ret;
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d%d", &N, &K);
    for (int i = 1; i <= N; ++ i) G[i].clear();
    for (int i = 1; i < N; ++ i) {
      int u, v; scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
    }
    LL ret = sqr((LL)N * (N - 1) / 2 + N) - solve(N);
    ret += solve(K);
    printf("%llu\n", ret);
  }
}

Problem E Quiz for EXO-L

给出12种图案, 以及一个$n \times n$的黑白像素矩阵, 问矩阵对应的图案.

数据规模: $100 \le n \le 900$

大部分图像可以通过数黑白联通块的数据区分. 有两种图像不能区分, 然后用黑色像素点的比例就可以区分了.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 1000 + 10;
const char* exo[] = {
	"Baekhyun", "Chanyeol", "Chen", "D.O",
	"Kai", "Kris", "Lay", "Luhan",
	"Sehun", "Suho", "Tao", "Xiumin"
};

const int bw[][2] = {
	{9,2}, {5, 1}, {1, 3}, {1, 2},
	{2, 13}, {3, 1}, {6, 2}, {5, 8},
	{5, 2}, {2, 8}, {2, 4}, {5, 2}
};

int mp[MAXN][MAXN];
int N, M, cb, cw;

const int dx[]={1, 0, -1, 0, 1, -1, 1, -1};
const int dy[]={0, 1, 0, -1, 1, 1, -1, -1};

void mark(int x, int y, int c) {
	queue<PII> Q; Q.push(PII(x, y)); mp[x][y] = -1;
	while (!Q.empty()) {
		PII nw = Q.front(); Q.pop();
		for (int i = 0; i < 8; ++ i) {
			x = nw.first + dx[i], y = nw.second + dy[i];
			if (x < 0 || y < 0 || x >= N || y >= N) continue;
			if (mp[x][y] != c) continue;
			mp[x][y] = -1; Q.push(PII(x, y));
		}
	}
}

int main() {
	int T; scanf("%d", &T);
	for (int _ = 0; _ < T; ++ _) {
		scanf("%d%d", &N, &M); cb = 0, cw = 0;
		for (int i = 0, x = 0, y = 0; i < M; ++ i) {
			int c; scanf("%d", &c);
			if (i & 1) cb += c;
			else cw += c;
			while (c --) {
				mp[x][y] = i & 1;
				++ y; if (y == N) ++ x, y = 0;
			}
		}
		int v[2] = {0, 0};
		for (int i = 0; i < N; ++ i) {
			for (int j = 0; j < N; ++ j) {
				if (mp[i][j] != -1) {
					v[mp[i][j]] ++;
					mark(i, j, mp[i][j]);
				}
			}
		}
		if (v[0] == 2 && v[1] == 5) {
			if (cb * 10000 < 1800 * N * N) puts("Xiumin");
			else puts("Sehun");
		}
		else {
			for (int i = 0; i < 12; ++ i) {
				if (v[0] == bw[i][1] && v[1] == bw[i][0]) {
					puts(exo[i]);
					break;
				}
			}
		}
	}
	return 0;
}

Problem F Superbot

给出一个$n \times m$的格子, 还有一个方向控制panel. 在每一秒可以干如下三件事:

  • 按下方向键
  • 光标移动一格
  • do nothing

panel每隔$P$s会旋转一下. 问从起点到终点的最短时间.

数据规模: $1 \le n,m \le 10, 1 \le P \le 50$

简单的bfs, 以$(x,y,c,t)$为状态: 当前坐标$(x,y)$, 光标和左方向键的距离$c$, 当前时间对$P$取模为$t$.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int MAXN = 20, MAXP = 60;

char mp[MAXN][MAXN];
bool mk[MAXN][MAXN][MAXP][4];
int N, M, P;

struct Node {
  int x, y, c, p, d;
  Node() {}
  Node(int x, int y, int c, int p, int d): 
    x(x), y(y), c(c), p(p), d(d) {}
};

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

void expand(int x, int y, int c, int p, int d, queue<Node> &Q) {
  if (x < 0 || y < 0 || x >= N || y >= M || mp[x][y] == '*') return;
  if (p == P) c = (c + 3) % 4, p = 0;
  if (mk[x][y][p][c]) return;
  Q.push(Node(x, y, c, p, d));
  mk[x][y][p][c] = true;
}

int solve(PII src, PII tar) {
  queue<Node> Q;
  Q.push(Node(src.first, src.second, 0, 0, 0));
  mk[src.first][src.second][0][0] = true;
  while (!Q.empty()) {
    Node nw = Q.front(); Q.pop();
    if (nw.x == tar.first && nw.y == tar.second) return nw.d;
    // push button
    expand(nw.x + dx[nw.c], nw.y + dy[nw.c], nw.c, nw.p + 1, nw.d + 1, Q);
    // cursor move left
    expand(nw.x, nw.y, (nw.c + 3) % 4, nw.p + 1, nw.d + 1, Q);
    // cursor move right
    expand(nw.x, nw.y, (nw.c + 1) % 4, nw.p + 1, nw.d + 1, Q);
    // do nothing
    expand(nw.x, nw.y, nw.c, nw.p + 1, nw.d + 1, Q);
  }
  return -1;
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d%d%d", &N, &M, &P);
    PII src, tar;
    for (int i = 0; i < N; ++ i) {
      scanf("%s", mp[i]);
      for (int j = 0; j < M; ++ j) {
        if (mp[i][j] == '@') src = PII(i, j), mp[i][j] = '.';
        if (mp[i][j] == '$') tar = PII(i, j), mp[i][j] = '.';
      }
    }
    memset(mk, 0, sizeof(mk));
    int ret = solve(src, tar);
    if (ret == -1) puts("YouBadbad");
    else printf("%d\n", ret);
  }
  return 0;
}

Problem G Cylinder Candy

给出一个半径为$r$, 高度为$h$的圆柱. 在外面包一层厚度为$d$的巧克力, 问最终的体积和表面积.

数据规模: $1 \le r, h, d \le 100$

就是积分.

体积可以考虑用Cylinder Shell(不懂得google一下)来积分

面积直接用旋转体侧面积的方法(不懂得翻微积分课本)搞就好了.

#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);

double sqr(double x) {return x * x;}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int r, h, d; scanf("%d%d%d", &r, &h, &d);
    double V = PI * (4 * d * sqr(d) + 3 * PI * r * sqr(d) + 6 * sqr(r) * d) / 3 + PI * sqr(r + d) * h;
    double S = 2 * PI * (sqr(r) + h * (r + d) + PI * r * d + 2 * sqr(d));
    printf("%.18f %.18f\n", V, S);
  }
  return 0;
}

Problem H Earthstone: Easy Version

给出两个随从的攻击力和血量, 第一个攻击第二个的结果.

应该没有人不会这题.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    int A1, H1, A2, H2;
    scanf("%d%d%d%d", &A1, &H1, &A2, &H2);
    if (A1 == 0) puts("Invalid");
    else {
      H1 -= A2; H2 -= A1;
      if (H1 <= 0) printf("Discard ");
      else printf("%d %d ", A1, H1);
      if (H2 <= 0) printf("Discard\n");
      else printf("%d %d\n", A2, H2);
    }
  }
  return 0;
}

Problem I GCD Expectation

给出$n$个数$\{a_1,a_2,\dots,a_n\}$, 问所有子集gcd的$k$次方的和.

数据规模: $1 \le n, a_i \le 10^6$

经典的容斥, 大家应该都会做.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1000000 + 10, MOD = 998244353;

LL pm(LL a, LL n) {
  LL r = 1;
  for (; n; n >>= 1) {
    if (n & 1) r = r * a % MOD;
    a = a * a % MOD;
  }
  return r;
}

int a[MAXN], cnt[MAXN], f[MAXN];
int N, K, mx;

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    scanf("%d%d", &N, &K); mx = 0;
    assert(1 <= N && N <= 1000000);
    assert(1 <= K && K <= 1000000);
    for (int i = 0; i < N; ++ i) {
      scanf("%d", a + i);
      assert(1 <= a[i] && a[i] <= 1000000);
      cnt[a[i]] ++; mx = max(mx, a[i]);
    }
    for (int g = mx; g >= 1; -- g) {
      int sum = 0; f[g] = 0;
      for (int ng = g; ng <= mx; ng += g) {
        sum += cnt[ng];
        f[g] = (f[g] - f[ng] + MOD) % MOD;
      }
      f[g] = (f[g] + pm(2, sum) - 1) % MOD;
    }
    int ret = 0;
    for (int g = 1; g <= mx; ++ g) {
      ret = (ret + (LL)pm(g, K) * f[g] % MOD) % MOD;
    }
    printf("%d\n", ret);
    for (int i = 0; i < N; ++ i) cnt[a[i]] = 0;
  }
  return 0;
}
  • No match
7oky0-H0t said:
Sat, 18 Apr 2015 01:14:34 +0800

第一题不是所有数异或一下就可以了吗?

LCLL said:
Fri, 08 May 2015 20:11:49 +0800

第一题 3 <= N <= 100?


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter