因为 qhy 太菜了所以只想 (hui) 做前四题
T1 redbag 发红包
签到题，随便推推，输出 $\frac w {2^k}$即可
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 200005
#define ls(u) t[u].s[0]
#define rs(u) t[u].s[1]
#define lowbit(x) x & -x
#define ll long long
#define pb push_back
#define mod 1000000007
ll n, m, a[N], x, y, k, ans, inv2, w;
inline ll pow (ll x, ll y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
int main ()
{
scanf("%lld %lld %lld", &w, &n, &k);
inv2 = pow(1ll * 2, 1ll * (mod - 2));
printf("%lld", w * pow(inv2, k) % mod);
return 0;
}
T2 不强制在线的动态快速排序
这题我们首先要推一推柿子
首先我们求一下 $[L,R]$这些数全部异或起来是多少？
将这些数二进制展开，注意到 $L$的二进制位任意一位进一位之后的枚举的数该位都是偶数次，根据异或的性质这些位对答案没有贡献，$R$也同理，所以预处理一个 $p[i]=2^i$，$logn$扫一遍就求出来了。
求 $[2L+1,2R-1]$之间所有奇数的异或和，因为是奇数，个位随便搞搞，其它位就是 $[L,R-1]$所有整数的异或和，求出来左移一位就行。
inline ll calc (ll l, ll r)
{
//first digit
ll x = l, y = r, ret = 0;
if (x & 1) --x;
if (!(y & 1)) ++y, ret ^= 1;
ret ^= ((y - x + 1) >> 1) & 1;
//other digits
fo (i, 1, 30)
{
ll bit = p[i];
if (bit & l)//1
{
x = p[i + 1];
ret ^= ((x - l) & 1) ? bit : 0;
}
if (bit & r)
{
y = p[i];
ret ^= ((y - r + 1) & 1) ? bit : 0;
}
}
return ret;
}
由于那个询问 2 的公式，重复的元素只等价于出现了 1 次，所以只需要记录一个元素是否出现。
然而比赛的时候我脑抽以为要将出现的元素次数分奇偶性讨论 (其实打到后来就发现不用了，然而脑子已经混乱了)，写了一棵珂朵莉树，但是由于分类讨论过于鬼畜不堪维护区间之间的关系然后就写了个极丑的 query，结果爆 40 分了
珂朵莉树 (40 分的那个，改改区间之间的关系应该能 A？)：
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 2000505
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
ll p[40], l, r, n, opt, sum = 0;
struct node{
int l, r;
mutable bool v;
node (int L, int R = -1, ll V = 0):l(L), r(R), v(V) {}
friend bool operator < (node x, node y) {return x.l < y.l;}
};
std::set<node> s;
inline bool check (ll l, ll r)
{
ll x = l, y = r;
bool ret = 0;
if (x & 1) --x;
if (!(y & 1)) ++y, ret ^= 1;
ret ^= ((y - x + 1) >> 1) & 1;
return ret;
}
inline itset split (ll p)
{
itset it = s.lb(node(p));
if (it != s.end() && it -> l == p) return it;
--it;
ll L = it -> l, R = it -> r;
bool V = it -> v;
s.erase(it);
s.insert(node(L, p - 1, V));
return s.insert(node(p, R, V)).first;//把后面那个区间的迭代器返回
}
ll calc (ll l, ll r);
inline void assign (int l, int r)
{
itset itr = split(r + 1), itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, 1));
}
inline ll query ()
{
ll ret = 0;
itset it = s.begin(), ed = s.end();
ll last = 0;
for (; it != ed; ++it)
{
if (it -> v == 0) continue;
// ll lastret = ret;
ll l = it -> l, r = it -> r;
if (!last)
{
last = l++;
if (l > r) continue;
}
ret ^= calc(l, r - 1) << 1;
ret ^= (r - l) & 1;
// printf("%lld\n", ret ^ lastret);
ret ^= (l - last) * (l + last);
last = r;
}
return ret;
}
inline ll calc (ll l, ll r)
{
//first digit
ll x = l, y = r, ret = 0;
if (x & 1) --x;
if (!(y & 1)) ++y, ret ^= 1;
ret ^= ((y - x + 1) >> 1) & 1;
//other digits
fo (i, 1, 30)
{
ll bit = p[i];
if (bit & l)//1
{
x = p[i + 1];
ret ^= ((x - l) & 1) ? bit : 0;
}
if (bit & r)
{
y = p[i];
ret ^= ((y - r + 1) & 1) ? bit : 0;
}
}
return ret;
}
int main ()
{
p[0] = 1;
fo (i, 1, 35) p[i] = p[i - 1] * 2;
scanf("%lld", &n);
s.insert(node(1, inf, 0));
s.insert(node(inf + 1, inf + 1, 0));
while (n--)
{
scanf("%lld", &opt);
if (opt & 1)
{
scanf("%lld %lld", &l, &r);
assign(l, r);
}
else
{
printf("%lld\n", query());
}
}
return 0;
}
其实区间维护不是线段树吼吗？因为 $L$和 $R$比较大那就动态开点呗，维护一下每个区间的 min 和 max 值，合并即可：
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 7000505
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls(u) t[u].s[0]
#define rs(u) t[u].s[1]
#define mod 1000000007
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
ll p[40], l, r, n, opt, sum = 0, tot, root;
struct node{
ll sum, s[2], mx, mi;
bool v;
}t[N];
inline bool check (ll l, ll r)
{
ll x = l, y = r;
bool ret = 0;
if (x & 1) --x;
if (!(y & 1)) ++y, ret ^= 1;
ret ^= ((y - x + 1) >> 1) & 1;
return ret;
}
inline ll calc (ll l, ll r)
{
//first digit
ll x = l, y = r, ret = 0;
if (x & 1) --x;
if (!(y & 1)) ++y, ret ^= 1;
ret ^= ((y - x + 1) >> 1) & 1;
//other digits
fo (i, 1, 30)
{
ll bit = p[i];
if (bit & l)//1
{
x = p[i + 1];
ret ^= ((x - l) & 1) ? bit : 0;
}
if (bit & r)
{
y = p[i];
ret ^= ((y - r + 1) & 1) ? bit : 0;
}
}
return ret;
}
inline void update (ll u)
{
if (ls(u) && rs(u))
{
t[u].mx = std::max(t[ls(u)].mx, t[rs(u)].mx);
t[u].mi = std::min(t[ls(u)].mi, t[rs(u)].mi);
t[u].sum = t[ls(u)].sum ^ t[rs(u)].sum ^ ((t[rs(u)].mi - t[ls(u)].mx) * (t[rs(u)].mi + t[ls(u)].mx));
t[u].v = t[ls(u)].v && t[rs(u)].v;
}
else
{
ll p = ls(u) ? 0 : 1;
t[u].mx = t[t[u].s[p]].mx;
t[u].mi = t[t[u].s[p]].mi;
t[u].sum = t[t[u].s[p]].sum;
}
}
inline void add (ll &u, ll l, ll r, ll L, ll R)
{
if (!u) u = ++tot;
if (t[u].v) return;
if (l <= L && R <= r)
{
t[u].sum = (calc(L, R - 1) << 1) + ((R - L) & 1);
t[u].mi = L; t[u].mx = R; t[u].v = 1; return;
}
ll mid = L + R >> 1;
if (l <= mid) add(ls(u), l, r, L, mid);
if (mid < r) add(rs(u), l, r, mid + 1, R);
update(u);
}
int main ()
{
p[0] = 1;
fo (i, 1, 35) p[i] = p[i - 1] * 2;
scanf("%lld", &n);
while (n--)
{
scanf("%lld", &opt);
if (opt & 1)
{
scanf("%lld %lld", &l, &r);
add(root, l, r, 1, inf);
}
else
{
printf("%lld\n", t[1].sum);
}
}
return 0;
}
另外我感觉题解的打表法找出来的规律太可怕了 mark 一下
T3 dkw 的 lcm
改变枚举顺序的好题啊！因为欧拉函数有积性，我们可以将质因数拆开，枚举 $p_i^j$，表示小于 n 的第 i 个质数的 j 次方，考虑 $phi(p_i^j)$对答案的贡献，我们要求出 $p_i^j$它的出现次数，我们令 $t = lcm(a_1,\cdots,a_k)$，我们也就是求有多少个 a 的 k 元组个数满足 $p_i^j|t$且 $t\not\equiv 0(mod\; p_i^{j + 1})$（这个叫恰好整除的东西似乎还有一种 $p_i^j||t$的表达方法，我以后用第二种吧因为不整除号打不出来）
假设 $a_i$被 $p_i^{k_i}$恰好整除，我们有
$$max\{k_1,\cdots,k_k)\}=j$$
也就是说我们要求出 $p_i^{j’}||b\quad \forall j’\in [1,j]\quad b\in[1,n]$的 b 的个数，说这么复杂其实就是一个补集转换的事情，我们求 $p_i^{j’}||b\quad \forall j’\in [j+1,\infty)\quad b\in[1,n]$的个数再用 n 减一下就行，这里显然有 $b=[\frac n {p_{j + 1}}]$。
现在我们已经满足了所有的指数都是在 $[1,j]$之间的，但是我们要保证最大的指数是 $j$，其实我们再用这个减去指数在 $[1,j-1]$之间中随便选的方案就能保证最大的指数是 $j$了。
我们费劲千辛万苦就求出了 $phi(p_i^j)$对答案的贡献次数，将它乘这么多次就行了。
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 7000505
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls(u) t[u].s[0]
#define rs(u) t[u].s[1]
#define mod 1000000007
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
int n, k;
std::bitset<N> vis;
int p[N], tot, phi[N];
ll prod;
inline void init ()
{
phi[1] = 1;
fo (i, 2, n)
{
if (!vis[i])
{
p[++tot] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= tot && i * p[j] <= n; ++j)
{
vis[i * p[j]] = 1;
if (!(i % p[j]))
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
}
inline ll pow (ll x, ll y, ll mo)
{
if (!x) return 0;
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mo;
x = x * x % mo;
y >>= 1;
}
return ret;
}
int main ()
{
scanf("%d %d", &n, &k);
init();
prod = 1;
fo (i, 1, tot)
{
for (ll now = p[i]; now <= n; now *= p[i])
{
ll a = (pow(n - n / now / p[i], k, (ll) (mod - 1)) - pow(n - n / now, k, (ll) (mod - 1)) + mod - 1) % (mod - 1);
prod = prod * pow(phi[now], a, (ll) mod) % mod;
}
}
printf("%lld\n", prod);
return 0;
}
T4 能量采集
比赛的时候一看就是矩阵快速幂？但是因为五点半了六点要上晚修然而还没吃饭就随便打个 30 分就跑了。
事实证明不是只有矩阵快速幂那么简单，如果我当时有时间写的话估计也只能拿 60 分 $QAQ$
我们可以发现这题的瓶颈在于询问次数太多了，因为矩阵快速幂是 $n^2logt$的，再乘个 $q$显然会咕咕咕
我们先看 80 分做法
因为初始矩阵只是一个向量，我们可以将 $t=2$的幂次方的转移矩阵全部先预处理一遍，然后每次询问用向量去乘 $logt$个矩阵，这样我们每次询问的时间复杂度变成了 $nlogt$
然而这样还是不足以通过全部数据，然而 100 分我们还是用了相似的 trick，因为预处理是 $n^3 logt$的，我们可以考虑加大预处理的复杂度而减少询问的复杂度，把它改成 k 进制下的展开矩阵。
但是因为 qhy 比较懒所以去写了二进制下的矩阵快速幂循环展开，然后 A 了 (：
原来循环展开还能这样用.jpg
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 505
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define eps 1e-4
#define itset std::set<node>::iterator
#define lb lower_bound
ll l, r, n, m, q, f[55][55], now, a[N], tim;
struct matrix{
ll n, m, a[51][51];
friend matrix operator * (matrix x, matrix y)
{
matrix ret;
ret.n = x.n; ret.m = y.m;
fo (i, 1, ret.n)
fo (j, 1, ret.m)
{
ret.a[i][j] = 0;
for (int k = 1; k + 15 <= x.m; k += 16)
{
ret.a[i][j] = ((ret.a[i][j] + x.a[i][k] * y.a[k][j]
+ x.a[i][k + 1] * y.a[k + 1][j]
+ x.a[i][k + 2] * y.a[k + 2][j]
+ x.a[i][k + 3] * y.a[k + 3][j]
+ x.a[i][k + 4] * y.a[k + 4][j]
+ x.a[i][k + 5] * y.a[k + 5][j]
+ x.a[i][k + 6] * y.a[k + 6][j]
+ x.a[i][k + 7] * y.a[k + 7][j]
+ x.a[i][k + 8] * y.a[k + 8][j]) % mod
+ x.a[i][k + 9] * y.a[k + 9][j]
+ x.a[i][k + 10] * y.a[k + 10][j]
+ x.a[i][k + 11] * y.a[k + 11][j]
+ x.a[i][k + 12] * y.a[k + 12][j]
+ x.a[i][k + 13] * y.a[k + 13][j]
+ x.a[i][k + 14] * y.a[k + 14][j]
+ x.a[i][k + 15] * y.a[k + 15][j]) % mod;
}
fo (k, x.m - x.m % 16 + 1, x.m)
ret.a[i][j] = (ret.a[i][j] + x.a[i][k] * y.a[k][j]) % mod;
}
return ret;
}
}t[N], b, x, a1;
std::vector<ll> e[N];
inline ll pow (ll x, ll y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
inline matrix powm (matrix x, ll y)
{
matrix ret;
ret.n = ret.m = x.n;
fo (i, 1, ret.n) fo (j, 1, ret.m) ret.a[i][j] = 0;
fo (i, 1, ret.n) ret.a[i][i] = 1;
while (y)
{
if (y & 1) ret = ret * x;
x = x * x;
y >>= 1;
}
return ret;
}
inline void query (int y)
{
int i = 0;
while (y)
{
if (y & 1) x = x * t[i];
++i;
y >>= 1;
}
}
int main ()
{
scanf("%lld %lld %lld", &n, &m, &q);
fo (i, 1, n) scanf("%lld", &a[i]);
a1.n = 1; a1.m = n;
fo (i, 1, n) a1.a[1][i] = a[i];
fo (i, 1, n) e[i].pb(i);
fo (i, 1, m)
{
ll u, v;
scanf("%lld %lld", &u, &v);
e[u].pb(v);
}
b.n = b.m = n;
fo (u, 1, n)
{
ll sz = e[u].size() - 1;
ll inv = pow(sz + 1, (ll) mod - 2);
fo (j, 0, sz)
{
ll v = e[u][j];
b.a[u][v] = (b.a[u][v] + inv) % mod;
}
}
int now = 1;
fo (i, 0, 30)
{
t[i] = powm(b, now);
now = now << 1;
}
fo (i, 1, q)
{
scanf("%lld", &tim);
x = a1;
query(tim);
ll ans = 0;
fo (j, 1, n) ans ^= x.a[1][j];
printf("%lld\n", ans % mod);
}
return 0;
}
吐槽：luogu 评分有毒吧 qhy 能订正的题肯定最多紫题咋题目难度全黑了 QAQ
0 条评论