【BZOJ 3672】[NOI2014] 购票

解题报告

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3672
神犇题解:http://blog.csdn.net/lych_cys/article/details/51317809

解题报告

一句话题解:树上CDQ分治

先推一推式子,发现可以斜率优化
于是我们可以用树链剖分做到$O(n \log^3 n)$
或者也可以用KD-Tree配合DFS序做到$O(n^{1.5} \log n)$

我们进一步观察,使单纯的DFS序不能做的地方在于凸包是动态的,查询也是动态的且限制了横坐标的最小值
考虑分治的话,我们按横坐标的限制排序,然后边查询边更新凸包就可以了
总的时间复杂度:$O(n \log^2 n)$

Code

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

const int N = 200009;
const int M = N << 1;
const LL INF = 6e18;

int n, head[N], nxt[M], to[M], fa[N];
LL q[N], p[N], len[N], dep[N], f[N];

struct Point{
	LL x, y, id, range;
	inline Point() {
	}
	inline Point(LL a, LL b, LL c, LL d):x(a), y(b), id(c), range(d) {
	}
	inline bool operator < (const Point &P) const {
		return x > P.x || (x == P.x && y > P.y);
	}
	inline Point operator - (const Point &P) {
		return Point(x - P.x, y - P.y, 0, 0);
	}
	inline double operator * (const Point &P) {
		return (double)x * P.y - (double)y * P.x;
	}
	inline double slope(const Point &P) {
		return (double)(y - P.y) / (x - P.x);
	}
	static bool update(const Point &P1, const Point &P2) {
		return P1.range > P2.range;
	}
};

inline LL read() {
	char c = getchar(); LL ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

class DivideAndConquer{
int sz[N], vis[N];
public:	
	inline void solve(int w, int universe) {
		int top = w;
		vis[w = FindRoot(w, universe)] = 1;
		if (fa[w] && !vis[fa[w]]) {
			solve(top, universe - sz[w]);
		}
		vector<Point> cvx;
		for (int nw = fa[w]; dep[nw] >= dep[top]; nw = fa[nw]) {
			cvx.push_back(Point(dep[nw], f[nw], nw, dep[nw] - len[nw]));
		}
		vector<Point> que;
		que.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				DFS(to[i], w, que);
			}	
		}	
		
		sort(que.begin(), que.end(), Point::update);
		sort(cvx.begin(), cvx.end());
		for (int i = 0, j = 0, tot = 0; i < (int)que.size(); i++) {
			for (; j < (int)cvx.size() && cvx[j].x >= que[i].range; j++) {
				for (; tot > 1 && (cvx[tot - 1] - cvx[tot - 2]) * (cvx[j] - cvx[tot - 2]) >= 0; --tot);
				cvx[tot++] = cvx[j];
			}
			int ret = tot - 1, l = 0, r = tot - 2, mid, k = que[i].id;
			while (l <= r) {
				mid = l + r >> 1;
				if (cvx[mid].slope(cvx[mid + 1]) <= p[k]) {
					ret = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			if (ret >= 0) {
				f[k] = min(f[k], cvx[ret].y + (dep[k] - cvx[ret].x) * p[k] + q[k]);
			}
		}
		for (int i = 0, j; i < (int)que.size(); i++) {
			if (j = que[i].id, que[i].range <= dep[w]) {
				f[j] = min(f[j], f[w] + (dep[j] - dep[w]) * p[j] + q[j]);
			}
		}
		que.clear();
		cvx.clear();
	
		for (int i = head[w]; i; i = nxt[i]) {
			if (dep[to[i]] > dep[w] && !vis[to[i]]) {
				solve(to[i], sz[to[i]]);
			}
		}	
	}	
private:
	inline int FindRoot(int w, int universe) {
		int ret = 0, ans;
		FindRoot(w, w, universe, ret, ans);
		return ret;
	}	
	inline void FindRoot(int w, int f, int universe, int &ret, int &ans) {
		int mx = 1; sz[w] = 1;
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				FindRoot(to[i], w, universe, ret, ans);
				sz[w] += sz[to[i]];
				mx = max(mx, sz[to[i]]);
			}
		}
		mx = max(mx, universe - sz[w]);
		if (!ret || mx < ans) {
			ans = mx;
			ret = w;
		}
	}
	inline void DFS(int w, int f, vector<Point> &ret) {
		ret.push_back(Point(dep[w], 0, w, dep[w] - len[w]));
		for (int i = head[w]; i; i = nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, ret);
			}
		}
	}
}DAC;

int main() {
	n = read(); read();
	for (int i = 2; i <= n; i++) {
		fa[i] = read();
		LL c = read(); AddEdge(fa[i], i);
		p[i] = read(); q[i] = read();
		len[i] = read();
		dep[i] = dep[fa[i]] + c;
	}
	fill(f, f + N, INF);
	f[1] = 0; dep[0] = -1;
	DAC.solve(1, n);
	for (int i = 2; i <= n; i++) {
		printf("%lld\n", f[i]);
	}
	return 0;
}

【日常小测】仰望星空

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf

解题报告

我们按照极角序来贪心匹配
不难发现这样一定有解

另外Dinic是不能求这种要求字典序最小的解的
似乎只能用最裸的匈牙利

Code

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

const int N = 1009;
const int M = 1000009;
const int INF = 1e9;
const double PI = acos(-1);

int n, R, D, S, T;
int in[N], ot[N], cnt_in, cnt_ot;
int head[N], nxt[M], to[M], mth[N], vis[N];
pair<double, int> arr[N];
struct Point{
	int x, y, ty;
	inline int dis(const Point &P) {
		return (x - P.x) * (x - P.x) + (y - P.y) * (y - P.y);
	}
}p[N];

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
} 

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool DFS(int w) {
	vis[w] = 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!mth[to[i]] || (!vis[mth[to[i]]] && DFS(mth[to[i]]))) {
			mth[to[i]] = w;
			mth[w] = to[i];
			return 1;
		} 
	}
	return 0;
}

inline int solve() {
	int ret = 0;
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (!mth[i]) {
			memset(vis, 0, sizeof(vis));
			ret += DFS(i);
		}
	}
	return ret;
}

inline void print(int w) {
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] == mth[w]) {
			vis[w] = vis[to[i]] = 1;
			printf("%d %d\n", w, mth[w]);
			return;
		} else if (!vis[to[i]]){
			print(mth[to[i]]);
		}
	}
}

int main() {
	n = read(); 
	R = read(); R *= R;
	D = read(); D *= D;
	S = 0; T = N - 1;
	for (int i = 1; i <= n; i++) {
		p[i].x = read();
		p[i].y = read();
		if (p[i].ty = p[i].dis(p[1]) > R) {
			in[++cnt_in] = i;
		} else {
			ot[++cnt_ot] = i;
		}
	}
	for (int ii = 1; ii <= cnt_in; ii++) {
		int i = in[ii], cnt_arr = 0;
		double mx = -PI, mn = PI;
		for (int jj = 1; jj <= cnt_ot; jj++) {
			int j = ot[jj];
			if (p[i].dis(p[j]) <= D) {
				double agl = atan2(p[j].y - p[i].y, p[j].x - p[i].x);
				mx = max(mx, agl);
				mn = min(mn, agl);
				arr[++cnt_arr] = make_pair(agl, j);
			}
		}
		if (mx - mn >= PI) {
			for (int j = 1; j <= cnt_arr; j++) {
				arr[j].first += arr[j].first < 0? PI * 2: 0;
			}
		}
		sort(arr + 1, arr + 1 + cnt_arr);
		for (int j = 1; j <= cnt_arr; j++) {
			AddEdge(i, arr[j].second);
		}
	}
	printf("%d\n", solve() << 1);
	memset(vis, 0, sizeof(vis));
	for (int ii = 1, i; i = in[ii], ii <= cnt_in; ii++) {
		if (mth[i] && !vis[i]) {
			print(i);
		}
	}
	return 0;
}

【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

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

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

【Codeforces 819B】Mister B and PR Shifts

相关链接

题目传送门:http://codeforces.com/contest/819/problem/B

解题报告

这题是今年SCOI D2T1的一部分

具体的做法就是如果$i$变成$i+1$,那么有多少$|p_i – i|$会增加和减少
对于每个$|p_i – i|$,“从增加变到减少 或 从减少变到增加” 只会进行一次
于是总的时间复杂度就是:$O(n)$的

Code

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

const int N = 1000009;

int n, p[N], chg[N], delta[2];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

int main() {
	n = read();
	LL cur = 0, ans, pos = 0;
	for (int i = 1; i <= n; i++) {
		p[i] = read();
		cur += abs(p[i] - i);
		delta[p[i] > i]++; 
		if (p[i] > i) {
			++chg[p[i] - i]; 
		} else {
			++chg[n - i + p[i]]; 
		}
		--chg[n - i + 1]; 
	}
	ans = cur;
	for (int i = 1; i < n; i++) {
		cur += delta[0] - delta[1];
		cur += abs(p[n - i + 1] - 1) - abs(p[n - i + 1] - n - 1);
		if (cur < ans) {
			ans = cur;
			pos = i;
		}
		delta[1] -= chg[i];
		delta[0] += chg[i];
	}
	cout<<ans<<' '<<pos<<endl;
	return 0;
}

【Codeforces 212B】Polycarpus is Looking for Good Substrings

相关链接

题目传送门:http://codeforces.com/contest/212/problem/B
中文题面:http://www.tsinsen.com/A1470

解题报告

这题你需要观察到一个非常重要的结论:

以字符串某个特定位置为开头的字符串,至多只有26个会产生贡献

于是我们就可以暴力枚举这$O(26n)$的字符串
然后去更新答案
时间复杂度:$O(26n \log q)$

Code

这份代码我写挫了
时间复杂度是:$O(676n \log q)$的

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

const int N = 1000009;
const int SGZ = 26;
const int M = 10009;

int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M];
vector<int> val;
char s[N], qy[SGZ]; 

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline int index(int x) {
	for (int l = 0, r = val.size() - 1, mid; l <= r; ) {
		mid = l + r >> 1;
		if (val[mid] == x) {
			return mid; 
		} else if (val[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	} 
	return -1;
}

int main() {
	scanf("%s", s);
	n = strlen(s);
	m = read();
	for (int i = 1; i <= m; i++) {
		scanf("%s", qy);
		int len = strlen(qy);
		for (int j = 0; j < len; j++) {
			q[i] |= 1 << qy[j] - 'a';
		}
		val.push_back(q[i]);
	}
	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());
	int last_position[SGZ];
	fill(last_position, last_position + SGZ, n);
	for (int i = n - 1; ~i; i--) {
		last_position[s[i] - 'a'] = i;
		for (int j = 0; j < SGZ; j++) {
			nxt[i][j] = last_position[j];
		}
	}
	memset(crt, -1, sizeof(crt));
	for (int i = 0; i < n; i++) {
		for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) {
			int np = n, c = -1;
			for (int k = 0; k < 26; k++) {
				if ((sta >> k & 1) == 0) {
					if (np > nxt[p][k]) {
						c = k;
						np = nxt[p][k];
					}
				}
			}
			if (~c) {
				sta |= 1 << c;
				p = np;
				crt[i][j] = sta;
				if (!i || crt[i - 1][j] != sta) {
					int idx = index(sta);
					if (~idx) { 
						ans[idx]++;
					}
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		printf("%d\n", ans[index(q[i])]);
	}
	return 0;
}

【Codeforces 734F】Anton and School

相关链接

题目传送门:http://codeforces.com/contest/734/problem/F
官方题解:http://codeforces.com/blog/entry/48397

解题报告

画一画维恩图便容易发现:$(a \ and \ b) + (a \ or \ b) = a + b$
所以$b_i + c_i = \sum\limits_{j = 1}^{n}{a_i + a_j} = na_i + \sum\limits_{j = 1}^{n}{a_j}$
于是有$\sum\limits_{i = 1}^{n}{a_i} = \frac{\sum\limits_{i = 1}^{n}{b_i + c_i}}{2n}$
最后加加减减搞一搞就可以求出$a_i$了

然后就是检查${a_i}$是否符合${b_i}$和${c_i}$
这个按二进制位枚举一下就可以了
总的时间复杂度是:$O(n \log \max(a_i))$的

Code

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

const int N = 200009;

int n, a[N], b[N], c[N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline bool check() {
	static int cnt[100];
	for (int i = 1; i <= n; i++) {
		for (int t = 0, v = a[i]; v; v >>= 1, ++t) {
			cnt[t] += v & 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		int tb = 0, tc = 0;
		for (int j = 0, cur = 1; j <= 30; j++, cur <<= 1) {
			tb += (a[i] & cur)? cnt[j] * cur: 0;
			tc += (a[i] & cur)? n * cur: cnt[j] * cur;
		}
		if (tb != b[i] || tc != c[i]) {
			return false;
		}
	}
	return true;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = b[i] = read();
	}
	LL sum = 0;
	for (int i = 1; i <= n; i++) {
		a[i] += (c[i] = read());
		sum += a[i];
	}
	if (sum % (n << 1)) {
		puts("-1");
		exit(0);
	}
	sum /= n << 1;
	for (int i = 1; i <= n; i++) {
		if ((a[i] -= sum) % n) {
			puts("-1");
			exit(0);
		} else {
			a[i] /= n;
		}
	}
	if (!check()) {
		puts("-1");
		exit(0);
	} 
	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

【日常小测】友好城市

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【AtCoder】[Grand Contest 013 B] Hamiltonish Path

相关链接

题目传送门:http://agc013.contest.atcoder.jp/tasks/agc013_b

解题报告

最开始想用$DFS$树来搞
然而$Corner \ Case$太多了,写不动啊_(:з」∠)_

最后还是看了题解
题解是使用的调整算法
如果某个端点还可以走,那就走进去
因为每条边至多访问两遍,每个点至多访问一次
所以复杂度是:$O(n + m)$的

Code

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

const int N = 100009;
const int M = N << 1;

int n, m, head[N], nxt[M], to[M], vis[N];
deque<int> ans;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; 
}

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif	
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		AddEdge(u, v);
		if (i == 1) {
			ans.push_back(u);
			ans.push_back(v);
			vis[u] = vis[v] = 1;
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.front()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_front(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.back()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_back(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	cout<<ans.size()<<endl;
	for (; !ans.empty(); ans.pop_front()) {
		printf("%d ", ans.front());
	}
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL ans;
  
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
  
int find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【BZOJ 2296】[POJ Challenge] 随机种子

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2296

解题报告

我们假设高位是$9876543201$,低$6$位随意
那么每一次加上$x$,导致高位至多增加$1$
所以一定有解,至于是多少倍?我们可以二分

Code

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

const LL MX = 9876543201999999;
const LL MN = 9876543201000000; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T = read(); T; T--) {
		LL x = read();
		if (!x) {
			puts("-1");
		} else {
			LL r = MX / x + 1, l = MN / x;
			while (l <= r) {
				LL mid = l + r >> 1;
				if (x * mid < MN) {
					l = mid + 1;
				} else if (x * mid > MX) {
					r = mid - 1;
				} else {
					printf("%lld\n", mid * x);
					break;
				}
			}
		}
	}
	return 0;
}

【POJ 3922】A simple stone game

相关链接

题目传送门:http://poj.org/problem?id=3922
神犇题解:http://www.cnblogs.com/jianglangcaijin/archive/2012/12/19/2825539.html

解题报告

根据$k = 1$的情况,我们发现在二进制下,我们取走最低位的$1$,对手取不走较高位的$1$
所以如果不是二的整次幂,那么先手必胜

再来看看$k = 2$的情况
根据$HINT$我们把每个整数拆成若干个不同、不相邻的斐波那契数之和,表示成二进制状态
之后跟据$k = 1$时的推论,我们取走最低位的$1$,对手不能直接取走较高位的$1$

先在我们看我们依赖拆分数列的哪些性质:

存在一种拆分使得选中的项的任意相邻两项超过$k$倍

于是我们尝试构造拆分数列$a_i$
我们设$b_i$为$a_1 \to a_i$能拼出的极长的前缀长度
不难发现$a_i = b_{i-1}+1, b_i=a_i+b_j$,其中$j$尽可能大,且$a_j k < a_i$

于是这题就做完啦
似乎这个问题还是博弈论里的一个经典问题,叫”$k$倍动态减法问题”
似乎某年国家集训队论文里还提出了另外的算法,对于某些数据会更优

Code

#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;

const int N = 10000000;

int n,k,x,y,a[N],b[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int t = 1, T = read(); t <= T; ++t) {
		n = read(); k = read();
		a[0] = b[0] = x = y = 0;
		while (a[x] < n) {
			a[x + 1] = b[x] + 1;
			for (++x; (LL)a[y + 1] * k < a[x]; ++y);
			b[x] = y? b[y] + a[x]: a[x];
		}
		if (a[x] == n) {
			printf("Case %d: lose\n", t);
		} else {
			int ans = 0;
			for (; n && x; --x) {
				if (n >= a[x]) {
					n -= a[x];
					ans = a[x];
				}
			}
			printf("Case %d: %d\n", t, ans);
		}
	}
	return 0;
}

【TopCoder SRM714】NAddOdd

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14408&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358475

解题报告

设$f(x)=\sum\limits_{i=1}^{x}{g(k+i)}$
那么奇偶讨论,可以得到递推式$f(x)=(f(\frac{x-k}{2})+\frac{x}{2})+(f(\frac{x}{2})+x)$
于是递归算$f(\frac{x-k}{2})$,$\sum\limits_{i=\frac{x-k}{2}+1}^{\frac{x}{2}}{g(i)}$暴力算
时间复杂度:$O(k \log^2 n)$

Code

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

class NAddOdd {
    public:
    	long long solve(long long L, long long R, int K) {
			return Cal(R - K, K) - Cal(L - 1 - K, K);
   		}
   	private:
   		inline LL Cal(LL n, int k) {
			if (n <= 0) {
				return 0;
			} else {
				LL ret = Cal((n - k) >> 1, k) << 1;
				ret += n + (n >> 1);
				for (LL i=((n-k)>>1)+1;i*2<=n;i++) {
					ret += g(i + k, k);
				}
				return ret;
			}
		}
		inline int g(LL x, int k) {
			LL ret = 0, w = x;
			while (w > k) {
				++ret;
				w = (((w&1)? (w+k): (w>>1)));
			} 
			return ret;
		} 
};

【TopCoder SRM714】Salesman

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14120&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358439

解题报告

设最终移动的范围为$[l,r]$
那么如果存在$r’ < r$且$sum_{l \to r’} \ge 0$,则$r’$优于$r$
所以我们可以枚举左端点,然后找到其对应的最优右端点

接下来就是区间内的路径规划问题
我们可以假设先走到左端点,那么剩下的东西的分配一定是尽量往左分配
这样就可以贪心了

Code

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

const int INF = 1e9;
const int N = 1e4;

int pfx[N],delta[N],pos[N],nxt[N];

class Salesman {
    public:
    	int minMoves(vector<int> ppos, vector<int> ddelta) {
    	    int n = ppos.size();
    	    for (int i=1;i<=n;i++) {
				pos[i] = ppos[i - 1];
				delta[i] = ddelta[i - 1];
			}
			int ans = INF;
			ans = min(ans, solve(n));
			for (int l=1,r=n;l<r;l++,r--) {
				swap(pos[l], pos[r]);
				swap(delta[l], delta[r]);
			}
			for (int i=1;i<=n;i++) {
				pos[i] = -pos[i];
			}
			ans = min(ans, solve(n));
			return ans;
   		}
   	private:
   		inline int solve(int n) {
			int mn = INF, mx = -INF, ret = INF;
			for (int i=1;i<=n;i++) {
				pfx[i] = pfx[i-1] + delta[i];
				if (delta[i] < 0) {
					mx = max(mx, i);
					mn = min(mn, i);
				}
			}   
			for (int i=n,j=n;i;i--) {
				if (delta[i] < 0) {
					j = i;
				}
				nxt[i] = j;
			}
			if (mn == INF) {
				return 0;
			}
			for (int l=1;l<=mn;l++) {
				for (int r=mx;r<=n;r++) {
					if (pfx[r] - pfx[l - 1] >= 0) {
						ret = min(ret, cal(l, r));	
						break;
					}
				}
			}
			return ret;
		}
		inline int cal(int l, int r) {
			int ret = pos[r] - pos[l] + abs(pos[l]), ans = INF;
			int cry = 0, ned = 0, ptn = 0;
			for (int i=l;i<=r;i++) {
				if (delta[i] >= 0) {
					cry += delta[i];
					if (cry >= ned && ned) {
						cry -= ned;
						ret += max(0, pos[i] - ptn) << 1;
						ned = 0;
					}
				} else if (delta[i] < 0) {
					if (!ned && cry >= -delta[i]) {
						cry += delta[i];
					} else {
						if (!ned) {
							ptn = max(ptn, pos[i]);
						} 
						ned -= delta[i];
					}
				}
				
				ans = min(ans, ret + max(0, pos[r] - (ned? ptn: pos[nxt[i+1]])));
			}
			return ans;
		}
};

【BZOJ 4828】[HNOI2017] 大佬

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4828

解题报告

先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数

最后回答每个询问的时候
用个双指针扫一扫

Code

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

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int t, LL sum) {
	if (t > MX) return;
	else {
		DFS(t + 1, sum);
		if (ispri[t]) {
			for (;sum*=t,sum<=1e8;) {
				itm[++tot].first = sum;
				DFS(t + 1, sum);
			}
		}
	}
}

inline int cal(int x) {
	int ret = x + 1;
	for (int i=min(MX,x-1),cnt,tmp;i;i--) {
		if (x % i) continue;
		cnt = i + 1; tmp = x;
		for (int j=i;j>1&&tmp>1;j--) {
			while (tmp % j == 0) {
				tmp /= j;
				++cnt;
			}
		}
		if (tmp == 1) {
			ret = min(ret, cnt);
		} else {
			break;
		}
	}
	return ret;
}

int main() {
	n = read(); m = read(); mc = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	for (int j=1;j<=n;j++) {
		w[j] = read();
	}
	//DP最多空出来的天数 
	memset(f, -1, sizeof(f));
	f[1][mc] = 0;
	for (int i=1;i<=n;i++) {
		for (int j=a[i];j<=mc;j++) {
			if (f[i][j] == -1) continue;
			int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
			if (t1 >= 0) {
				f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
			}
			if (t2 >= 0) {
				f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
			}
		}
	}
	MX = -1; 
	for (int j=2;j<=n+1;j++) {
		for (int i=0;i<=mc;i++) {
			MX = max(MX, f[j][i]);
		}
	} 
	//搞出每一个物品的最小花费 
	for (int j=2;j<=100;j++) {
		ispri[j] = 1;
		for (int i=2;i*i<=j;i++) {
			if (j % i == 0) {
				ispri[j] = 0;
			}
		}
	}
	DFS(1, 1); 
	for (int i=1;i<=tot;i++) {
		itm[i].second = cal(itm[i].first);
	}
	itm[++tot] = make_pair(0, 0);
	sort(itm+1, itm+1+tot);
	//对于每个询问用一个双端队列
	for (int tt=1;tt<=m;tt++) {
		int C = read(), ans = 0;
		for (int i=tot,pfx=1,cur=-1e9;i;i--) {
			while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
				cur = max(cur, itm[pfx].first - itm[pfx].second);
				pfx++;
			}
			if (cur + itm[i].first - itm[i].second >= C - MX) {
				ans = 1; 
				break;
			}
		}
		printf("%d\n",ans);
	} 
	return 0;
}

【TopCoder SRM713】PowerEquation

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

【BZOJ 4826】[HNOI2017] 影魔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html

解题报告

这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$

至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
   
const int N = 200009;
const int NN = N << 1;
const int M = 18;
   
int n,m,p1,p2,val[N];
LL ans[N];
vector<int> q1[N];
vector<pair<int,int> > q2[N],q3[N];
struct Query{int l,r,id;}q[N];
   
inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;}
inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;}
   
inline int read() {
    char c=getchar(); int f=1,ret=0;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
   
class Sparse_Table{
    int mx[M][N],pos[M][N],lg[N];
    public:
        inline void init(int *arr) {
            for (int i=1;i<=n;i++) {
                mx[0][i] = arr[i];
                pos[0][i] = i;
            }
            for (int l=1,j=1;l*2<=n;j++,l<<=1) {
                for (int i=1;i<=n-l;i++) {
                    if (mx[j-1][i] >= mx[j-1][i+l]) {
                        pos[j][i] = pos[j-1][i];
                        mx[j][i] = mx[j-1][i];
                    } else {
                        pos[j][i] = pos[j-1][i+l];
                        mx[j][i] = mx[j-1][i+l];
                    }
                }
            }
            for (int i=2;i<=n;i++) {
                lg[i] = lg[i>>1] + 1;
            }
        }
        inline int query(int l, int r) {
            int t = lg[r-l+1], j = 1 << t;
            if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l];
            else return pos[t][r-j+1]; 
        }
}ST;
   
void solve(int l, int r) {
    if (l == r - 1) {
        return;
    } else {
        int pos = ST.query(l+1, r-1);
        if (l) q1[pos].push_back(l);
        if (r <= n) q1[r].push_back(pos);
           
        if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1));
        if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1));
           
        solve(l, pos);
        solve(pos, r);
    }
}
   
class Segment_Tree{
    int cnt; LL AnsTmp;
    struct Node{
        Node *ch[2];
        int len;
        LL sum,tag;
    }p[NN],*root; 
    public:
        inline void init() {
            cnt = 0;
            build(root, 1, n);
        }
        inline void modify(int pos, int delta) {
            Node *w = root;
            int  l = 1, r = n, mid;
            while (l <= r) {
                w->sum += delta;
                if (l == r) break;
                mid = l + r + 1 >> 1;
                if (pos < mid) w = w->ch[0], r = mid - 1;
                else w = w->ch[1], l = mid;
            }
        }
        inline void modify(int l, int r, int delta) {
            modify(root, 1, n, l, r, delta);
        }
        inline LL query(int l, int r) {
            AnsTmp = 0;
            query(root, 1, n, l, r);
            return AnsTmp;
        }
    private:
        inline void pushdown(Node *w) {
            w->ch[0]->sum += w->ch[0]->len * w->tag;
            w->ch[1]->sum += w->ch[1]->len * w->tag;
            w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag;
            w->tag = 0;
        }
        void query(Node *w, int l, int r, int L, int R) {
            if (L <= l && r <= R) {
                AnsTmp += w->sum;
            } else {
                if (w->tag) pushdown(w);
                int mid = l + r + 1 >> 1;
                if (L < mid) query(w->ch[0], l, mid-1, L, R);
                if (mid <= R) query(w->ch[1], mid, r, L, R);
            }
        }
        void modify(Node *w, int l, int r, int L, int R, int delta) {
            if (L <= l && r <= R) {
                w->sum += (LL)delta * w->len;
                w->tag += delta;
            } else {
                if (w->tag) pushdown(w);
                int mid = r + l + 1 >> 1;
                if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta);
                if (mid <= R) modify(w->ch[1], mid, r, L, R, delta);
                w->sum = w->ch[0]->sum + w->ch[1]->sum;
            }
        }
        void build(Node *&w, int l, int r) {
            w = &p[++cnt];
            w->len = r - l + 1;
            w->sum = w->tag = 0; 
            w->ch[0] = w->ch[1] = 0;
            if (l < r) {
                int mid = l + r + 1 >> 1;
                build(w->ch[0], l, mid-1);
                build(w->ch[1], mid, r);
            }
        }
}SEG;
   
int main() {
    n = read(); m = read();
    p1 = read(); p2 = read();
    for (int i=1;i<=n;i++) {
        val[i] = read();
    }
    ST.init(val); 
    solve(0, n+1); 
    for (int i=1;i<=m;i++) {
        q[i].l = read(); 
        q[i].r = read();
        q[i].id = i;
    }
    sort(q+1, q+1+m, cmp1);
    SEG.init();
    for (int i=1,pos=0;i<=m;i++) {
        while (pos < q[i].r) {
            pos++;
            for (int j=0;j<q1[pos].size();j++) {
                SEG.modify(q1[pos][j], p1);
            }
            for (int j=0;j<q2[pos].size();j++) {
                SEG.modify(q2[pos][j].first, q2[pos][j].second, p2);
            }
        }
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    sort(q+1, q+1+m, cmp2);
    SEG.init(); 
    for (int i=1,pos=n+1;i<=m;i++) {
        while (pos > q[i].l) {
            pos--;
            for (int j=0;j<q3[pos].size();j++) {
                SEG.modify(q3[pos][j].first, q3[pos][j].second, p2);
            }
        } 
        ans[q[i].id] += SEG.query(q[i].l, q[i].r);
    }
    for (int i=1;i<=m;i++) {
        printf("%lld\n",ans[i]);
    }
    return 0;
}