AtCoder Beginner Contest 150
https://atcoder.jp/contests/abc150
def都蛮不错的
D - Semi Common Multiple
先推一下:\(x=a_i\times(p+0.5)\rightarrow x=\frac{a_i}2(2p+1)\rightarrow x=\frac{lcm}2(2p+1)\)
所以 \(x\) 就是 \(\frac{lcm}2, \frac{3lcm}2, \frac{5lcm}2, ...\) 这样以 \(\frac{lcm}2\) 为首项,\(lcm\) 为公差的等差数列,其项数就是答案。
注意最终答案会爆 longlong,所以要在\(lcm\)那里特判一下
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
ll n, m, a[N];
ll LCM (ll x, ll y) {
return x / __gcd (x, y) * y;
}
int main () {
cin >> n >> m;
ll lcm = 1;
for (int i = 1; i <= n; i++) cin >> a[i], lcm = LCM (lcm, a[i]);
// cout << lcm << endl;
if (lcm < 0 || lcm / 2 > m) { //爆ll
cout << 0;
return 0;
}
for (int i = 1; i <= n; i++) {
if (((lcm / 2) / (a[i] / 2)) % 2 == 0) {
cout << 0 << endl;
return 0;
}
}
cout << (m - lcm / 2) / lcm + 1 << endl; //可能会爆longlong
//除去偶数
}
// 1-m中有多少个 x,满足 x=ai*(p+0.5), i:1-n, p可变,p>=0
//lcm/2, 3lcm/2, 5lcm/2, ...
//应该是爆Longlong了
E - Change a Little Bit
手动模拟一下,发现只需要算一种答案,其他都是对称的,即总和为 \(2^n\times sum\)
考虑怎么算 \(sum\)。
含义为考虑到第 \(i\) 位,有 \(j\) 位不同的总贡献,其中 \(j+1\) 为权值
其中上面展开的那一步用到了二项式定理:
考虑把含 \(j\) 的那一项展开。
根据吸收恒等式:
然后就能直接 \(O(n)\) 计算了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
ll a[N], pw[N], sum;
int n;
int main () {
cin >> n;
pw[0] = 1;
for (int i = 1; i <= n; i++) cin >> a[i], pw[i] = (pw[i-1] * 2) % mod;
sort (a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
ll dx = pw[n-i] + (n - i) % mod * pw[n-i-1];
dx %= mod;
(sum += pw[i-1] * a[i] % mod * dx % mod) %= mod;
}
// cout << sum << ' ';
cout << (sum * pw[n]) % mod << endl;
}
//T3: 2^5 * 8416
//sort之后:
//非常好组合数题
//考了一个吸收恒等式
F - Xor Shift
先进行一下式子变换:\(b_i=a_{(i+k\mod\,n)}\bigoplus x\rightarrow b_i\bigoplus a_{(i+k\mod\,n)}= x\)
即 \(a_{(i+k\mod\,n)}\bigoplus b_0=a_{(i+k+1\mod\,n)}\bigoplus b_1=...\),
即 \(a_{(i+k\mod\,n)}\bigoplus a_{(i+k+1\mod\,n)}=b_0\bigoplus b_1=...\)
因此可以令 \(c_i=a_i\bigoplus a_{i+1}, d_i=b_i\bigoplus b_{i+1}\)
即 \(c_i\) 与 \(d_i\) 轮换匹配,等价于把 \(c_i\) 复制一倍,\(d_i\) 在 \(c_i\) 上的长度为 \(n\) 的匹配有多少种。
这里我们采用 \(Z\) 函数来做,原理看这里————
z函数:https://oi-wiki.org/string/z-func/ (比KMP好理解)
利用 \(z_i\) 的含义(\(s[i,n-1]\) 与 \(s\) 的前缀匹配的最大长度),把 \(d_i\) 放在 \(s[0,n-1]\),\(s[n]=-1\) 作为间隔。\(c_i\) 复制两遍放在 \(s[n+1,3n]\)。
答案即为 \(s[n+1,2n]\) 中, \(z_i=n\) 即为符合条件的值。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int a[N], b[N], c[N], d[N], s[N*3], n;
vector<int> ExKMP (int *s, int n) {
//int n = s.size ();
vector<int> z(n);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i <= r && z[i-l] < r - i + 1) z[i] = z[i-l];
else {
z[i] = max (0, r - i + 1);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i] ++; //暴力匹配
}
if (i + z[i] > r) l = i, r = i + z[i] - 1; //更新l,r
}
return z;
}
int main () {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
for (int i = 0; i < n; i++) c[i] = a[i] ^ a[(i+1)%n], d[i] = b[i] ^ b[(i+1)%n];
for (int i = 0; i < n; i++) s[i] = d[i], s[i+n+1] = s[i+2*n+1] = c[i];
s[n] = -1;
vector<int> z(n * 3);
z = ExKMP (s, 3 * n);
for (int i = n + 1; i <= 2 * n; i++) {
if (z[i] == n) cout << i - n - 1 << ' ' << (a[i-n-1] ^ b[0]) << endl;
}
}
//[0,n-1]放d, [n]放-1作为间隔
//[n+1,2n]放c,[2n+1,3n]再复制一遍c
//[n+1,2n]中,z[i]=n即为符合条件的值
- Beginner AtCoder Contest 150beginner atcoder contest 150 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 315 beginner atcoder contest 334