T1 铲雪
通过打表可以发现 \(2^{23}\equiv 2^{47}\pmod{998244352}\) ,因此对于前 \(22\) 次平方操作,直接暴力修改即可,超出 \(22\) 的平方操作,对每个位置维护长度为 \(24\) 的平方数组,那么每次操作就是简单的数组循环移动,线段树维护即可。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#include <iostream>
using namespace std;
const int max1 = 1e5;
const int mod = 998244353;
int n, m, A[max1 + 5][24];
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
map <int, int> pos;
struct Bit
{
int tree[max1 + 5];
#define lowbit(now) ( now & -now )
void Clear ()
{
memset(tree + 1, 0, sizeof(int) * n);
return;
}
void Insert ( int now, int x )
{
while ( now <= n )
{
Add(tree[now], x);
now += lowbit(now);
}
return;
}
int Query ( int now )
{
int res = 0;
while ( now )
{
Add(res, tree[now]);
now -= lowbit(now);
}
return res;
}
int Query ( int L, int R )
{
return ( Query(R) - Query(L - 1) + mod ) % mod;
}
}Tree1;
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
struct Data
{
int val[24], head, tag;
}tree[max1 * 4 + 5];
void Push_Up ( int now )
{
tree[now].head = 0;
int L = tree[lson(now)].head, R = tree[rson(now)].head;
for ( int i = 0; i < 24; i ++ )
{
tree[now].val[i] = 0;
Add(tree[now].val[i], tree[lson(now)].val[L]);
Add(tree[now].val[i], tree[rson(now)].val[R]);
L = L == 23 ? 0 : L + 1;
R = R == 23 ? 0 : R + 1;
}
return;
}
void Push_Down ( int now )
{
if ( tree[now].tag )
{
tree[lson(now)].head = ( tree[lson(now)].head + tree[now].tag ) % 24;
tree[rson(now)].head = ( tree[rson(now)].head + tree[now].tag ) % 24;
tree[lson(now)].tag += tree[now].tag;
tree[rson(now)].tag += tree[now].tag;
tree[now].tag = 0;
}
return;
}
void Build ( int now, int L, int R )
{
memset(tree[now].val, 0, sizeof(tree[now].val)); tree[now].head = tree[now].tag = 0;
if ( L == R )
return;
int mid = L + R >> 1;
Build(lson(now), L, mid);
Build(rson(now), mid + 1, R);
return;
}
void Insert ( int now, int L, int R, int p, int x )
{
if ( L == R )
{
tree[now].head = tree[now].tag = 0; tree[now].val[0] = x;
for ( int i = 1; i < 24; i ++ )
tree[now].val[i] = 1LL * tree[now].val[i - 1] * tree[now].val[i - 1] % mod;
return;
}
Push_Down(now);
int mid = L + R >> 1;
if ( p <= mid )
Insert(lson(now), L, mid, p, x);
else
Insert(rson(now), mid + 1, R, p, x);
Push_Up(now);
return;
}
void Update ( int now, int L, int R, int ql, int qr )
{
if ( L >= ql && R <= qr )
{
tree[now].head = tree[now].head == 23 ? 0 : tree[now].head + 1;
++tree[now].tag;
return;
}
Push_Down(now);
int mid = L + R >> 1;
if ( ql <= mid )
Update(lson(now), L, mid, ql, qr);
if ( qr > mid )
Update(rson(now), mid + 1, R, ql, qr);
Push_Up(now);
return;
}
int Query ( int now, int L, int R, int ql, int qr )
{
if ( L >= ql && R <= qr )
return tree[now].val[tree[now].head];
Push_Down(now);
int mid = L + R >> 1, res = 0;
if ( ql <= mid )
Add(res, Query(lson(now), L, mid, ql, qr));
if ( qr > mid )
Add(res, Query(rson(now), mid + 1, R, ql, qr));
return res;
}
}Tree2;
int main ()
{
freopen("snow.in", "r", stdin);
freopen("snow.out", "w", stdout);
scanf("%d%d", &n, &m); Tree1.Clear(); Tree2.Build(1, 1, n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%d", &A[i][0]);
A[i][0] = Quick_Power(A[i][0], mod - 2);
for ( int k = 1; k < 24; k ++ )
A[i][k] = 1LL * A[i][k - 1] * A[i][k - 1] % mod;
pos[i] = 0; Tree1.Insert(i, A[i][0]);
}
pos[n + 1] = 0;
int opt, L, R, ans;
while ( m -- )
{
scanf("%d%d%d", &opt, &L, &R);
if ( !opt )
{
Tree2.Update(1, 1, n, L, R);
while ( true )
{
int p = pos.lower_bound(L) -> first;
if ( p > R )
break;
L = p + 1;
Tree1.Insert(p, mod - A[p][pos[p]]);
if ( pos[p] == 22 )
{
pos.erase(pos.find(p));
Tree2.Insert(1, 1, n, p, A[p][23]);
}
else
{
++pos[p];
Tree1.Insert(p, A[p][pos[p]]);
}
}
}
else
{
ans = ( Tree1.Query(L, R) + Tree2.Query(1, 1, n, L, R) ) % mod;
printf("%d\n", ans);
}
}
return 0;
}
T2 抽卡
设 \(f(S)\) 表示当前先手行动,剩余卡牌组成集合 \(S\) 时的期望权值和,设 \(g(S)\) 表示当前后手行动,剩余卡牌组成集合 \(S\) 时的期望权值和。
考虑转移,以 \(f(S)\) 转移为例,枚举随机选取的集合 \(T\) (由于 \(T\) 越大,可选卡牌越多,因此先手会使 \(T\) 集合尽可能大),设合法的 \(T\) 集合有 \(cnt\) 个,存在转移:
\[f(S)=\tfrac{1}{cnt}\sum_{T\subseteq S, |T|\le m}\max(\max_{i\in T}(a_i+g(S-\{i\})), g(S)) \]同理:
\[g(S)=\tfrac{1}{cnt}\sum_{T\subseteq S, |T|\le m}\min(\min_{i\in T}(a_i+f(S-\{i\})), f(S)) \]容易发现转移存在后效性,比较显然的思路使枚举 \(f(S)\) 的值,带入计算,找到计算结果与枚举结果相等的值。
优化只需要发现随之枚举值的增大,求解值同样增大,但是求解值增大速度较小,简单画函数图像可以发现求解值与枚举值之差存在单调性,因此可以二分求解。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 15, max2 = 1 << 15;
const double eps = 1e-8;
int n, m, k, A[max1 + 5], sum;
vector <int> sit[max2 + 5];
double f[max2 + 5], g[max2 + 5], tmp1[max2 + 5], tmp2[max2 + 5];
void Solve ( int S, double val )
{
int siz = sit[S].size();
g[S] = 0;
for ( auto T : sit[S] )
g[S] += min(tmp1[T], val) / siz;
f[S] = 0;
for ( auto T : sit[S] )
f[S] += max(tmp2[T], g[S]) / siz;
return;
}
int main ()
{
freopen("card.in", "r", stdin);
freopen("card.out", "w", stdout);
scanf("%d%d%d", &n, &m, &k);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &A[i]), sum += A[i];
for ( int S = 0; S < 1 << n; S ++ )
{
if ( __builtin_popcount(S) >= k )
{
if ( __builtin_popcount(S) <= m )
sit[S].push_back(S);
else
{
for ( int T = S; T; T = ( T - 1 ) & S )
if ( __builtin_popcount(T) == m )
sit[S].push_back(T);
}
}
}
for ( int S = 0; S < 1 << n; S ++ )
{
int pop = __builtin_popcount(S);
if ( pop == k )
f[S] = g[S] = 0;
else if ( pop > k )
{
for ( auto T : sit[S] )
{
tmp1[T] = sum;
for ( int i = 1; i <= n; i ++ )
if ( T >> i - 1 & 1 )
tmp1[T] = min(tmp1[T], A[i] + f[S ^ 1 << i - 1]);
}
for ( auto T : sit[S] )
{
tmp2[T] = -sum;
for ( int i = 1; i <= n; i ++ )
if ( T >> i - 1 & 1 )
tmp2[T] = max(tmp2[T], A[i] + g[S ^ 1 << i - 1]);
}
double L = 0, R = sum;
while ( R - L > eps )
{
double mid = 0.5 * ( L + R ); Solve(S, mid);
if ( f[S] < mid )
R = mid;
else
L = mid;
}
}
}
printf("%.8lf\n", f[( 1 << n ) - 1]);
return 0;
}
T3 樟
考虑一条边 \((i, j)\) ,根据题目要求,一定存在边 \((p_i, p_j)\) ,继续推导,一定存在边 \((p_{p_i}, p_{p_j})\) ,继续推导,一定存在边 \((p_{p_{p_i}}, p_{p_{p_j}})\) ,容易发现这构成置换环的关系。
于是考虑两个置换环的连边,以大小为 \(2,4\) 的置换环为例:
容易发现图中不存在环,因此这样的连边可能形成树。
猜想到置换环之间的连边不存在环可能与 \(\gcd\) 有关,因此考虑大小为 \(4,6\) 的置换环:
(其中 \(1, 2, 3, 4, 5, 6\) 为一个置换环, \(7, 8, 9, 10\) 位一个置换环)
容易发现连边中存在环,一定无法构成一棵树。
于是猜想一个结论:只有大小存在倍数关系的置换环间存在连边,并且连边方案数为较小的环的大小。
此时观察到,大小大于 \(2\) 的置换环中的点两两之间不能存在连边,因此如果需要将整棵树连通,需要大小为 \(1\) 或大小为 \(2\) 的置换环。
如果存在大小为 \(1\) 的置换环,显然这些置换环形成树,容易通过 prufer 序列求解这棵树的方案数。
考虑将其余大小的环挂到这棵树上,设当前枚举的大小为 \(i\) ,置换环个数为 \(c_i\) ,由于大小相同的置换环之间可能存在连边,因此需要枚举当前大小的所有置换环构成的连通块个数 \(k\) ,考虑对这个存在 \(k\) 个连通块的森林进行计数,建立虚点 \(0\) ,将森林中所有树的根节点与 \(0\) 连边,容易发现此时形成的新树中,存在 \(k-1\) 个位置在 prufer 序列上数值为 \(0\) ,其余位置任意,因此方案数为 \(\binom{c_i-1}{k-1}c_i^{c_i-k}\) 。
因此大小为 \(i\) 的置换环对答案的贡献为
\[\sum_{k=1}^{c_i}\binom{c_i-1}{k-1}c_i^{c_i-k}\times i^{c_i-k}\times (\sum_{d|i, d<i}(c_d\times d))^k \]如果不存在大小为 \(1\) 的置换环,考虑使用大小为 \(2\) 的置换环进行代替,这些环构成树的方案数为 \((2c_2)^{c_2-1}\) ,之后仍然枚举剩余大小的环连接到树上即可。
code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int max1 = 5e5;
const int mod = 998244353;
int T, n, A[max1 + 5], bin[max1 + 5], sum[max1 + 5];
bool vis[max1 + 5];
int fac[max1 + 5], ifac[max1 + 5], inv[max1 + 5];
int C ( int n, int m )
{
if ( n < m || n < 0 || m < 0 )
return 0;
return 1LL * fac[n] * ifac[n - m] % mod * ifac[m] % mod;
}
int Quick_Power ( int base, int p )
{
int res = 1;
while ( p )
{
if ( p & 1 )
res = 1LL * res * base % mod;
p >>= 1;
base = 1LL * base * base % mod;
}
return res;
}
void Work ()
{
scanf("%d", &n);
memset(bin + 1, 0, sizeof(int) * n);
memset(sum + 1, 0, sizeof(int) * n);
memset(vis + 1, 0, sizeof(bool) * n);
for ( int i = 1; i <= n; i ++ )
scanf("%d", &A[i]);
for ( int i = 1; i <= n; i ++ )
{
if ( !vis[i] )
{
int x = i, len = 0;
while ( !vis[x] )
{
++len;
vis[x] = true;
x = A[x];
}
++bin[len];
}
}
for ( int i = 1; i <= n; i ++ )
{
if ( !bin[i] )
continue;
for ( int k = 2; k * i <= n; k ++ )
sum[i * k] = ( sum[i * k] + 1LL * bin[i] * i ) % mod;
}
int ans = 0;
if ( bin[1] )
{
if ( bin[1] == 1 )
ans = 1;
else
ans = Quick_Power(bin[1], bin[1] - 2);
for ( int i = 2; i <= n; i ++ )
{
if ( !bin[i] )
continue;
int trans = 0;
for ( int k = 1; k <= bin[i]; k ++ )
trans = ( trans + 1LL * C(bin[i] - 1, k - 1) * Quick_Power(bin[i], bin[i] - k) % mod * Quick_Power(i, bin[i] - k) % mod * Quick_Power(sum[i], k) % mod ) % mod;
ans = 1LL * ans * trans % mod;
}
}
else if ( bin[2] )
{
if ( bin[2] == 1 )
ans = 1;
else
ans = 1LL * Quick_Power(bin[2], bin[2] - 1) * Quick_Power(2, bin[2] - 1) % mod;
for ( int i = 3; i <= n; i ++ )
{
if ( !bin[i] )
continue;
int trans = 0;
for ( int k = 1; k <= bin[i]; k ++ )
trans = ( trans + 1LL * C(bin[i] - 1, k - 1) * Quick_Power(bin[i], bin[i] - k) % mod * Quick_Power(i, bin[i] - k) % mod * Quick_Power(sum[i], k) % mod ) % mod;
ans = 1LL * ans * trans % mod;
}
}
printf("%d\n", ans);
return;
}
int main ()
{
freopen("camphor.in", "r", stdin);
freopen("camphor.out", "w", stdout);
inv[1] = 1;
for ( int i = 2; i <= max1; i ++ )
inv[i] = 1LL * ( mod - mod / i ) * inv[mod % i] % mod;
fac[0] = ifac[0] = 1;
for ( int i = 1; i <= max1; i ++ )
{
fac[i] = 1LL * fac[i - 1] * i % mod;
ifac[i] = 1LL * ifac[i - 1] * inv[i] % mod;
}
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}