CLB

3491

CLB
9个月前

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 6e5 + 10, M = N * 32;

int cnt, trie[M][2], rt[N];

int n, m;

void insert(int p, int x) {
for (int i = 30; i >= 0; i--)
trie[p][x >> i & 1] = ++cnt, p = cnt;
}

void merge(int &x, int y) {
if (!x) { x = y; return;}
if (!y) return;
merge(trie[x][0], trie[y][0]);
merge(trie[x][1], trie[y][1]);
}

int calc(int l, int r, int x) {
int ans = 0;
for (int i = 30; i >= 0; i--) {
int p = x >> i & 1;
if (trie[l][p ^ 1] != trie[r][p ^ 1]) ans += (1 << i), l = trie[l][p ^ 1], r = trie[r][p ^ 1];
else if (trie[r][p]) l = trie[l][p], r = trie[r][p];
else break;
}
return ans;
}

int main() {
rt[0] = ++cnt, insert(rt[0], 0);
cin >> n >> m; int now = 0;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x); now ^= x;
rt[i] = ++cnt, insert(rt[i], now);
merge(rt[i], rt[i - 1]);
}
while (m--) {
char s[5]; scanf("%s", s);
if (s[0] == 'A') {
int x; scanf("%d", &x); now ^= x;
rt[++n] = ++cnt; insert(rt[n], now);
merge(rt[n], rt[n - 1]);
}
else {
int l, r, x; scanf("%d%d%d", &l, &r, &x);
x ^= now;
if (r == 1) { printf("%d\n", x); continue;}
int ans = calc(l > 1 ? rt[l - 2] : rt[l - 1], rt[r - 1], x);
printf("%d\n", l > 1 ? ans : max(ans, x));
}
}
return 0;
}


CLB
9个月前

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 4e4 + 10, M = 5e4 + 10, K = 210;
int n, m, q, a[N], b[N];
int get(int x) {
int l = 1, r = m, mid, ans;
while (l <= r) {
mid = (l + r) >> 1;
if (b[mid] <= x) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}

int cnt, L[K], R[K], p[N];
//s[K][N] 前缀和
//nxt[N][10] 倍增
//zs[K][N] 块头到某个点的众数，num[K][N]个数

int s[K][N], nxt[N][10], head[K][N], zs[K][N], num[K][N];

int last[N], sum[N];

bool vis[N]; int tp, sta[N];

int getl(int now) {
int sum = 1;
for (int j = 8; j >= 0; j--)
if (nxt[now][j]) now = nxt[now][j], sum += (1 << j);
return sum;
}

int getr(int now, int y) {
if (!now || now > y) return 0;
int sum = 1, p = 1;
while (p > 0) {
if (!nxt[now][p - 1]) p--;
else {
if (nxt[now][p - 1] <= y) now = nxt[now][p - 1], sum += 1 << (p - 1), p++;
else p--;
}
}
return sum;
}

int main() {
freopen("2.in", "r", stdin);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1); m = 1;
for (int i = 2; i <= n; i++)
if (b[i] != b[i - 1]) b[++m] = b[i];
for (int i = 1; i <= n; i++) a[i] = get(a[i]);
int block = 3, cnt = (n - 1) / block + 1;
for (int i = 1; i <= cnt; i++) {
L[i] = R[i - 1] + 1;
R[i] = R[i - 1] + block;
if (i == cnt) R[i] = n;
for (int j = L[i]; j <= R[i]; j++) p[j] = i;
}
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= m; j++) s[i][j] = s[i - 1][j], last[j] = sum[j] = 0;
for (int j = L[i]; j <= R[i]; j++) {
s[i][a[j]]++;
if (head[i][a[j]] == 0) head[i][a[j]] = j;
if (last[a[j]]) nxt[last[a[j]]][0] = j;
last[a[j]] = j;
}
int maxx = 0;
for (int j = L[i]; j <= n; j++) {
sum[a[j]]++;
if ((sum[a[j]] > sum[maxx]) || (sum[a[j]] == sum[maxx] && a[j] < maxx)) maxx = a[j];
zs[i][j] = maxx; num[i][j] = sum[maxx];
}
}
for (int j = 1; j <= 8; j++)
for (int i = 1; i <= n; i++)
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
int lastans = 0;
for (int i = 1; i <= q; i++) {
int x, y; scanf("%d%d", &x, &y);
x = (x + lastans - 1) % n + 1;
y = (y + lastans - 1) % n + 1;
if (x > y) swap(x, y);
int l = L[p[x]] == x ? p[x] : p[x] + 1;
int r = R[p[y]] == y ? p[y] : p[y] - 1;
if (l > r) {
int maxx = 0, hh;
if (p[x] == p[y]) {
for (int i = x; i <= y; i++)
if (!vis[a[i]]) {
vis[a[i]] = 1; sta[++tp] = a[i];
int now = i, sum = getr(now, y);
if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
}
}
else {
for (int i = x; i <= y; i++) {
if (vis[a[i]]) continue;
vis[a[i]] = 1; sta[++tp] = a[i];
int sum = 0, now = i;
if (i <= R[p[x]]) sum += getl(now);
sum += getr(now, y);
if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
}
}
printf("%d\n", lastans = b[hh]);
}
else {
int p1 = zs[l][y], s1 = num[l][y];
if (L[p[x]] == x) { printf("%d\n", lastans = b[p1]); continue;}
int maxx = 0, hh;
for (int i = x; i < L[l]; i++) {
if (vis[a[i]]) continue;
if (a[i] == p1) {s1++; continue;}
vis[a[i]] = 1; sta[++tp] = a[i];
int sum = s[r][a[i]] - s[l - 1][a[i]], now;
now = i; sum += getl(now);
if (y != R[p[y]]) now = head[p[y]][a[i]], sum += getr(now, y);
if (sum > maxx || (sum == maxx && hh > a[i])) maxx = sum, hh = a[i];
}
if (s1 > maxx || (s1 == maxx && p1 < hh)) printf("%d\n", lastans = b[p1]);
else printf("%d\n", lastans = b[hh]);
}
while (tp) vis[sta[tp--]] = 0;
}
return 0;
}


CLB
9个月前

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
//a[i]表示1 ~ i-1有多少个比b[i]小的
//1 ~ i-1 > b[i] = i - 1 - a[i]
//i+1 ~ n  < b[i] = b[i] - 1 - a[i]
//i+1 ~ n  > b[i] = n - b[i] - (i - 1 - a[i]) = n - i + 1 + a[i] - b[i]
int n, /* a[N], b[N],*/ c[N];

void add(int x) {
for (; x <= n; x += x & -x) c[x]++;
}
int get(int x) {
int s = 0;
for (; x; x -= x & -x) s += c[x];
return s;
}

int main() {
cin >> n;
/*  for (int i = 1; i <= n; i++) {
scanf("%d", &b[i]);
a[i] = get(b[i] - 1);
}
LL s1 = 0, s2 = 0;
for (int i = 2; i < n; i++) {
s1 += 1ll * (i - 1 - a[i]) * (n - i + 1 + a[i] - b[i]);
s2 += 1ll * a[i] * (b[i] - 1 - a[i]);
}*/
LL s1 = 0, s2 = 0;
for (int i = 1; i <= n; i++) {
int b; scanf("%d", &b);
int a = get(b - 1);
s1 += 1ll * (i - 1 - a) * (n - i + 1 + a - b);
s2 += 1ll * a * (b - 1 - a);
}

cout << s1 << " " << s2 << endl;
return 0;
}


CLB
9个月前

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e4 + 10;
int n, k, fa[N], tp, a[N], b[N];

int findfa(int x) {
if (x == fa[x]) return x;
a[++tp] = x; b[tp] = fa[x];
return fa[x] = findfa(fa[x]);
}

void merge(int x, int y) {
int fx = findfa(x);
int fy = findfa(y);
if (fx != fy) {
a[++tp] = fx; b[tp] = fa[fx];
fa[fx] = fy;
}
}

int main() {
cin >> n >> k;
for (int i = 1; i <= 3 * n; i++) fa[i] = i;
int ans = 0;
for (int i = 1; i <= k; i++) {
int d, x, y;
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n) { ans++; continue; }
if (d == 2 && x == y) { ans++; continue; }
tp = 0;
if (d == 1) merge(x, y), merge(x + n, y + n), merge(x + n + n, y + n + n);
else merge(x, y + n), merge(x + n, y + n + n), merge(x + n + n, y);
if (findfa(x) == findfa(x + n) || findfa(x) == findfa(x + n + n) || findfa(x + n) == findfa(x + n + n) ||
findfa(y) == findfa(y + n) || findfa(y) == findfa(y + n + n) || findfa(y + n) == findfa(y + n + n)) {
ans++;
while (tp--) fa[a[tp]] = b[tp];
}
}
cout << ans << endl; return 0;
}


CLB
9个月前

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, M = 3e2 + 10;
int n, m, V, E, c[N], d[N], a[M][M];
double b[N], f[2][N][2];
void init(int p) {for (int i = 0; i <= m; i++) f[p][i][0] = f[p][i][1] = 1000000000.0;}
int main() {
cin >> n >> m >> V >> E;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 1; i <= n; i++) cin >> b[i];
memset(a, 0x3f, sizeof(a));
for (int i = 1; i <= V; i++) a[i][i] = 0;
for (int i = 1; i <= E; i++) {
int x, y, z; scanf("%d%d%d", &x, &y, &z);
if (z < a[x][y]) a[x][y] = a[y][x] = z;
}
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
if (a[i][j] > a[i][k] + a[k][j])
a[i][j] = a[i][k] + a[k][j];
init(0); f[0][0][0] = f[0][1][1] = 0.0;
int p = 0;
for (int i = 2; i <= n; i++) {
p ^= 1; init(p);
for (int j = 0; j <= m; j++) {
f[p][j][0] = f[p ^ 1][j][0] + 1.0 * a[c[i - 1]][c[i]];
if (j) f[p][j][0] = min(f[p][j][0], f[p ^ 1][j][1] + 1.0 * b[i - 1] * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * a[c[i - 1]][c[i]]);
if (!j) continue;
f[p][j][1] = f[p ^ 1][j - 1][0] + 1.0 * b[i] * a[c[i - 1]][d[i]] + 1.0 * (1.0 - b[i]) * a[c[i - 1]][c[i]];
if (j > 1) f[p][j][1] = min(f[p][j][1], f[p ^ 1][j - 1][1] + 1.0 * b[i - 1] * (1.0 - b[i]) * a[d[i - 1]][c[i]] + 1.0 * (1.0 - b[i - 1]) * (1.0 - b[i]) * a[c[i - 1]][c[i]] + 1.0 * b[i - 1] * b[i] * a[d[i - 1]][d[i]] +1.0 * (1.0 - b[i - 1]) * b[i] * a[c[i - 1]][d[i]]);
}
}
double ans = 100000000.0;
for (int i = 0; i <= m; i++) ans = min(ans, min(f[p][i][0], f[p][i][1]));
printf("%.2lf\n", ans);
return 0;
}


CLB
9个月前

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
int n, s, p[N], miu[N]; bool v[N];
void get_miu() {
miu[1] = 1;
for (int i = 2; i <= 10000; i++) {
if (!v[i]) p[++s] = i, miu[i] = -1;
for (int j = 1; j <= s && i * p[j] <= 10000; j++) {
v[i * p[j]] = 1;
if (i % p[j] == 0) break;
miu[i * p[j]] = -miu[i];
}
}
}

int sum[N];

LL C(int n, int m) {
if (n < m) return 0;
if (!m) return 1;
double ans = 1.0;
for (int i = 1; i <= m; i++) ans = 1.0 * ans * (n + 1 - i) / i;
return (LL)ans;
}

int main() {
get_miu();
while (cin >> n) {
memset(sum, 0, sizeof(sum));
int m = 0;
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
m = max(m, x);
for (int j = 1; j * j <= x; j++)
if (x % j == 0) {
sum[j]++;
if (j * j != x) sum[x / j]++;
}
}
LL ans = 0;
for (int i = 1; i <= m; i++)
ans += 1ll * miu[i] * C(sum[i], 4);
cout << ans << endl;
}
return 0;
}


CLB
9个月前

$$P_n-C_n^1 * P_{n-1}+C_n^2 * P_{n-2}-···+(-1)^n*C_n^n * P_0$$

$C_n^2 * P_{n-2}$的意思是先选2个数在原位上，其余的都随意排列。

$$C_n^a * P_{n-a} = \dfrac{n!}{a! * (n-a)!} * (n-a)! = \dfrac{n!}{a!}$$

$$C_n^m * (P_{n-m}-(n-m)! * s[n-m])$$

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
void read(int &x) {
x = 0; int f = 0; char s = getchar();
while (!isdigit(s)) f |= s=='-', s = getchar();
while ( isdigit(s)) x = x * 10 + s - 48, s = getchar();
x = f ? - x : x;
}

typedef long long LL;
const int N = 1e6 + 10;
const LL P = 1e9 + 7;

LL fc[N], inv[N], s[N];

LL power(LL a, LL b) {
LL ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P; b >>= 1;
}
return ans;
}

LL C(int n, int m) { return fc[n] * inv[m] % P * inv[n - m] % P; }
LL p(int n) { return fc[n];}
//LL CP(int n, int a) { return fc[n] * inv[a] % P;} // C(n,a) * P(n - a) = n! / a!

int main() {
fc[0] = 1; inv[0] = 1;
for (int i = 1; i <= 1000000; i++)
fc[i] = fc[i - 1] * i % P, inv[i] = power(fc[i], P - 2);
for (int i = 1, j = 1; i <= 1000000; i++, j *= -1)
s[i] = s[i - 1] + 1ll * j * inv[i] % P, s[i] %= P;
int T; cin >> T;
while (T--) {
LL s1 = fc[n - m] * s[n - m] % P;
LL s2 = (p(n - m) - s1 + P) % P;
LL ans = C(n, m) * s2 % P;
printf("%lld\n", ans);
}
return 0;
}


CLB
9个月前

（我被这道题恶心了大半个上午）

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int N = 310, P = 7;
int power(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P; b >>= 1;
}
return ans;
}
int n, m, a[N][N], ans[N];
map<string, int> mp;

void init() {
mp["MON"] = 1;
mp["TUE"] = 2;
mp["WED"] = 3;
mp["THU"] = 4;
mp["FRI"] = 5;
mp["SAT"] = 6;
mp["SUN"] = 7;
}

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;}

void Prepare() {
int k, st, ed; string s;
memset(a, 0, sizeof(a));
for (int i = 1; i <= m; i++) {
scanf("%d", &k);
cin >> s; st = mp[s];
cin >> s; ed = mp[s];
a[i][n + 1] = (ed - st + 1 + P) % P;
for (int j = 1; j <= k; j++) {
scanf("%d", &st);
a[i][st]++; a[i][st] %= P;
}
}
}

void Guass() {
int now = 1; bool flag = 0;
for (int i = 1; i <= n; i++) {
int k = now;
for (; k <= m; k++) if (a[k][i] != 0) break;
if (k == m + 1) continue;
if (k != now) for (int j = 1; j <= n + 1; j++) swap(a[now][j], a[k][j]);
for (int j = 1; j <= m; j++) {
if (j == now) continue;
if (a[j][i] == 0) continue;
int t = a[now][i] * a[j][i] / gcd(a[now][i], a[j][i]);
int p1 = t / a[now][i], p2 = t / a[j][i];
for (int k = 1; k <= n + 1; k++)
a[j][k] = (a[j][k] * p2 - a[now][k] * p1) % P;
}
if (i == n) flag = 1;
now++; if (now == m + 1) break;
}
for (int i = 1; i <= m; i++) {
if (a[i][n + 1] == 0) continue;
bool bk = 0;
for (int j = 1; j <= n; j++)
if (a[i][j] != 0) { bk = 1; break;}
if (!bk) {puts("Inconsistent data."); return;}
}
if (!flag) {puts("Multiple solutions."); return;}
for (int i = 1; i <= n; i++) {
if (a[i][i] == 0) {puts("Multiple solutions."); return;}
if (a[i][i] * a[i][n + 1] < 0) {
if (a[i][i] < 0) a[i][i] = abs(a[i][i]), a[i][n + 1] = abs((a[i][n + 1] % P - P) % P);
else a[i][n + 1] = (a[i][n + 1] % P + P) % P;
}
ans[i] = a[i][n + 1] * power(a[i][i], P - 2) % P;
if (ans[i] < 3) ans[i] += P;
}
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
puts("");
}

int main() {
init();
while (cin >> n >> m && n && m) {
Prepare();
Guass();
}
return 0;
}


CLB
9个月前

(ax+by)(ax+by)…(ax+by)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1010, P = 10007;
int a, b, k, n, m;
int f[N][N];
int main() {
cin >> a >> b >> k >> n >> m;
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int j = 0; j <= m; j++) f[0][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
f[i][j] = (f[i - 1][j] + f[i][j - 1]) % P;
int ans = f[n][m];
a %= P;
for (int i = 1; i <= n; i++) ans = (ans * a) % P;
b %= P;
for (int i = 1; i <= m; i++) ans = (ans * b) % P;
cout << ans << endl; return 0;
}


CLB
9个月前

1：系数全部为0，但是结果为1，那么无解
2：系数有1，那么该开关的状态肯定是确定的，跳过
3：系数全部为0，结果也为0，那么按不按都可以

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 41;
int n;
int a[N], b[N], c[N][N];
int main() {
int T; cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
int x, y;
memset(c, 0, sizeof(c));
while (~scanf("%d%d", &x, &y) && x && y) c[y][x] = 1;
for (int i = 1; i <= n; i++) c[i][n + 1] = a[i] ^ b[i], c[i][i] = 1;
for (int ki = 1; ki < n; ki++) {
int k = ki;
for(; k <= n && !c[k][ki]; k++);
if (k == n + 1) continue;
if (k != ki) for (int i = 1; i <= n + 1; i++) swap(c[ki][i], c[k][i]);
for (int i = ki + 1; i <= n; i++) {
if (c[i][ki] == 0) continue;
for (int j = ki; j <= n + 1; j++)
c[i][j] = c[i][j] ^ c[ki][j];
}
}
bool flag = 1;
int sum = 0;
for (int i = n; i >= 1; i--) {
bool bk = 0;
for (int j = i; j <= n; j++)
if (c[i][j] == 1) { bk = 1; continue;}
if (!bk) {
if (c[i][n + 1] == 1) {flag = 0; break; }
sum++;
}
if (c[i][i] == 0) continue;
for (int j = i - 1; j >= 1; j--) {
if (c[j][i] == 0) continue;
for (int k = i; k <= n + 1; k++)
c[j][k] = c[j][k] ^ c[i][k];
}
}
if (!flag) {puts("Oh,it's impossible~!!"); continue;}
int ans = 1;
for (int i = 1; i <= sum; i++) ans = ans * 2;
cout << ans << endl;
}
return 0;
}