链接:https://codeforces.com/gym/104090
A. Modulo Ruins the Legend
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
i64 d = exgcd(b, a % b, x, y);
i64 t = x;
x = y;
y = t - (a / b) * y;
return d;
}
void solve() {
i64 n, m;
cin >> n >> m;
vector<i64> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
i64 sum = accumulate(A.begin(), A.end(), 0LL) % m;
i64 m1 = n % m;
i64 m2 = n * (n + 1) / 2 % m;
i64 s = 0, d = 0, a = 0, b = 0;
i64 m0 = exgcd(m1, m2, s, d);
i64 m3 = exgcd(m0, m, a, b);
s = s * a % m;
d = d * a % m;
i64 t = (m - sum + m3 - 1) / m3;
cout << (t * m3 + sum) % m << '\n' << (s * t % m + m) % m << ' ' << (d * t % m + m) % m << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
D. Money Game
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
double sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
}
double tmp = sum / (n + 1);
cout << tmp * 2 << ' ';
for (int i = 1; i < n; i++) {
cout << tmp << ' ';
}
cout << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cout << fixed << setprecision(12);
int tt = 1;
//cin >> tt;
while (tt--) {
solve();
}
return 0;
}
F. Da Mi Lao Shi Ai Kan De
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
void solve() {
int n;
cin >> n;
set<string> mp;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
bool ok = 0;
for (int j = 0; j < k; j++) {
string s;
cin >> s;
for (int p = 0; p + 2 < (int) s.size(); p++) {
if (s[p] == 'b' && s[p + 1] == 'i' && s[p + 2] == 'e' && !mp.count(s)) {
mp.insert(s);
cout << s << '\n';
ok = 1;
break;
}
}
}
if (!ok) {
cout << "Time to play Genshin Impact, Teacher Rice!" << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
for (int _ = 1; _ <= tt; _++) {
solve();
}
return 0;
}
G. Subgraph Isomorphism
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
static constexpr int p[2] = {223333333, 773333333};
static constexpr int mod[2] = {1000000033, 1000002233};
using Hash = pair<i64, i64>;
#define x first
#define y second
void solve() {
int n, m;
cin >> n >> m;
vector<vector<int>> g(n + 1);
vector<int> deg(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
if (m == n - 1) {
cout << "YES" << '\n';
return;
}
if (m > n) {
cout << "NO" << '\n';
return;
}
queue<int> q;
vector<bool> vis(n + 1);
for (int i = 1; i <= n; i++) {
if (deg[i] == 1) {
q.push(i);
}
}
int SIZE = n;
while (!q.empty()) {
int cur = q.front();
q.pop();
vis[cur] = 1;
SIZE--;
for (auto nex : g[cur]) {
if (!vis[nex] && --deg[nex] == 1) {
q.push(nex);
}
}
}
vector<i64> sz(n + 1);
auto TreeHash = [&](int root) {
function<Hash(int, int)> dfs = [&](int cur, int pre) {
Hash res;
sz[cur] = 1;
vector<Hash> s;
for (auto nex : g[cur]) {
if (vis[nex] && nex != pre) {
s.push_back(dfs(nex, cur));
sz[cur] += sz[nex];
}
}
sort(s.begin(), s.end(), greater<>());
for (auto si : s) {
res.x = (res.x * p[0] + si.x) % mod[0];
res.y = (res.y * p[1] + si.y) % mod[1];
}
res.x = (res.x * p[0] + sz[cur]) % mod[0];
res.y = (res.y * p[1] + sz[cur]) % mod[1];
return res;
};
return dfs(root, 0);
};
vector<Hash> h;
int pre = 0;
int cur = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cur = i;
break;
}
}
for (int i = 0; i < SIZE; i++) {
h.push_back(TreeHash(cur));
int now = 0;
for (auto nex : g[cur]) {
if (!vis[nex] && nex != pre) {
now = nex;
break;
}
}
pre = cur;
cur = now;
}
for (int i = 0; i < SIZE; i++) {
if (h[i] != h[(i + 2) % SIZE]) {
cout << "NO" << '\n';
return;
}
}
cout << "YES" << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
K. Master of Both
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int N = 26;
constexpr int M = 2E6;
i64 cnt[M + 10];
i64 add;
i64 num[N][N];
i64 ed[M + 10];
class Trie {
public:
int tot;
vector<vector<int>> t;
Trie(const int &n = 2E6) : t(n, vector<int>(N)), tot(0) {}
inline void insert(const string &s) {
int SIZE = s.size();
int u = 0;
for (int i = 0; i < SIZE; i++) {
int c = s[i] - 'a';
for (int j = 0; j < N; j++) {
if (c != j && t[u][j]) {
num[c][j] += cnt[t[u][j]];
}
}
if (t[u][c] == 0) {
t[u][c] = ++tot;
}
u = t[u][c];
cnt[u]++;
}
ed[u]++;
add += cnt[u] - ed[u];
}
};
void solve() {
int n, q;
cin >> n >> q;
Trie tree;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
tree.insert(s);
}
for (int i = 0; i < q; i++) {
string s;
cin >> s;
i64 ans = 0;
for (int j = 0; j < N; j++) {
for (int k = j; k < N; k++) {
ans += num[s[j] - 'a'][s[k] - 'a'];
}
}
cout << ans + add << '\n';
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
for (int _ = 1; _ <= tt; _++) {
solve();
}
return 0;
}
标签:std,Contest,int,Regional,Programming,cin,i64,++,using
From: https://www.cnblogs.com/kiddingma/p/16969596.html