Brief explanation of NOI 2019

Start here

What about agc 046

Last year's question was really hard to write

Day 1

Problem A home route

Violence is enough. 2e8 is really stable.

You can sort by start time, and then optimize the slope at each point.

Code

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

const int N = 2e5 + 5;

#define ll long long

const ll llf = (signed ll) (~0ull >> 3);

typedef class Point {
  public:
    int x;
    ll y;
    
    Point(int x = 0, ll y = 0) : x(x), y(y) { }
} Point;

Point operator - (Point a, Point b) {
  return Point(a.x - b.x, a.y - b.y);
}

ll cross(Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}

typedef class ConvexHull {
  public:
    int pos;
    vector<Point> stk;
    
    ConvexHull() : pos(0) { }
   
    void insert(int _x, ll _y) {
      Point p (_x, _y);
      while (!stk.empty() && stk.back().x == _x && stk.back().y >= _y)
        stk.pop_back();
      while (stk.size() > 1u && cross(stk.back() - stk[stk.size() - 2], p - stk.back()) <= 0)
        stk.pop_back();
      stk.push_back(p);
    }
    ll query(ll k) {
      if (stk.empty()) {
        return llf;
      }
      ll ret = llf;
      for (int i = 0; i < (signed) stk.size(); i++) {
        ret = min(ret, stk[i].y - stk[i].x * k);
      }
      pos = min(pos, (signed) stk.size() - 1);
      while (pos < (signed) stk.size() - 1 && stk[pos].y - k * stk[pos].x > stk[pos + 1].y - k * stk[pos + 1].x)
        pos++;
      return stk[pos].y - k * stk[pos].x;
    }
} ConvexHull;

typedef class Route {
  public:
    int s, t, p, q;
    
    void read() {
      scanf("%d%d%d%d", &s, &t, &p, &q);
    }
    
    bool operator < (Route b) const {
      return p < b.p;
    }
} Route;

int n, m, A, B, C;
ll f[N];
Route R[N];
int ord[N];
ConvexHull con[N];

int main() {
  freopen("route.in", "r", stdin);
  freopen("route.out", "w", stdout);
  scanf("%d%d%d%d%d", &n, &m, &A, &B, &C);
  for (int i = 1; i <= m; i++) {
    R[i].read();
    assert(R[i].p < R[i].q);
  }
  sort(R + 1, R + m + 1);
  R[0].t = 1, R[0].q = 0;
  for (int i = 0; i <= m; i++) {
    ord[i] = i;
  }
  sort(ord + 1, ord + m + 1, [&] (int x, int y) { return R[x].q < R[y].q; });
  ll ans = llf;
  int* po = ord, *_po = ord + m + 1;
  for (int i = 1; i <= m; i++) {
    while (po != _po && R[*po].q <= R[i].p) {
      if (f[*po] < (llf >> 1)) {
        Route &r = R[*po];
        con[r.t].insert(r.q, f[*po] + 1ll * A * r.q * r.q - 1ll * B * r.q);
      }
      po++;
    }
    Route& r = R[i];
    f[i] = con[r.s].query(2 * A * r.p);
    if (f[i] >= (llf >> 1))
      continue;
    f[i] += 1ll * A * r.p * r.p + 1ll * B * r.p + C;
    if (r.t == n) {
      ans = min(ans, f[i] + r.q);
    } 
  }
  printf("%lld\n", ans);
  return 0;
}

Problem B robot

Obviously, the answer is a piecewise polynomial of no more than $n$degree with respect to the maximum number that can be selected.

It is found that the length and maximum length of the interval involved in writing a violent typing table is about 17400, because a point may be added $O(log n) $times because of +1, and the total number of segments is about $10^5$. Maintain piecewise polynomials directly with point values. It is said that the polynomial expressed by the coefficient can also be maintained directly.

Code 

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

const int N = 305;
const int Mod = 1e9 + 7;

const int inf = (~0u >> 2);

#define ll long long

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}
int inv(int a) {
  int x, y;
  exgcd(a, Mod, x, y);
  return x < 0 ? x + Mod : x;
}

typedef class Zi {
  public:
    int v;
     
    Zi() { }
    Zi(int v) : v(v) { }
    Zi(ll x) : v(x % Mod) {  }
      
    friend Zi operator + (Zi a, Zi b) {
      int x = a.v + b.v;
      return x >= Mod ? x - Mod : x;
    }
    friend Zi operator - (Zi a, Zi b) {
      int x = a.v -b.v;
      return x < 0 ? x + Mod : x; 
    }
    friend Zi operator * (Zi a, Zi b) {
      return 1ll * a.v * b.v;
    }
    friend Zi operator ~ (Zi a) {
      return inv(a.v);
    }
    Zi& operator += (Zi b) {
      return *this = *this + b;
    }
    Zi& operator -= (Zi b) {
      return *this = *this - b;
    }
    Zi& operator *= (Zi b) {
      return *this = *this * b;
    }
} Zi;

vector<Zi> Inv;
vector<Zi> fac, _fac;

void prepare(int n) {
  Inv.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    Inv[i] = ~Zi(i);
  }
  fac.resize(n + 1);
  _fac.resize(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i;
  }
  _fac[n] = ~fac[n];
  for (int i = n; i; i--) {
    _fac[i - 1] = _fac[i] * i;
  }
}

int n, S;

typedef class Segment {
  public:
    int r;
    vector<Zi> f;
    
    Segment() { }
    Segment(int r, vector<Zi> f) : r(r), f(f) { }
    
    void init(Zi x) {
      f.resize(S, x);
    }
    Zi eval(Zi n) {
      static Zi L[N], R[N];
      if (n.v < S) {
        return f[n.v];
      }
      L[0] = 1;
      for (int i = 0; i < S; i++) {
        L[i + 1] = L[i] * (n - i); 
      }
      R[S] = 1;
      for (int i = S; i--; ) {
        R[i] = R[i + 1] * (n - i);
      }
      Zi ret = 0;
      for (int i = 0; i < S; i++) {
        Zi tmp = f[i] * L[i] * R[i + 1] * _fac[i] * _fac[S - 1 - i];
        if ((S - 1 - i) & 1) {
          ret -= tmp; 
        } else {
          ret += tmp;
        }
      }
      return ret;
    }
    Segment operator + (const Segment& b) {
      Segment s;
      s.init(S);
      s.r = min(r, b.r);
      for (int i = 0; i < S; i++) {
        s.f[i] = f[i] + b.f[i];
      } 
      return s;
    }
    Segment operator * (const Segment& b) {
      Segment s;
      s.init(S);
      s.r = min(r, b.r);
      for (int i = 0; i < S; i++) {
        s.f[i] = f[i] * b.f[i];
      }
      return s;
    }
    
    Segment& operator += (Zi x) {
      for (auto& y : f)
        y += x;
      return *this;
    }
    
    void pre_sum() {
      Zi sum = 0;
      for (int i = 0; i < S; i++) {
        sum += f[i];
        f[i] = sum;
      }
    }
    
    void shift() {
      r = min(r + 1, inf);
      f.insert(f.begin(), eval(Mod - 1));
      f.pop_back();
    }
} Segment;

typedef class Function {
  public:
    vector<Segment> seg;
    
    void append(Segment s) {
      seg.push_back(s);
    }
      
    void pre_sum() {
      int ls = 0;
      Zi sum = 0;
      for (auto&s : seg) {
        s.pre_sum();
        s += (sum - s.eval(ls));
        ls = s.r;
        sum = s.eval(s.r);
      }
    }
    
    Function operator * (const Function& b) {
      Function f;
      auto pl = seg.begin(), _pl = seg.end();
      auto pr = b.seg.begin(), _pr = b.seg.end();
      while (pl != _pl && pr != _pr) {
        if ((*pl).r == (*pr).r) {
          f.append(*(pl++) * *(pr++));
        } else if ((*pl).r < (*pr).r) {
          f.append(*(pl++) * *pr);
        } else {
          f.append(*pl * *(pr++));
        }
      }
      assert(pl == _pl && pr == _pr);
      return f;
    }
    Function operator + (const Function& b) {
      Function f;
      auto pl = seg.begin(), _pl = seg.end();
      auto pr = b.seg.begin(), _pr = b.seg.end();
      while (pl != _pl && pr != _pr) {
        if ((*pl).r == (*pr).r) {
          f.append(*(pl++) + *(pr++));
        } else if ((*pl).r < (*pr).r) {
          f.append(*(pl++) + *pr);
        } else {
          f.append(*pl + *(pr++));
        }
      }
      assert(pl == _pl && pr == _pr);
      return f;
    }
    
    Function& reserve(int l, int r) {
      for (int i = seg.size(); i--; ) {
        if (!i || seg[i - 1].r < r) {
          seg[i].r = r;
          seg.erase(seg.begin() + i + 1, seg.end());
          break;
        }
      }
      seg.push_back(Segment(inf, vector<Zi>(S, 0)));
      if (l == 1) return *this;
      for (int i = 0; i < (seg.size()); i++) {
        if (seg[i].r >= l) {
          seg.erase(seg.begin(), seg.begin() + i);
          break;
        }      
      }
      seg.insert(seg.begin(), Segment(l - 1, vector<Zi>(S, 0)));
      return *this;
    }
    
    Function& shift() {
      for (auto& s : seg) {
        s.shift();
      }
      seg.insert(seg.begin(), Segment(1, vector<Zi>(S, 0)));
      return *this;
    }
    
    void shrink() {
      vector<Segment> nseg;
      int ls = 0;
      for (auto& s : seg) {
        if (s.r > ls) {
          nseg.push_back(s);
          ls = s.r; 
        }        
      }
      seg = nseg;
    }
} Function;

int A[N], B[N];
bool vis[N][N];
Function f0, fe, f[N][N];

int Abs(int x) {
  return x < 0 ? -x : x;
} 

Function solve(int l, int r) {
  if (l > r) {
    return fe;
  }
  if (vis[l][r]) {
    return f[l][r];
  }
  vis[l][r] = true;
  Function& F = f[l][r];
  F = f0;
  for (int i = l; i <= r; i++) {
    if (Abs((i - l) - (r - i)) <= 2) {
      F = F + (solve(l, i - 1) * ((i + 1 <= r) ? solve(i + 1, r).shift() : fe)).reserve(A[i], B[i]);
    }
  }
  F.shrink();
  F.pre_sum();
  return F;
}

int main() {
  freopen("robot.in", "r", stdin);
  freopen("robot.out", "w", stdout);
  scanf("%d", &n);
  S = n + 2;
  prepare(S + 3);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d", A + i, B + i); 
  }
  f0.append(Segment(inf, vector<Zi>(S, 0)));
  fe.append(Segment(inf, vector<Zi>(S, 1)));
  Function fans = solve(1, n);
  Zi ans = fans.seg.back().eval(inf);
  printf("%d\n", ans.v);
  return 0;
}

Problem C sequence

Open a large array to get higher scores than expected, learned. The

There is a good plan, but the square version can not run 2e3, and the simulated cost flow can not run 3e5. d1 t3 is often poisonous.

Consider requiring you to select one $x$and one $y$at a time, which is a good way to limit their number to the same.

Build two columns of points, $A_i$to $B_i$edge linking: create another pair of points $x, x'$, edge linking $(x, X', K - L, 0) $, which is used to limit the number of different pairs. Then $A_i$to $x$and $x'$to $B_i$edge$ S$to $A_i$edge, $B_i$to $T$.

Consider how the cost flow:

  • If $x \rightarrow$is not full, it is equivalent to selecting the largest one on the left and the largest one on the right, and then judging whether its traffic will increase.
  • Otherwise, there are $4$cases
    • $S \rightarrow A_i \rightarrow B_i \rightarrow T$
    • $S \rightarrow A_i \rightarrow x \rightarrow A_j \rightarrow B_j \rightarrow T$
    • $S \rightarrow A_i \rightarrow B_i \rightarrow x' \rightarrow B_j \rightarrow T$
    • $S \rightarrow A_i \rightarrow B_i \rightarrow x' \rightarrow x \rightarrow  A_j \rightarrow B_j \rightarrow  T$

Then just maintain it blindly

Code

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

typedef class Input {
	protected:
		const static int limit = 65536;
		FILE* file; 

		int ss, st;
		char buf[limit];
	public:
		
		Input() : file(NULL)	{	};
		Input(FILE* file) : file(file) {	}

		void open(FILE *file) {
			this->file = file;
		}

		void open(const char* filename) {
			file = fopen(filename, "r");
		}

		char pick() {
			if (ss == st)
				st = fread(buf, 1, limit, file), ss = 0;//, cerr << "str: " << buf << "ed " << st << endl;
			return buf[ss++];
		}
} Input;

#define digit(_x) ((_x) >= '0' && (_x) <= '9')

Input& operator >> (Input& in, unsigned& u) {
	char x;
	while (~(x = in.pick()) && !digit(x));
	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');
	return in;
}

Input& operator >> (Input& in, unsigned long long& u) {
	char x;
	while (~(x = in.pick()) && !digit(x));
	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');
	return in;
}

Input& operator >> (Input& in, int& u) {
	char x;
	while (~(x = in.pick()) && !digit(x) && x != '-');
	int aflag = ((x == '-') ? (x = in.pick(), -1) : (1));
	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');
	u *= aflag;
	return in;
}

Input& operator >> (Input& in, long long& u) {
	char x;
	while (~(x = in.pick()) && !digit(x) && x != '-');
	int aflag = ((x == '-') ? (x = in.pick(), -1) : (1));
	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');
	u *= aflag;
	return in;
}

Input& operator >> (Input& in, double& u) {
	char x;
	while (~(x = in.pick()) && !digit(x) && x != '-');
	int aflag = ((x == '-') ? (x = in.pick(), -1) : (1));
	for (u = x - '0'; ~(x = in.pick()) && digit(x); u = u * 10 + x - '0');
	if (x == '.') {
		double dec = 1;
		for ( ; ~(x = in.pick()) && digit(x); u = u + (dec *= 0.1) * (x - '0'));
	}
	u *= aflag;
	return in;
}

Input& operator >> (Input& in, char* str) {
	char x;
	while (~(x = in.pick()) && x != '\n' && x != ' ')
		*(str++) = x;
	*str = 0;
	return in;
}

Input in (fopen("sequence.in", "r"));

typedef class Output {
	protected:
		const static int Limit = 65536;
		char *tp, *ed;
		char buf[Limit];
		FILE* file;
		int precision;

		void flush() {
			fwrite(buf, 1, tp - buf, file);
			fflush(file);
			tp = buf;
		}

	public:

		Output() {	}
		Output(FILE* file) : tp(buf), ed(buf + Limit), file(file), precision(6) {	}
		Output(const char *str) : tp(buf), ed(buf + Limit), precision(6) {
			file = fopen(str, "w");
		}
		~Output() {
			flush();
		}

		void put(char x) {
			if (tp == ed)
				flush();
			*(tp++) = x;
		}

		int get_precision() {
			return precision;
		}
		void set_percision(int x) {
			precision = x;
		}
} Output;

Output& operator << (Output& out, int x) {
	static char buf[35];
	static char * const lim = buf + 34;
	if (!x)
		out.put('0');
	else {
		if (x < 0)
			out.put('-'), x = -x;
		char *tp = lim;
		for ( ; x; *(--tp) = x % 10, x /= 10);
		for ( ; tp != lim; out.put(*(tp++) + '0'));
	}
	return out;
}

Output& operator << (Output& out, long long x) {
	static char buf[36];
	static char * const lim = buf + 34;
	if (!x)
		out.put('0');
	else {
		if (x < 0)
			out.put('-'), x = -x;
		char *tp = lim;
		for ( ; x; *(--tp) = x % 10, x /= 10);
		for ( ; tp != lim; out.put(*(tp++) + '0'));
	}
	return out;
}

Output& operator << (Output& out, unsigned x) {
	static char buf[35];
	static char * const lim = buf + 34;
	if (!x)
		out.put('0');
	else {
		char *tp = lim;
		for ( ; x; *(--tp) = x % 10, x /= 10);
		for ( ; tp != lim; out.put(*(tp++) + '0'));
	}
	return out;
}

Output& operator << (Output& out, char x)  {
	out.put(x);
	return out;
}

Output& operator << (Output& out, const char* str) {
	for ( ; *str; out.put(*(str++)));
	return out;
}

Output& operator << (Output& out, double x) {
	int y = x;
	x -= y;
	out << y << '.';
	for (int i = out.get_precision(); i; i--, y = x * 10, x = x * 10 - y, out.put(y + '0'));
	return out;
}

Output out ("sequence.out");

#define pii pair<int, int>
#define ll long long

const int inf = (signed) (~0u >> 2);

typedef class ZKW {
  public:
    int M;
    pii mx[524288];
    
    void init(int n, pii* w) {
      for (M = 1; M < n; M <<= 1);
      for (int i = 0; i < n; i++) {
        mx[i + M] = w[i];
      }
      for (int i = n; i < M; i++) {
        mx[i + M] = pii(-inf, 0);
      }
      for (int i = M; --i; push_up(i));
    }
    
    void push_up(int p) {
      mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
    }
    void upd(int p, int vi) {
      p += M;
      mx[p] = pii(vi, p - M);
      for ( ; p >>= 1; push_up(p));
    }
    int qry() {
      return mx[1].first;
    }
    int qryi() {
      return mx[1].second;
    }
} ZKW;

const int N = 2e5 + 5;

int T, n, K, L;
int cnt;
int a[N], b[N];
ZKW zs, za, zb, _za, _zb;
bool ina[N], inb[N];

void seclecta(int p) {
  ina[p] = true;
  cnt -= ina[p] && inb[p];
  zs.upd(p, -inf);
  za.upd(p, -inf);
  _za.upd(p, -inf);
  if (!inb[p])
    _zb.upd(p, b[p]);
}
void seclectb(int p) {
  inb[p] = true;
  cnt -= ina[p] && inb[p];
  zs.upd(p, -inf);
  zb.upd(p, -inf);
  _zb.upd(p, -inf);
  if (!ina[p])
    _za.upd(p, a[p]);
}

void solve() {
  static pii tmp[N];
  cnt = 0;
  in >> n >> K >> L;
  for (int i = 0; i < n; i++) {
    in >> a[i];
  }
  for (int i = 0; i < n; i++) {
    in >> b[i];
  }
  for (int i = 0; i < n; i++)
    tmp[i] = pii(a[i] + b[i], i);
  zs.init(n, tmp);
  for (int i = 0; i < n; i++)
    tmp[i] = pii(a[i], i);
  za.init(n, tmp);
  for (int i = 0; i < n; i++)
    tmp[i] = pii(b[i], i);
  zb.init(n, tmp);
  for (int i = 0; i < n; i++)
    tmp[i] = pii(-inf, i);
  _za.init(n, tmp);
  _zb.init(n, tmp);
  fill(ina, ina + n, false);
  fill(inb, inb + n, false);
  for (int i = 1; i <= K; i++) {
    if (cnt == K - L) {
      int swpa = _za.qry() + zb.qry();
      int swpb = za.qry() + _zb.qry();
      int mx = zs.qry(), id = 0, q;
      if ((q = _za.qry() + _zb.qry()) > mx)
        id = 1, mx = q;
      if ((q = swpa) > mx)
        id = 2, mx = q;
      if ((q = swpb) > mx)
        id = 3, mx = q;
      if (!id) {
        q = zs.qryi();
        seclecta(q);
        seclectb(q);      
      } else if (id == 1) {
        seclecta(_za.qryi());
        seclectb(_zb.qryi());
      } else if (id == 2) {
        seclecta(_za.qryi());
        seclectb(zb.qryi());
      } else {
        seclecta(za.qryi());
        seclectb(_zb.qryi());
      }
    } else {
      seclecta(za.qryi());
      seclectb(zb.qryi());
    }
    ++cnt;
  }
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += ina[i] * a[i];
    ans += inb[i] * b[i];
  }
  out << ans << '\n';
}

int main() {
  in >> T;
  while (T--) {
    solve();
  }
  return 0;
}

Day 2

Problem A bounce

Consider the dijkstra process, where we add one edge at a time. After an edge updates a point, a point can no longer be updated. So we just query all the points in a rectangle and delete them.

It can be maintained with segment tree set or KDtree.

Time complexity $O(n\log^2 n + m\log n) $.

Code

/**
 * loj
 * Problem#3159
 * Accepted
 * Time: 6467ms
 * Memory: 51568k
 */
#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

const int N = 7e4 + 5;
const int M = 150005;

typedef class Node {
	public:
		int eid, dis;

		Node() {	}
		Node(int eid, int dis) : eid(eid), dis(dis) {	}

		boolean operator < (Node b) const {
			return dis > b.dis;
		}
} Node;

#define pii pair<int, int>

int n, m, w, h;
int f[N];
boolean vis[N];
vector<int> G[N];
set<pii> S[N << 2];
priority_queue<Node> Q;

int xl[M], xr[M], yl[M], yr[M], W[M];

void insert(int p, int l, int r, int x, int y, int id) {
	S[p].insert(pii(y, id));
	if (l == r) return;
	int mid = (l + r) >> 1;
	if (x <= mid) {
		insert(p << 1, l, mid, x, y, id);
	} else {
		insert(p << 1 | 1, mid + 1, r, x, y, id);
	}
}

void del(int p, int l, int r, int x1, int x2, int y1, int y2, int w) {
	if (l == x1 && r == x2) {
		set<pii>::iterator it = S[p].lower_bound(pii(y1, 0));
		while (it != S[p].end() && (*it).first <= y2) {
			int id = (*it).second;
			if (!vis[id]) {
				vis[id] = true;
				f[id] = w;
				for (auto eid : G[id]) {
					Q.push(Node(eid, f[id] + W[eid]));
				}
			}
			it = S[p].erase(it);
		}
		return;
	}
	int mid = (l + r) >> 1;
	if (x2 <= mid) {
		del(p << 1, l, mid, x1, x2, y1, y2, w);
	} else if (x1 > mid) {
		del(p << 1 | 1, mid + 1, r, x1, x2, y1, y2, w);
	} else {
		del(p << 1, l, mid, x1, mid, y1, y2, w);
		del(p << 1 | 1, mid + 1, r, mid + 1, x2, y1, y2, w);
	}
}

int main() {
	freopen("jump.in", "r", stdin);
	freopen("jump.out", "w", stdout);
	scanf("%d%d%d%d", &n, &m, &w, &h);
	for (int i = 1, x, y; i <= n; i++) {
		scanf("%d%d", &x, &y);
		if (i ^ 1) {
			insert(1, 1, w, x, y, i);
		}
	}
	for (int i = 1, p; i <= m; i++) {
		scanf("%d%d%d%d%d%d", &p, W + i, xl + i, xr + i, yl + i, yr + i);
		G[p].push_back(i);
	}
	for (auto e : G[1]) {
		Q.push(Node(e, W[e]));
	}
	while (!Q.empty()) {
		int e = Q.top().eid;
		int d = Q.top().dis;
		Q.pop();
		del(1, 1, w, xl[e], xr[e], yl[e], yr[e], d);
	}
	for (int i = 2; i <= n; i++) {
		printf("%d\n", f[i]);
	}
	return 0;
}

Problem B bucket main ground

At first, I heard that I could read a specific math book. Later, I heard that I couldn't type a watch. At that time, I was different. I didn't read a book and couldn't type a watch

Consider calculating $e directly_ I$contribute to $e'_ Coefficient of j$. Consider $i \leqslant A$first

$$
\begin{align}
\binom{n - j}{A - i} \frac{A^{\underline{A-i+1}}(n-A)^{\underline{n - j - (A- i)}}}{n^{\underline{n - j + 1}}} &= \binom{n}{A}^{-1}\binom{n-j}{A- i}\binom{j-1}{i-1}
\end{align}
$$

Then $E'_j$will respond to $e of $i \leqslant A$_ I$is multiplied by this coefficient to sum.

Consider $e first_ When I = i$, put forward $\binom{n}{A}^{-1}$, and consider the combinatorial meaning of this formula: select $A$ball from $n$balls, and the $j$ball must be selected. If it is the $i$selected ball, the contribution is $i$.

Considering enumerating the selected balls, it is not difficult to find that it is equal to $\binom{n - 1}{A - 1} + (j - 1)\binom{n - 2}{A - 2}$.

For $i > a$.

Easy to find $E'_j$is a polynomial of degree with respect to $j$.

When $type = 2$, it is a quadratic polynomial about $j$.

It can be maintained violently or interpolated.

Interpolation contest (sure

Code

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

#define ll long long

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}

int inv(int a, int n) {
  int x, y;
  exgcd(a, n, x, y);
  return (x < 0) ? (x + n) : (x);
}

const int Mod = 998244353;

template <const int Mod = :: Mod>
class Z {
  public:
    int v;

    Z() : v(0) {	}
    Z(int x) : v(x){	}
    Z(ll x) : v(x % Mod) {	}

    friend Z operator + (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
    }
    friend Z operator - (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
    }
    friend Z operator * (const Z& a, const Z& b) {
      return Z(a.v * 1ll * b.v);
    }
    friend Z operator ~(const Z& a) {
      return inv(a.v, Mod);
    }
    friend Z operator - (const Z& a) {
      return Z(0) - a;
    }
    Z& operator += (Z b) {
      return *this = *this + b;
    }
    Z& operator -= (Z b) {
      return *this = *this - b;
    }
    Z& operator *= (Z b) {
      return *this = *this * b;
    }
};

Z<> qpow(Z<> a, int p) {
  Z<> rt = Z<>(1), pa = a;
  for ( ; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}

typedef Z<> Zi;

int n, m, type, q;

vector<Zi> fac, _fac;

void prepare(int n) {
  fac.resize(n + 1);
  _fac.resize(n + 1);
  fac[0] = 1;
  for (int i = 1; i <= n; i++) {
    fac[i] = fac[i - 1] * i;
  }
  _fac[n] = ~fac[n];
  for (int i = n; i; i--) {
    _fac[i - 1] = _fac[i] * i;
  }
}
Zi comb(int n, int m) {
  assert(n >= 0 && m >= 0);
  return n < m ? 0 : fac[n] * _fac[m] * _fac[n - m];
}
Zi _comb(int n, int m) {
  return _fac[n] * fac[m] * fac[n - m];
}

typedef vector<Zi> vec;

vec operator * (vec a, Zi k) {
  for (auto& x : a)
    x *= k;
  return a;
}
vec operator + (vec a, vec b) {
  if (a.size() < b.size())
    a.resize(b.size());
  for (int i = 0; i < (signed) b.size(); i++)
    a[i] += b[i];
  return a;
}

Zi eval(int A, int c) {
  return A - 1 < c ? 0 : comb(n - 1 - c, A - 1 - c);
}

vec get1(int A) {
  vec v (2);
  v[0] = eval(n - A, 0) * A;
  v[1] = eval(A, 1) + eval(n - A, 1);
  return v * _comb(n, A);
}
vec get2(int A) {
  vec v (3);
  v[0] = eval(n - A, 0) * A * (A - 1) * ((Mod + 1) >> 1);
  v[1] = eval(n - A, 1) * A;
  v[2] = eval(A, 2) + eval(n - A, 2);
  return v * _comb(n, A);
}

int main() {
  freopen("landlords.in", "r", stdin);
  freopen("landlords.out", "w", stdout);
  scanf("%d%d%d", &n, &m, &type);
  prepare(n + 1);
  vec f, g;
  if (type == 1) {
    f = {1, 1};
  } else {
    f = {1, 3, 2};
  }
  for (int i = 1, a; i <= m; i++) {
    scanf("%d", &a);
    g = vec {f[0]};
    g = g + get1(a) * f[1];
    if (type == 2)
      g = g + get2(a) * f[2];
    f = g;
  }
  scanf("%d", &q);
  Zi x;
  while (q--) {
    scanf("%d", &x.v);
    Zi ans = f[0] + f[1] * (x - 1);
    if (type == 2)
      ans += f[2] * (x - 1) * (x - 2) * ((Mod + 1) >> 1);
    printf("%d\n", ans.v);
  }
  return 0;
}

Problem C I Jun's exploration

A: it's not difficult to get a circle of XOR and sum around each point. It's done.

B: direct overall dichotomy.

For the partial division of the tree, we can assume that a point is a leaf, and then check whether it is a leaf by modifying it twice and asking it once. Therefore, we can judge whether a point is a leaf. Then you can peel the leaves every time.

For the case of a general graph, consider a random arrangement, and then apply the global bisection method of B. If a point is connected with an odd number of edges, then an edge must be found, otherwise it may be found.

It is not difficult to prove that in the worst case, it is expected to reduce $\frac{t}{3}$edges, where $t$is the number of points with non-zero degrees. Therefore, when there are outliers, the complexity is a bit false, and outliers need to be deleted.

Otherwise, you can spend $O(n\log n) $and expect to reduce the edges of $\frac{n}{3}$. Therefore, the expected number and complexity of operations are $O(m\log n) $.

As for the initial outliers, it seems that I only use the $O(n\log n) $randomization method with poor constants. It is estimated that the number of operations will be exceeded. However, it seems that there is no card in the data that does not process the initial outliers.

Code

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

int N, M;

namespace brute {
  
  vector<int> old;
  
  void solve() {
    old.resize(N, 0);
    for (int i = 0; i < N - 1; i++) {
      modify(i);
      for (int j = i + 1; j < N; j++) {
        int x = query(j);
        if (x ^ old[j]) {
          report(i, j);
          old[j] = x;
        }
      }
    }
  }
  
}

namespace subtaskA {

vector<int> v;
vector<int> old;

void solve() {
  v.assign(N, 0);
  old.assign(N, 0);
  for (int b = 1; b < N; b <<= 1) {
    for (int i = 0; i < N; i++) {
      if (i & b) {
        modify(i);
      }
    }
    for (int i = 0; i < N; i++) {
      int x = query(i);
      if (old[i] ^ x) {
        v[i] |= b;
        old[i] = x;
      }
    }
  }
  for (int i = 0; i < N; i++) {
    if ((v[i] ^ i) < i) {
      report(v[i] ^ i, i);
    }
  }
}

}

namespace subtaskB {

void dividing(int l, int r, vector<int> p)  {
  if (l == r) {
    for (auto x : p) {
      report(l, x);
    }
    return;
  }
  if (p.empty()) {
    return;
  }
  int mid = (l + r) >> 1;
  for (int i = l; i <= mid; i++) {
    modify(i);
  }
  vector<int> vl, vr;
  for (auto x : p) {
    if (x <= mid || query(x)) {
      vl.push_back(x); 
    } else {
      vr.push_back(x);
    }
  }
  for (int i = l; i <= mid; i++) {
    modify(i);
  }
  dividing(l, mid, vl);
  dividing(mid + 1, r, vr);
}

void solve() {
  vector<int> p (N - 1);
  for (int i = 1; i < N; i++)
    p[i - 1] = i;
  dividing(0, N - 1, p);
}

}

namespace general {

vector<int> P;
vector<int> on;
vector<int> tg;
vector<bool> exist;
vector<vector<int>> G;

void answer(int x, int y) {
  report(x, y);
  G[x].push_back(y);
  G[y].push_back(x);
  M--;
  if (check(x)) {
    exist[x] = false;
  }
  if (check(y)) {
    exist[y] = false;
  }
}
void upd(int p) {
  modify(p);
  on[p] ^= 1; 
}
bool qry(int p) {
  bool ret = query(p);
  for (auto x : G[p]) {
    ret ^= on[x];
  }
  return ret ^ tg[p];
}

void light_on(int l, int r) {
  static int ql = 0, qr = -1;
  if (l < 0) {
    for (int i = ql; i <= qr; i++) {
      upd(P[i]);
    }
    ql = 0, qr = -1;
    return;
  }
  for (int i = ql; i <= qr; i++) {
    if (i < l || i > r) {
      upd(P[i]);
    }
  }
  for (int i = l; i <= r; i++) {
    if (!on[P[i]]) {
      upd(P[i]);  
    }
  }
  ql = l, qr = r;
}

void dividing(int l, int r, vector<int> S) {
  if (S.empty()) {
    return;
  }
  if (l == r) {
    int p = P[l];
    light_on(l, l);
    for (auto x : S) {
      if (P[x] != p && qry(P[x])) {
        answer(p, P[x]);
      }
    }
    return;
  }
  int mid = (l + r) >> 1;
  light_on(l, mid);
  vector<int> sl, sr;
  for (auto x : S) {
    if (x <= mid || qry(P[x])) {
      sl.push_back(x);
    } else {
      sr.push_back(x);
    }
  }
  dividing(l, mid, sl);
  dividing(mid + 1, r, sr);
}

void solve() {
  P.resize(N);
  tg.assign(N, 0);
  on.assign(N, false);
  exist.assign(N, true);
  G.assign(N, vector<int>());
  for (int i = 0; i < N; i++)
    P[i] = i;
  vector<int> P0 = P;
  while (M) {
    light_on(-1, 0);
    vector<int> tmp;
    for (auto x : P) {
      if (exist[x]) {
        tmp.push_back(x);
      }
    }
    P = tmp;
    P0.resize(P.size());
    random_shuffle(P.begin(), P.end());
//    cerr << P.size() << " " << " " << M << '\n';
    dividing(0, (signed) P.size() - 1, P0);
  }
}

}

void explore(int N, int M) {
  srand(time(NULL));
//  srand(233u);
  ::N = N;
  ::M = M;
  if (N <= 500) {
    brute::solve();
  } else if (N % 10 == 8) {
    subtaskA::solve();
  } else if (N % 10 == 7) {
    subtaskB::solve();
  } else {
    general::solve(); 
  }
}

Tags: NOI

Posted by FuriousIrishman on Wed, 01 Jun 2022 05:35:58 +0530