【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

相关链接

题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_f

解题报告

我们写出使答案最大且值最小的序列,不难发现这是一个斐波那契数列
进一步发现,这条主链的每一个点只会引申出一条支链,且支链不会再分
所以我们可以暴力算出了$\log n$条链,共$\log ^ 2 n$对数,然后暴力算贡献

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
const int LOG = 100;
 
vector<pair<LL, LL> > num[LOG];
 
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 solve(LL A, LL B) {
	if (A < num[2][0].first || B < num[2][0].second) {
		printf("1 %d\n", A * B % MOD);
		return;
	}
	for (int i = 2; i < LOG; i++) {
		if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
			int cnt = 0;
			for (int j = 0; j < (int)num[i].size(); j++) {
				LL a = num[i][j].first, b = num[i][j].second;
				cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
				cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
			}
			printf("%d %d\n", i, cnt);
			return;
		}
	}
}
 
inline void prework() {
	num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < (int)num[i - 1].size(); ++j) {
			LL a = num[i - 1][j].first, b = num[i - 1][j].second;
			num[i].push_back(make_pair(b, a + b));
		}
		LL a = num[i - 1][0].first, b = num[i - 1][0].second;
		num[i].push_back(make_pair(a + b, 2 * a + b));
	}
}
 
int main() {
	prework();
	for (int T = read(); T; T--) {
		LL A = read(), B = read();
		solve(min(A, B), max(A, B));
	}
	return 0;
}

【BZOJ 2852】强大的区间

相关链接

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

解题报告

设最终区间包含的数为$t$
那么我们就是要求解这个不等式:$ka \le t \le kb$
我们分两种情况讨论:

1. $\lfloor a \rfloor \ne \lfloor b \rfloor$

这样的话,显然答案为$k = 1$

2. $\lfloor a \rfloor = \lfloor b \rfloor$

这样的话,我们先可以刨开$a,b$的整数部分
于是答案变为这个不等式的解:$s \cdot \frac{1}{b – \lfloor a \rfloor} \le k \le s \cdot \frac{1}{a – \lfloor a \rfloor}$

我们发现最后的式子与原问题形式相同,于是可以递归求解
更进一步,我们每次将较大的数减去较小的数,然后交换位置,这是典型的类欧几里得算法
于是我们就可以在:$O(\log n)$的时间复杂度内递归求解原问题了

至于代码,显然需要用高精度
但我不会py QwQ

【日常小测】超级绵羊异或

题目大意

求$(b)\oplus(b+a)\oplus(b+2a)\oplus\cdots\oplus(b+(n-1)a)$
其中$n,a,b\le10^9$

解题报告

因为是二进制,所以我们每一位分开考虑
又因为数$a$二进制下第$k$位的奇偶性与$a>>(k-1)$的奇偶性相同
所以对于第$k$位,我们实际是要求$\sum\limits_{x=0}^{n-1}{\left\lfloor {\frac{{ax + b}}{{{2^k}}}} \right\rfloor}$,我们将其一般化:求解$f(a,b,c,n)=\sum\limits_{x=0}^{n}{\left\lfloor {\frac{{ax + b}}{{{c}}}} \right\rfloor}$

设$s(x)=\sum\limits_{i=1}^{x}{i}$。为了只讨论$a,b<c$的情况,我们先来预处理一下:

  1. 若$a \ge c$那么显然$f(a,b,c,n) = f(a \% c,b,c,n) + \lfloor\frac{a}{c}\rfloor \cdot s(n)$
  2. 若$b \ge c$那么显然$f(a,b,c,n) = f(a,b\%c,c,n) + \lfloor\frac{b}{c}\rfloor \cdot n$

之后我们就可以施展膜法了:
设$m=\lfloor\frac{an+b}{c}\rfloor$
那么原式$=\sum\limits_{x=0}^{n}{\sum\limits_{y=0}^{m}{[y<\lfloor\frac{ax+b}{c}\rfloor]}}$
把$y<\lfloor\frac{ax+b}{c}\rfloor$提出来,可以化简:
$y<\lfloor\frac{ax+b}{c}\rfloor = c(y+1) \le ax+b = cy+c-b-1<ax=x>\lfloor\frac{cy+c-b-1}{a}\rfloor$
那么原式$=\sum\limits_{y=0}^{m}{\sum\limits_{x=0}^{n}{[x>\lfloor\frac{cy+c-b-1}{a}\rfloor]}}=n(m+1)-\sum\limits_{y=0}^m{\lfloor\frac{cy+c-b-1}{a}\rfloor}$
相当于$f(a,b,c,n)=n(m+1)-f(c,c-b\%c-1,a\%c,m)$
窝萌发现,这货的形式简直和辗转相处搞$gcd$一模一样
于是这货的复杂度也是$O(\log n)$的

当然这题还有一种数形结合的推法
推出来式子略有不同,不过时间复杂度仍然为$O(\log n)$
不过本文这种推法似乎更优?据敦敦敦讲,这货可以推广到高维
但我不会 QwQ

Code

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

inline int read() {
	char c=getchar(); int ret=0,f=1;
	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;
}

LL cal(LL a, LL b, LL c, LL n) { 
	if (a >= c) return (((n-1)*n/2)*(a/c)&1) ^ cal(a%c, b, c, n);
	if (b >= c) return (n * (b/c) & 1) ^ cal(a, b%c, c, n);
	if (!a) return (b/c) * n & 1;
	LL nw = (a * (n - 1) + b) / c; 
	return ((n-1) * nw & 1) ^ cal(c, c - b - 1, a, nw);
}

int main() {
	for (int T=read(),a,b,n;T;T--) {
		n = read(); b = read(); 
		a = read(); LL c = 1, ans = 0;
		if (!b) {printf("%d\n",(n&1)?a:0); continue;} 
		for (int i=0;i<=60;i++,c<<=1) 
			ans += cal(a, b, c, n) * c;
		printf("%lld\n",ans);
	}
	return 0;
}