我好摆！我好摆！我好摆！
求问各位大佬如何保持状态。
T1 Number
排除题面描述非常冗长的影响外，很容易想到数位 dp 。
比较显而易见的思路是从高到低考虑每一位，枚举每个数这一位填 \(0/1\) 进行转移。
考虑设 \(f_{bit,S,T}\) 表示当前从高向低考虑到第 \(bit\) 位， \(S\) 集合内的数卡到上界， \(T\) 集合内的数卡到下界时的方案数。发现状态总数为 \(O(4^n\log w)\) ，转移一次复杂度为 \(O(2^n)\) （预处理转移到的状态），但是跳过方案数为 \(0\) 的转移后发现跑的飞快，进一步分析复杂度，考虑一个数 \(i\) 的转移，将 \(L_i,R_i\) 写成二进制后发现，事实上对于大于 \(\operatorname{lcp}(L_i,R_i)\) 的位，这些位只存在一种选择方案（ \(\operatorname{lcp}\) 表示二进制下从高到低的最大失配位 ），从下一位开始，这个数只可能卡到上界，卡到下界，不卡上界也不卡下界，容易发现一个数只存在 \(O(3^n\log w)\) 种合法状态，因此总复杂度为 \(O(6^n\log w)\) 。
进一步优化，状态总数显然无法优化，因此从转移下手，考虑所有可能的转移，容易发现卡到上界只能转移到卡到上界，不卡上界也不卡下界；卡到下界只能转移到卡到下界，不卡上界也不卡下界；不卡上界也不卡下界只能转移到不卡上界也不卡下界。转移情况为 \(5\) 种，从理论上将可以做到 \(O(5^n\log w)\) ，因此考虑进行实现。沿用上述 \(f_{bit,S,T}\) 的定义，考虑在进行 \(bit=\operatorname{lcp}(L_i,R_i)\) 的转移时加入该数进行转移，具体来讲，在 \(bit\) 位枚举所有 \(bit=\operatorname{lcp}(L_i,R_i)\) 的数在这一位选择 \(0/1\) ，考虑 \(bit<\operatorname{lcp}(L_i,R_i)\) 的数的转移，对于卡到上下界的数，仍然枚举这一位选择 \(0/1\) ，对于不卡到上下界的数，由于其他数的选择已经全部确定，因此考虑直接计算满足其他数限制的，不卡到上下界的数在这一位上任选的方案数，设 \(trans_{S,T}\) 表示 \(S\) 集合内数在这一位选 \(1\) ， \(T\) 集合内数在这一位选 \(0\) ，不在 \(S/T\) 集合内的数在这一位任选的方案数，预处理 \(trans_{S,T}\) 的过程类似 FWT 枚举每一位进行转移可以做到 \(O(3^nn)\) 。
使用上述过程进行转移，可以做到 \(O(5^n\log w)\) ，由于本题数据随机，因此期望意义下貌似为 \(O(4^n\log w)\) （作者太菜了，所以根本不会证明），然后贴一份被卡成 96 分的代码。
code
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <vector>
using namespace std;
const int max1 = 11, max2 = 1 << 11;
const int mod = 998244353;
int n, lcp[max1 + 5], sum;
long long down[max1 + 5], up[max1 + 5];
char s[max2 + 5];
int lim, now;
int f[2][max2 + 5][max2 + 5], trans[max2 + 5][max2 + 5];
int newS[max2 + 5][max2 + 5], newT[max2 + 5][max2 + 5];
void Add ( int &x, int y )
{
x += y;
if ( x >= mod )
x -= mod;
return;
}
int Next ( int S, int i )
{
return ( i - 1 ) & S;
}
int main ()
{
freopen("number.in", "r", stdin);
freopen("number.out", "w", stdout);
scanf("%d", &n);
for ( int i = 1; i <= n; i ++ )
{
scanf("%lld%lld", &down[i], &up[i]);
lim = max(lim, (int)__lg(up[i]));
if ( down[i] == up[i] )
lcp[i] = -1;
else
lcp[i] = __lg(down[i] ^ up[i]);
}
scanf("%s", s);
sum = ( 1 << n ) - 1;
now = 0;
for ( int S = 0; S <= sum; S ++ )
for ( int T = 0; T <= sum; T ++ )
f[now][S][T] = 0;
f[now][0][0] = 1;
for ( int bit = lim; bit >= 0; bit -- )
{
now ^= 1;
for ( int S = 0; S <= sum; S ++ )
for ( int T = 0; T <= sum; T ++ )
f[now][S][T] = 0;
int P = 0, Q = 0, R = 0, target = 0;
for ( int i = 1; i <= n; i ++ )
{
if ( lcp[i] > bit )
P |= 1 << i - 1;
else if ( lcp[i] == bit )
Q |= 1 << i - 1;
else
R |= 1 << i - 1,
target |= ( up[i] >> bit & 1 ) << i - 1;
}
for ( int k = Q; ; k = Next(Q, k) )
{
for ( int S = P; ; S = Next(P, S) )
{
for ( int T = P; ; T = Next(P, T) )
{
trans[S][T] = 0;
if ( !T )
break;
}
if ( !S )
break;
}
int add1 = 0, add2 = 0;
for ( int i = 1; i <= n; i ++ )
{
if ( Q >> i - 1 & 1 )
{
if ( k >> i - 1 & 1 )
add1 |= 1 << i - 1;
else
add2 |= 1 << i - 1;
}
}
for ( int S = 0; S <= sum; S ++ )
{
if ( s[S] == '1' && ( R & S ) == target && ( Q & S ) == k )
{
int A = 0, B = 0;
for ( int i = 1; i <= n; i ++ )
{
if ( P >> i - 1 & 1 )
{
if ( S >> i - 1 & 1 )
A |= 1 << i - 1;
else
B |= 1 << i - 1;
}
}
++trans[A][B];
}
}
for ( int i = 1; i <= n; i ++ )
{
if ( P >> i - 1 & 1 )
{
for ( int S = P; ; S = Next(P, S) )
{
for ( int T = P ^ S; ; T = Next(P ^ S, T) )
{
if ( !( S >> i - 1 & 1 ) && !( T >> i - 1 & 1 ) )
{
Add(trans[S][T], trans[S | ( 1 << i - 1 )][T]);
Add(trans[S][T], trans[S][T | ( 1 << i - 1 )]);
}
if ( !T )
break;
}
if ( !S )
break;
}
}
}
for ( int S = P; ; S = Next(P, S) )
{
for ( int w1 = S; ; w1 = Next(S, w1) )
{
bool flag = false;
for ( int i = 1; i <= n; i ++ )
if ( P >> i - 1 & 1 )
flag |= ( S >> i - 1 & 1 ) && ( w1 >> i - 1 & 1 ) > ( up[i] >> bit & 1 );
if ( flag )
newS[S][w1] = -1;
else
{
newS[S][w1] = 0;
for ( int i = 1; i <= n; i ++ )
if ( P >> i - 1 & 1 )
if ( ( S >> i - 1 & 1 ) && ( w1 >> i - 1 & 1 ) == ( up[i] >> bit & 1 ) )
newS[S][w1] |= 1 << i - 1;
}
if ( !w1 )
break;
}
if ( !S )
break;
}
for ( int T = P; ; T = Next(P, T) )
{
for ( int w2 = T; ; w2 = Next(T, w2) )
{
bool flag = false;
for ( int i = 1; i <= n; i ++ )
if ( P >> i - 1 & 1 )
flag |= ( T >> i - 1 & 1 ) && ( w2 >> i - 1 & 1 ) < ( down[i] >> bit & 1 );
if ( flag )
newT[T][w2] = -1;
else
{
newT[T][w2] = 0;
for ( int i = 1; i <= n; i ++ )
if ( P >> i - 1 & 1 )
if ( ( T >> i - 1 & 1 ) && ( w2 >> i - 1 & 1 ) == ( down[i] >> bit & 1 ) )
newT[T][w2] |= 1 << i - 1;
}
if ( !w2 )
break;
}
if ( !T )
break;
}
for ( int S = P; ; S = Next(P, S) )
{
for ( int w1 = S; ; w1 = Next(S, w1) )
{
if ( newS[S][w1] != -1 )
{
for ( int T = P ^ S; ; T = Next(P ^ S, T) )
{
if ( f[now ^ 1][S][T] )
{
for ( int w2 = T; ; w2 = Next(T, w2) )
{
if ( newT[T][w2] != -1 )
Add(f[now][newS[S][w1] | add1][newT[T][w2] | add2], 1LL * f[now ^ 1][S][T] * trans[w1 | w2][( S | T ) ^ ( w1 | w2 )] % mod);
if ( !w2 )
break;
}
}
if ( !T )
break;
}
}
if ( !w1 )
break;
}
if ( !S )
break;
}
if ( !k )
break;
}
}
int ans = 0;
for ( int S = 0; S <= sum; S ++ )
for ( int T = 0; T <= sum; T ++ )
Add(ans, f[now][S][T]);
printf("%d\n", ans);
return 0;
}
T2 Light
比较显然的暴力是 \(O(n^2)\) 进行 Bfs ，正解考虑优化这个过程。
容易发现到达一段连续的无障碍物的格子所需时间相同，因此考虑将二维平面横着划分为 \(O(n+k)\) 个连续的无障碍物的格子，同时竖着划分为 \(O(n+k)\) 个连续的无障碍物的格子，仍然维护队列进行 Bfs ，每次取出连续的一段，如果取出的一段方向为横着，那么查询所有没有被访问过的与这条线段有交的竖着的线段并将他们塞进队列中。很容易使用树套树将上述过程优化为 \(O(n\log^2n)\) 。
统计答案考虑每个点会被一条竖着和一条横着的线段覆盖，并且这两条线段距离为 \(x,x+1\) ，其中 \(x\) 为这个点的贡献，因此构造函数 \(f(x)=\tfrac{x(x-1)}{2}\) ，容易发现直接对线段贡献加和即可得到答案。
code
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
using namespace std;
const int max1 = 1e5;
const int mod = 998244353;
int T, n, m;
vector <int> binx[max1 + 5], biny[max1 + 5];
struct Segment
{
int x, L, R;
Segment () {}
Segment ( int __x, int __L, int __R )
{ x = __x, L = __L, R = __R; }
bool operator < ( const Segment &A ) const
{
return x < A.x;
}
};
struct Data
{
Segment s;
int opt, dis;
Data () {}
Data ( Segment __s, int __opt, int __dis )
{ s = __s, opt = __opt, dis = __dis; }
};
queue <Data> que;
struct Segment_Tree
{
#define lson(now) ( now << 1 )
#define rson(now) ( now << 1 | 1 )
multiset <Segment> tree[max1 * 4 + 5];
void Build ( int now, int L, int R )
{
tree[now].clear();
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 ql, int qr, int x )
{
if ( L >= ql && R <= qr )
{
tree[now].insert(Segment(x, ql, qr));
return;
}
int mid = L + R >> 1;
if ( ql <= mid )
Insert(lson(now), L, mid, ql, qr, x);
if ( qr > mid )
Insert(rson(now), mid + 1, R, ql, qr, x);
return;
}
void Delete ( int now, int L, int R, int ql, int qr, int x )
{
if ( L >= ql && R <= qr )
{
tree[now].erase(tree[now].find(Segment(x, ql, qr)));
return;
}
int mid = L + R >> 1;
if ( ql <= mid )
Delete(lson(now), L, mid, ql, qr, x);
if ( qr > mid )
Delete(rson(now), mid + 1, R, ql, qr, x);
return;
}
Segment Query ( int now, int L, int R, int pos, int ql, int qr )
{
if ( !tree[now].empty() )
{
Segment tmp = *--tree[now].end();
if ( tmp.x >= ql )
{
tmp = *tree[now].lower_bound(Segment(ql, 0, 0));
if ( tmp.x <= qr )
return tmp;
}
}
if ( L == R )
return Segment(-1, -1, -1);
int mid = L + R >> 1;
if ( pos <= mid )
return Query(lson(now), L, mid, pos, ql, qr);
return Query(rson(now), mid + 1, R, pos, ql, qr);
}
}Treex, Treey;
void Work ()
{
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
{
binx[i].clear(), biny[i].clear();
binx[i].push_back(n + 1);
biny[i].push_back(n + 1);
}
for ( int i = 1, x, y; i <= m; i ++ )
{
scanf("%d%d", &x, &y);
binx[x].push_back(y);
biny[y].push_back(x);
}
Treex.Build(1, 1, n);
Treey.Build(1, 1, n);
while ( !que.empty() )
que.pop();
for ( int i = 1; i <= n; i ++ )
{
sort(binx[i].begin(), binx[i].end());
int pre = 0;
for ( auto v : binx[i] )
{
if ( pre + 1 <= v - 1 )
Treex.Insert(1, 1, n, pre + 1, v - 1, i);
pre = v;
}
}
for ( int i = 1; i <= n; i ++ )
{
sort(biny[i].begin(), biny[i].end());
int pre = 0;
for ( auto v : biny[i] )
{
if ( pre + 1 <= v - 1 )
Treey.Insert(1, 1, n, pre + 1, v - 1, i);
pre = v;
}
}
Treey.Delete(1, 1, n, 1, biny[1].front() - 1, 1);
que.push(Data(Segment(1, 1, biny[1].front() - 1), 2, 0));
long long ans = 0;
while ( !que.empty() )
{
Segment now = que.front().s;
int opt = que.front().opt, dis = que.front().dis;
que.pop();
ans += 1LL * ( now.R - now.L + 1 ) * dis * ( dis - 1 ) / 2;
if ( opt == 1 )
{
while ( true )
{
Segment v = Treey.Query(1, 1, n, now.x, now.L, now.R);
if ( v.x == -1 )
break;
Treey.Delete(1, 1, n, v.L, v.R, v.x);
que.push(Data(v, 2, dis + 1));
}
}
else
{
while ( true )
{
Segment v = Treex.Query(1, 1, n, now.x, now.L, now.R);
if ( v.x == -1 )
break;
Treex.Delete(1, 1, n, v.L, v.R, v.x);
que.push(Data(v, 1, dis + 1));
}
}
}
ans %= mod;
printf("%lld\n", ans);
return;
}
int main ()
{
freopen("light.in", "r", stdin);
freopen("light.out", "w", stdout);
scanf("%d", &T);
while ( T -- )
Work();
return 0;
}
T3 Game
考虑固定根节点求解答案。
考虑枚举最终小 P 和小 L 的得分 \((a,b)\) ，不妨设目前到达了 \(u\) 子树，那么这个子树需要满足小 L 的策略不变，不管小 P 如何改变策略，小 P 的得分永远无法超过 \(a\) ，这和小 P 之前的决策以及 \(b_i\) 没有关系，考虑 dp 计算此时得分下的所有 \(a_i\) 和小 L 的策略的方案数。设 \(f_{u,a}\) 表示当前决策到 \(u\) 子树，不论小 P 如何操作，小 P 得分均不超过 \(a\) 的方案数，转移考虑当前子树 \(u\) 如果是小 P 决策，有 \(f_{u,a}=f_{v_1,a}\times f_{v_2,a}\) ，表示不论小 P 的策略是什么，其得分不能超过 \(a\) ；当前子树 \(u\) 如果是小 L 决策，有 \(f_{u,a}=f_{v_1,a}\times w_{v_2}+f_{v_2,a}\times w_{v_1}\) ，其中 \(w_u\) 表示在 \(u\) 子树内随意选择 \(a_i\) 以及小 L 策略的方案数。
同理我们预处理 \(g_{u,b}\) 表示决策到 \(u\) 子树，不论小 L 如何操作，小 L 得分不超过 \(b\) 的方案数。
此时考虑计算答案，设 \(h_{u,a,b}\) 表示决策到 \(u\) 子树，小 P 得分为 \(a\) ，小 L 得分为 \(b\) 的方案数，假设 \(u\) 子树轮到小 P 进行决策，那么有转移 \(h_{u,a,b}=h_{v_1,a,b}\times f_{v_2,a}+h_{v_2,a,b}\times f_{v_1,a}\) 。
根据某些神奇的结论， \(f,g,h\) 均为关于 \(a,b\) 的长度为 \(n\) 的多项式，因此直接按照系数表达式转移 dp ，复杂度为 \(O(n^3)\) 。
思考目前的限制是什么：
最终小 P 得分为 \(a\) ，小 L 得分为 \(b\) ；
不论小 P 如何改变策略，小 P 得分无法超过 \(a\) ；
不论小 L 如何改变策略，小 L 得分无法超过 \(b\) 。
考虑去掉第一种限制，此时对于每个小于 \(a\) 的得分 \(a_i\) 以及每个小于 \(b\) 的得分 \(b_i\) 之前全部等效，直接 dp 可以计算小 P 得分无法超过 \(a\) ，小 L 得分无法超过 \(b\) 的方案数，猜测一个结论：当前计算的方案数除以 \(ab\) 就是小 P 得分恰好为 \(a\) ，小 L 得分恰好为 \(b\) 的方案数。
因此我们实际上计算 \(\sum_{a=1}^{k}\sum_{b=1}^{k}\tfrac{f_{u}(a)}{a}\tfrac{g_{u}(b)}{b}\) ，因此考虑计算 \(\sum_{a=1}^{k}\tfrac{f_{u}(a)}{a}\) ，直接维护多项式 \(\tfrac{f_u(x)}{x}\) ，那么我们需要求解 \(\sum_{i=0}^mf_i\sum_{a=1}^ka^i\) 。
考虑预处理幂和，简单推式子有：
容易发现 \((k+1)^{\underline{w+1}}\) 一定包含 \(w+1\) 的倍数，因此可以直接计算。
code
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int max1 = 1e4;
int n, k, mod;
vector <int> edge[max1 + 5];
int ans[max1 + 5];
int S[max1 + 5][max1 + 5], C[max1 + 5], D[max1 + 5];
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;
}
struct Poly
{
int len, A[max1 + 5];
Poly operator * ( const Poly &tmp ) const
{
Poly res;
res.len = len + tmp.len;
for ( int i = 0; i <= res.len; i ++ )
res.A[i] = 0;
for ( int i = 0; i <= len; i ++ )
for ( int j = 0; j <= tmp.len; j ++ )
res.A[i + j] = ( res.A[i + j] + 1LL * A[i] * tmp.A[j] ) % mod;
return res;
}
Poly operator * ( const int &tmp ) const
{
Poly res;
res.len = len;
for ( int i = 0; i <= len; i ++ )
res.A[i] = 1LL * A[i] * tmp % mod;
return res;
}
Poly operator + ( const Poly &tmp ) const
{
Poly res;
res.len = max(len, tmp.len);
for ( int i = 0; i <= res.len; i ++ )
{
res.A[i] = 0;
if ( i <= len )
Add(res.A[i], A[i]);
if ( i <= tmp.len )
Add(res.A[i], tmp.A[i]);
}
return res;
}
Poly operator << ( const int &x ) const
{
Poly res;
res.len = len + x;
for ( int i = 0; i <= x - 1; i ++ )
res.A[i] = 0;
for ( int i = 0; i <= len; i ++ )
res.A[i + x] = A[i];
return res;
}
int Calc ()
{
int res = 0;
for ( int i = 0; i <= len; i ++ )
res = ( res + 1LL * A[i] * D[i] ) % mod;
return res;
}
};
int f[max1 + 5][2], g[max1 + 5][2];
Poly F[max1 + 5][2], G[max1 + 5][2];
void Dfs ( int now )
{
if ( edge[now].empty() )
{
f[now][0] = f[now][1] = k;
g[now][0] = g[now][1] = k;
F[now][0].len = 0;
F[now][0].A[0] = 1;
F[now][1].len = 0;
F[now][1].A[0] = 1;
G[now][0].len = 0;
G[now][0].A[0] = 1;
G[now][1].len = 0;
G[now][1].A[0] = 1;
ans[now] = 1LL * F[now][0].Calc() * G[now][0].Calc() % mod;
return;
}
Dfs(edge[now][0]);
Dfs(edge[now][1]);
f[now][0] = 1LL * f[edge[now][0]][1] * f[edge[now][1]][1] % mod;
f[now][1] = 2LL * f[edge[now][0]][0] * f[edge[now][1]][0] % mod;
g[now][0] = 2LL * g[edge[now][0]][1] * g[edge[now][1]][1] % mod;
g[now][1] = 1LL * g[edge[now][0]][0] * g[edge[now][1]][0] % mod;
F[now][1] = F[edge[now][0]][0] * f[edge[now][1]][0] + F[edge[now][1]][0] * f[edge[now][0]][0];
F[now][0] = F[edge[now][0]][1] * F[edge[now][1]][1]; F[now][0] = F[now][0] << 1;
G[now][1] = G[edge[now][0]][0] * G[edge[now][1]][0]; G[now][1] = G[now][1] << 1;
G[now][0] = G[edge[now][0]][1] * g[edge[now][1]][1] + G[edge[now][1]][1] * g[edge[now][0]][1];
ans[now] = 1LL * F[now][0].Calc() * G[now][0].Calc() % mod;
return;
}
int main ()
{
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
scanf("%d%d%d", &n, &k, &mod);
for ( int i = 2, u; i <= n; i ++ )
{
scanf("%d", &u);
edge[u].push_back(i);
}
S[0][0] = 1;
for ( int i = 1; i <= n >> 1; i ++ )
for ( int j = 1; j <= i; j ++ )
S[i][j] = ( S[i - 1][j - 1] + 1LL * S[i - 1][j] * j ) % mod;
for ( int i = 0; i <= n >> 1; i ++ )
{
if ( !( k + 1 - i ) )
break;
C[i] = 1;
for ( int j = 0; j <= i; j ++ )
{
if ( ( k + 1 - j ) % ( i + 1 ) )
C[i] = 1LL * C[i] * ( k + 1 - j ) % mod;
else
C[i] = 1LL * C[i] * ( ( k + 1 - j ) / ( i + 1 ) ) % mod;
}
}
for ( int i = 0; i <= n >> 1; i ++ )
for ( int j = 0; j <= i; j ++ )
D[i] = ( D[i] + 1LL * S[i][j] * C[j] ) % mod;
D[0] = ( D[0] + mod - 1 ) % mod;
Dfs(1);
for ( int i = 1; i <= n; i ++ )
printf("%d\n", ans[i]);
return 0;
}