AtCoder Beginner Contest 152
https://atcoder.jp/contests/abc152
F我看了半天,编码方式那里还算是感觉比较玄乎,这题确实妙。
D - Handstand 2
只需记录两端数字即可,不要想太复杂。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, sum, a[10][10];
ll pw[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int main () {
cin >> n;
for (int i = 1; i <= n; i++) a[i / pw[(int)to_string (i).size () - 1]][i % 10] ++;
for (int i = 1; i < 10; i++) {
for (int j = 1; j < 10; j++) {
sum += a[i][j] * a[j][i];
}
}
cout << sum;
}
//只存首尾
E - Flatten
答案是
\[\sum_{i=1}^n\frac{lcm}{a_i}
\]
但是直接乘来求 \(lcm\) 会爆 longlong,因此换一种方式存:记录素因数的最大次数,然后就出来了。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 1e4 + 5, mod = 1e9 + 7, M = 1e6 + 5;// M = 78499 + 5; //1e6以内素数的个数
int n, a[N], cnt[M];
ll sum;
ll qmi(ll a, ll k, ll p){
ll res = 1;
while(k){
if(k & 1)
res = (ll)res * a % p;
a = (ll)a * a % p;
k >>= 1;
}
return res;
}
int main () {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
// cout << a[i] << ":\n";
int t = a[i];
for (int j = 2; j * j <= t; j++) {
if (t % j == 0) {
int tt = 0;
while (t % j == 0) t /= j, tt++;
cnt[j] = max (tt, cnt[j]);
}
}
if (t > 1) cnt[t] = max (cnt[t], 1);
}
ll mul = 1;
for (int i = 1; i < M; i++) {
while (cnt[i]--) (mul *= i) %= mod;
}
for (int i = 1; i <= n; i++) (sum += mul % mod * qmi (a[i], mod - 2, mod)) %= mod;
cout << sum;
}
//d/ai求和
//对ai进行素因数分解
F - Tree and Constraints
容斥 + 状压。
边的处理那里其实还是不太清楚。
https://www.luogu.com.cn/blog/subtlemaple/solution-at-abc152-f
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 55;
int h[N], e[N*2], ne[N*2], idx;
ll n, m, d[N], st[N]; //di为限制条件, st[i]当前边状态
void add (int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs (int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
d[j] = d[u] | (1ll << (j - 1)); //根节点到 x 经过的边的状压数值
dfs (j, u);
}
}
ll count (ll S) { //f(S) = 2^{n-1-|S|}
ll cnt = __builtin_popcountll (S), T = 0; //T为并集
for (int i = 0; i < m; i++) {
if (S & (1ll << i)) {
T |= st[i];
}
}
ll sum = (1ll << (n - 1 - __builtin_popcountll (T)));
if (cnt & 1) sum *= -1ll; //容斥系数
return sum;
}
int main () {
memset (h, -1, sizeof h);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
add (a, b), add (b, a);
}
cin >> m;
dfs (1, -1);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
st[i] = d[a] ^ d[b]; //经典的树上异或性质:x到y的路径上的边的状压数值
}
ll ans = 0;
//0的状态是全集
for (ll i = 0; i < (1ll << m); i++) ans += count (i);
cout << ans << endl;
}
- Beginner AtCoder Contest 152beginner atcoder contest 152 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