比赛链接

B.(积性函数前缀和)

题意

给定$n,m,p$, 其中$p$是质数

求$\prod _{i=1}^n\prod _{j=1}^n\prod _{k=1}^n{m}^{(i,j)[k|(i,j)]}\mathrm{m}\mathrm{o}\mathrm{d}p$

推导

使用费马降幂,可得$m^{\sum _{i=1}^n\sum _{j=1}^n(i,j)\sigma ((i,j))\mathrm{m}\mathrm{o}\mathrm{d}(p-1)}\mathrm{m}\mathrm{o}\mathrm{d}p$

$\sum _{i=1}^n\sum _{j=1}^n\sum _{k=1}^n(i,j)[k|(i,j)]=\sum _{d=1}^{n}d\sigma (d)\sum _{i=1}^n\sum _{j=1}^n[(i,j)==d]=\sum _{d=1}^{n}d\sigma (d)\sum _{i=1}^{\frac{n}{d}}\sum _{j=1}^{\frac{n}{d}}[(i,j)==1]$

使用欧拉函数可得, ${\sum }_{d=1}^{n}d\sigma (d)(2\Phi (\frac{n}{d})-1)$

$d\sigma (d),\varphi (d)$前缀和可线性筛预处理$O(n^{\frac{2}{3}})$, 剩下的直接杜教筛(或者直接分块)，这样总复杂度为$O(n^{\frac{2}{3}})$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x7fffffff;
const int N = 8e6 + 7;
int mod;
int dsig[N+1000], phi[N+10000], p[N>>3], num[N], pn;
void init() {
phi[1] = dsig[1] = 1;
for(int i = 2; i < N; i++) {
if(!phi[i]) {
phi[i] = i - 1;
p[pn++] = i;
num[i] = 1;
dsig[i] = 2;
}
for(int j = 0, d; j<pn && (d=i*p[j])<N; j++) {
if(i % p[j] == 0) {
num[d] = num[i] + 1;
phi[d] = phi[i] * p[j];
dsig[d] = dsig[i]/num[d]*(num[d]+1);
break;
} else {
num[d] = 1;
phi[d] = phi[i] * (p[j] - 1);
dsig[d] = dsig[i]*2;
}
}
}
for(int i = 1; i < N; i++) {
phi[i] = (2ll * phi[i] + phi[i - 1]) % mod;
dsig[i] = ((ll)i * dsig[i] + dsig[i - 1]) % mod;
}
for(int i = 0; i < 1000; i++) phi[i+N]=dsig[i+N]=inf;
}
int n, m, pp;
inline int id(int x) { return x < N? x : n / x + N;}
inline int s1(int x) { return x*(x+1ll)/2%mod;}
int Dsig(int x) {
int t = id(x);
if(t < N || dsig[t] != inf) return dsig[t];
int &ret = dsig[t] = 0;
for(int l = 1, r; l <= x; l = r + 1) {
r = x / (x / l);
ret = (ret + ((ll)s1(r) - s1(l-1))*s1(x/l))%mod;
}
return ret = ((ll)ret + mod) % mod;
}
int Phi(int x) {
int t = id(x);
if(t < N || phi[t] != inf) return (phi[t] - 1ll + mod) % mod;
int &ret = phi[t] = 2ll*s1(x)%mod;
for(int l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
ret = (ret - (r - l + 1ll) * (Phi(x/l) + 1)) % mod;
}
ret = ((ll)ret + mod) % mod;
return ((ll)ret + mod - 1) % mod;
}
int solve() {
mod = pp - 1;
init();
int ord = 0;
for(int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
ord = (ord + Phi(n / l) * ((ll)Dsig(r) - Dsig(l - 1))) % mod;
}
ord = ((ll)ord + mod) % mod;
int ret = 1;
for(m %= pp; ord; ord>>=1, m = (ll)m*m%pp)
if(ord&1) ret = (ll)ret*m%pp;
return ret;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
clock_t s = clock();
#endif
scanf("%d%d%d", &n, &m, &pp);
printf("%dn", solve());
#ifdef local
cerr << clock() - s << " msn";
#endif
return 0;
}

E.(树链剖分)

由于每次操作都是$s$到根，所以有一个$log$的做法？（这不是$bzoj$原题吗.jpg）

菜鸡只会树链剖分然后维护$or$和$and$标记，两个$log$的做法

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1 << 18 | 7;
vector<int> E[N];
int fa[N], dep[N], sz[N], son[N], top[N], id[N], rid[N], cnt;
void dfs1(int u, int d) {
dep[u] = d; sz[u] = 1;
int& maxs = son[u] = -1;
for(int &e : E[u]) {
if(e == fa[u]) continue;
fa[e] = u, dfs1(e, d + 1);
sz[u] += sz[e];
if(maxs == -1 || sz[e] > sz[maxs]) maxs = e;
}
}
void dfs2(int u, int tp) {
top[u] = tp; id[u] = ++cnt; rid[cnt] = u;
if(son[u] != -1) dfs2(son[u], tp);
for(int &e : E[u]) {
if(e == fa[u] || e == son[u]) continue;
dfs2(e, e);
}
}
int w[N], tag[2][N], a[N];
int n, q;
#define ls o<<1
#define rs o<<1|1
void push_up(int o){ w[o]=w[ls]^w[rs];}
void push_down(int o, int l, int r) {
int &t1 = tag[0][o], &t2=tag[1][o];
if(~t1) {
w[ls] &= t1, w[rs] &= t1;
tag[0][ls] &= t1; tag[0][rs] &= t1;
tag[1][ls] ^= (~t1&tag[1][ls]);
tag[1][rs] ^= (~t1&tag[1][rs]);
t1 = ~0u;
}
if(t2) {
int mid = (l+r)>>1;
if((mid-l+1)&1) w[ls] |= t2;
else w[ls] ^= t2&w[ls];
if((r-mid)&1) w[rs] |= t2;
else w[rs] ^= t2&w[rs];
tag[1][ls] |= t2; tag[1][rs] |= t2;
tag[0][ls] ^= (~tag[0][ls]&t2);
tag[0][rs] ^= (~tag[0][rs]&t2);
t2 = 0;
}
}
void build(int o, int l, int r) {
tag[0][o] = ~0u, tag[1][o] = 0;
if(l == r) { w[o] = a[rid[l]]; return;}
int mid = (l + r)>>1;
build(ls,l,mid), build(rs, mid+1, r);
push_up(o);
}
void update(int o, int l, int r, int L, int R, int x, int k) {
// k = 0 for AND, k = 1 for OR
if(L <= l && r <= R) {
if(k) {
if((r-l+1)&1) w[o] |= x;
else w[o] ^= w[o]&x;
tag[0][o] ^= ~tag[0][o]&x, tag[1][o] |= x;
} else {
w[o] &= x;
tag[0][o] &= x, tag[1][o] ^= (~x&tag[1][o]);
}
return;
}
int mid = (l + r) >> 1;
push_down(o, l, r);
if(mid >= L) update(ls, l, mid, L, R, x, k);
if(mid < R) update(rs, mid+1, r, L, R, x, k);
push_up(o);
}
int query(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) return w[o];
int mid = (l + r)>>1, ret = 0;
push_down(o, l, r);
if(mid >= L) ret ^= query(ls, l, mid, L, R);
if(mid < R) ret ^= query(rs, mid+1, r, L, R);
return ret;
}
/*
void brock(int l, int r, int x, int o) {
if(o == 0) for(int i = l; i <= r; i++) a[i] &= x;
if(o == 1) for(int i = l; i <= r; i++) a[i] |= x;
}
int query(int l, int r) {
int ret = 0;
for(int i = l; i <= r; i++)
ret ^= a[i];
return ret;
}*/
void updates(int u, int v, int x, int op) {
int uu = top[u], vv = top[v];
while(uu != vv) {
if(dep[uu] < dep[vv]) swap(uu, vv), swap(u, v);
update(1, 1, n, id[uu], id[u], x, op);
u = fa[uu], uu = top[u];
}
if(dep[u] < dep[v]) swap(u, v);
update(1, 1, n, id[v], id[u], x, op);
}
int query(int u, int v) {
int uu = top[u], vv = top[v], ret = 0;
while(uu != vv) {
if(dep[uu] < dep[vv]) swap(uu, vv), swap(u, v);
ret ^= query(1, 1, n, id[uu], id[u]);
u = fa[uu], uu = top[u];
}
if(dep[u] < dep[v]) swap(u, v);
ret ^= query(1, 1, n, id[v], id[u]);
return ret;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
E[u].push_back(v);
E[v].push_back(u);
}
dfs1(1, 1); dfs2(1, 1);
build(1, 1, n);
for(int i = 0, op, u, x; i < q; i++) {
scanf("%d%d%d", &op, &u, &x);
if(op == 3) {
x ^= query(1, u);
puts(x?"YES":"NO");
} else updates(1, u, x, op==1);
}
return 0;
}

I.(细节题，bsgs)

题意

给定由$a,p$生成的一个序列$b_1,b_2,...,b_n$,其中{$b_n$}为$c_k\equiv a^k\mathrm{m}\mathrm{o}\mathrm{d}p$的一段连续的子串.

现在要求$a,p$.答案不唯一输出"unsure", 不存在输出"error".

做法

假设$b_1=a^k$, 则$b_i=a^{k+i-1}$
对于任意的$2\le i\le n-1$, 都有$b_i^2\equiv b_{i-1}{b}_{i+1}\mathrm{m}\mathrm{o}\mathrm{d}p$

也就是说$p|(b_i^2-b_{i-1}{b}_{i+1})$，求出所有的$b_i^2-b_{i-1}{b}_{i+1}$求gcd, 然后对最后结果的每个素因子check即可.

如何check？ 就是说判断一个素数$p$是否合法.

注意到$a=inv(b_0)\times b_1\mathrm{m}\mathrm{o}\mathrm{d}p$

先判$b_0$能否通过$a^k\mathrm{m}\mathrm{o}\mathrm{d}p$表示（bsgs算法），然后挨个检查是否合法。

边界情况: 所有数都相等, 如果全为1, 输出"unsure", 否则输出"error".

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 1e5 + 7;
#ifdef local
typedef long long i16;
#else
typedef __int128 i16;
#endif
const i16 one = 1;
ll power_mod(ll a, ll b, ll mod) {
ll ret = 1;
for(a %= mod; b; b>>=1, a=one*a*a%mod)
if(b & 1) ret = one*ret*a%mod;
return ret;
}
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
cc_hash_table<ll, ll> hs;
bool bsgs(ll a, ll b, ll n) {
hs.clear();
ll B = sqrt(n), t = 1, tt = b;
for(ll i = 0; i < B; i++)
hs[t] = i, t = one*a*t%n;
t = power_mod(t, n - 2, n);
for(ll i = 0; i < n; i += B, tt=one*tt*t%n)
if(hs.find(tt) != hs.end())
return true;
return false;
}
ll a[N];
bool chk(int n, ll x) {
ll inv = power_mod(a[0], x - 2, x);
ll aa = one * a[1] * inv % x, t = a[0];
if(a[0] >= x || !bsgs(aa, a[0], x)) return 0;
for(int i = 1; i < n; i++)
if((t = one * t * aa % x) != a[i])
return 0;
return 1;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
int n; scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lld", a+i);
ll d = 0;
if(n >= 2) {
bool f = 1;
for(int i = 1; i < n; i++)
f &= a[i] == a[i - 1];
if(f) return 0 * puts(a[0]==1?"unsure":"error");
}
for(int i = 1; i < n-1; i++)
d = __gcd(d, abs(a[i]*a[i]-a[i-1]*a[i+1]));
if(d == 1) return 0 * puts("error");
if(d == 0) return 0 * puts("unsure");
vector<ll> aa;
for(ll i = 2; i * i <= d; i++) {
if(d % i == 0) {
if(chk(n, i)) aa.push_back(i), assert(i==2);
while(d % i == 0) d /= i;
}
}
if(d != 1) if(chk(n, d)) aa.push_back(d);
if(aa.size() == 0) return 0 * puts("error");
else if(aa.size() > 1) return 0 * puts("unsure");
else {
ll inv = power_mod(a[0], aa[0] - 2, aa[0]);
ll tt = one * a[1] * inv % aa[0];
printf("%lld %lldn", tt, aa[0]);
}
return 0;
}

J.(dfs+map启发式合并)

处理出树上前缀异或和, 然后只有异或值相等的点对才有贡献.

对于没有祖先关系的点对$(u,v)$, 贡献为$s{z}_u\times s{z}_v$，其中$s{z}_x$表示以$x$为根的子树大小.

对于有祖先关系的点对$(u,v)$,贡献为$(n-s{z}_{v^{\prime }})\times s{z}_v$, 假设祖先为$u$, $v^{\prime }$表示以$u$的儿子为根子树中包含$v$的子树根编号.

对于第一种情况，可以$dfs$前序统计，后序加点的方式来计算.

对于第二种可以直接用$map$启发式合并, 复杂度为$O(nlo{g}^{2}n)$

（赛后发现可以不用启发式合并，对于$u$这个点只在以$u$为根的子树中作为祖先，那么回溯的时候直接减掉就可以了，这样复杂度为$O(nlogn)$）

代码（启发式合并）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
vector<int> E[N];
ll w[N];
int sz[N];
void dfs(int u, int fa) {
sz[u] = 1;
for(auto &e : E[u]) {
if(e == fa) continue;
w[e] ^= w[u];
dfs(e, u);
sz[u] += sz[e];
}
}
map<ll, int> mp[N];
void Union(int x, int y) {
if(mp[x].size() < mp[y].size())
swap(mp[x], mp[y]);
for(auto &e : mp[y])
(mp[x][e.fi] += e.se) %= mod;
}
ll ans = 0;
int n;
void work(int u, int fa) {
ans += 1ll * mp[0][w[u]] * sz[u];
ans %= mod;
mp[u][w[u]] = sz[u];
for(auto &e : E[u]) {
if(e == fa) continue;
work(e, u);
if(mp[e].count(w[u])) {
ans += 1ll * mp[e][w[u]] * (n - sz[e]);
ans %= mod;
}
Union(u, e);
}
(mp[0][w[u]] += sz[u]) %= mod;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for(int i = 2, fa; i <= n; i++) {
scanf("%d%lld", &fa, &w[i]);
E[fa].push_back(i);
E[i].push_back(fa);
}
dfs(1, 0); work(1, 0);
printf("%lldn", ans);
return 0;
}

回溯

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
vector<int> E[N];
ll w[N]; int sz[N];
void prepare(int u = 1) {
sz[u] = 1;
for(int &e : E[u])
w[e]^=w[u],prepare(e),sz[u]+=sz[e];
}
map<ll, int> nfa, fa;
ll ans; int n;
void work(int u) {
int &x = nfa[w[u]], &y = fa[w[u]];
ans = (ans + 1ll*x*sz[u]) % mod;
ans = (ans + 1ll*y*sz[u]) % mod;
for(int &e : E[u]) {
y = (y + n - sz[e]) % mod;
work(e);
y = (y + mod - n + sz[e]) % mod;
}
x = (x + sz[u])%mod;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
scanf("%d", &n);
for(int i = 2, fa; i <= n; i++)
scanf("%d%lld", &fa, &w[i]), E[fa].pb(i);
prepare(), work(1);
printf("%lldn", ans);
return 0;
}

L.(置换群)

题意

给一个长度为$n$, 且每个数字都不相同的序列$a_i$.
有两种操作，
第一种交换序列的前一半和后一半, 如果$n$为奇数，中间的数不变
比如1 2 3 4 5 交换后变成 4 5 3 1 2.
第二种操作为将偶数位与其前一位交换，如果$n$为奇数，最后一个数不用交换
比如1 2 3 4 5 交换后变成 2 1 4 3 5.
两种操作可以无限次，现问可以生成多少种不同的序列序列

做法

比赛时候先瞎推瞎猜wa了两发，然后直接打表发现规律直接过了，在飞机上仔细想了下可以用置换群来解决
注意到同一个操作连续使用偶数次就变回原序列，因此可以直接做两次不同的操作，然后求置换群的循环节即可.
废话不多说直接上代码

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 7;
int a[N], vis[N];
int solve(int n) {
if(n == 1) return 1;
iota(a, a + 1 + n, 0);
fill(vis, vis + 1 + n, 0);
for(int i = 2; i <= n; i+=2)
swap(a[i], a[i - 1]);
int t = (n+1)/2+1;
for(int i = t; i <= n; i++)
swap(a[i], a[i-t+1]);
int _lc = 1;
for(int i = 1; i <= n; i++) {
if(vis[i]) continue;
int cnt = 0; int t = i;
while(!vis[t]) {
cnt++, vis[t] = 1;
t = a[t];
}
_lc = _lc/__gcd(_lc, cnt)*cnt;
}
return _lc * 2;
}
int main() {
#ifdef local
freopen("in.txt", "r", stdin);
#endif
int n; scanf("%d", &n);
for(int i = 0, x; i < n; i++) scanf("%d", &n);
printf("%dn", solve(n));
return 0;
}

最后

以上就是专一雨为你收集整理的2019西安邀请赛题解(部分)J.(dfs+map启发式合并)的全部内容，希望文章能够帮你解决2019西安邀请赛题解(部分)J.(dfs+map启发式合并)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。