ABC216H - Random Robots(容斥,状压DP)
阅读原文时间:2023年07月10日阅读:2

题面

K

K

K 个机器人初始分别位于数轴上

x

1

,

x

2

,

.

.

.

,

x

K

x_1,x_2,…,x_{K}

x1​,x2​,…,xK​ 的整点位置。

接下来会经历

N

N

N 秒,每一秒都会发生如下事件:

  • 每个机器人分别有一半的概率停住不动,有一般的概率往坐标轴正方向移动一单位距离。每个机器人的移动是同时进行的。

问机器人互相不碰撞的概率是多少。对

998244353

998244353

998244353 取模。

2

K

10

,

1

N

1000

,

0

x

1

<

x

2

<

.

.

.

<

x

K

1000

.

2\leq K\leq10,1\leq N\leq1000,0\leq x_1<x_2<…<x_K\leq1000\,.

2≤K≤10,1≤N≤1000,0≤x1​<x2​<…<xK​≤1000.

题解

听说要用

L

G

V

\tt LGV

LGV ?听他吹吧

还是离得挺远的,只是用了下

L

G

V

\tt LGV

LGV 引理的核心——容斥原理罢了。

把问题转化到二维平面,每个机器人在

x

x

x 轴方向照常,在

y

y

y 轴方向每秒都前进一格。看起来是不是很像

L

V

G

\tt LVG

LVG 的问题了?但这样完全没用。

我们把最终的机器人序列从左到右记录为

P

P

P,为了利用容斥原理,我们定义一个不合法条件为某个逆序对是否存在,因为存在某个逆序对,可以等价于两个机器人相撞,而最终答案不受影响。可以用

L

G

V

LGV

LGV 引理的路径交换思想加深理解。

形式化地,我们可以把答案表示为:

P

,

Q

(

1

)

σ

(

P

)

(

1

2

)

N

K

i

=

1

K

C

(

N

,

Q

i

x

i

)

\sum_{P,Q} (-1)^{σ(P)}\cdot(\frac{1}{2})^{NK}\cdot\prod_{i=1}^K {\rm C}(N,Q_i-x_i)

P,Q∑​(−1)σ(P)⋅(21​)NK⋅i=1∏K​C(N,Qi​−xi​)

序列

Q

Q

Q 是最终的位置序列,是递增的,中间的

(

1

2

)

N

K

(\frac{1}{2})^{NK}

(21​)NK 是一个方案的概率,右边用组合数算出了每种

(

P

,

Q

)

(P,Q)

(P,Q) 的情况数。

现在,我们面前有两个艰难的选择:壹,用状态压缩DP来模拟排列

P

P

P 的形成,同时用DP模拟序列

Q

Q

Q 的形成;贰,无比简单地直接枚举排列,然后计算别的,序列

Q

Q

Q 、组合数……

后者,

n

!

n!

n! 直接达到了

3

e

6

3e6

3e6 级别,后面的没法算了。所以我们选择前者。定义

d

p

[

S

]

[

j

]

dp[S][j]

dp[S][j] 表示当前已经往排列中(从左往右)填入的机器人集合为

S

S

S,同时最靠右的机器人最终位置

j

\leq j

≤j 的带权方案数。加入一个机器人,可以通过

S

S

S 算出前面比它标号大的个数,维护逆序对,而且它的最终位置要比前面的都靠右,所以很好维护,我们令

d

(

S

,

i

)

d(S,i)

d(S,i) 表示

S

S

S 中比

i

i

i 标号大的机器人个数,有如下转移:

d

p

[

S

]

[

j

]

=

d

p

[

S

]

[

j

1

]

+

i

S

(

1

)

d

(

S

,

i

)

d

p

[

S

i

]

[

j

1

]

C

(

N

,

j

x

i

)

(

1

2

)

N

dp[S][j]=dp[S][j-1]+\sum_{i\in S}(-1)^{d(S,i)}dp[\complement_S\,i][j-1]\cdot {\rm C}(N,j-x_i)\cdot (\frac{1}{2})^{N}

dp[S][j]=dp[S][j−1]  +  i∈S∑​(−1)d(S,i)dp[∁S​i][j−1]⋅C(N,j−xi​)⋅(21​)N

最终答案就是

d

p

[

U

]

[

max

x

+

N

]

dp[U][\max x+N]

dp[U][maxx+N] 取模

998244353

998244353

998244353 ,时间复杂度

O

(

2

K

K

N

)

{\rm O}(2^{K}KN)

O(2KKN) 。

如何评价 jiangly 说用

L

G

V

\tt LGV

LGV ,结果代码打的是状压DP ? 其实说的有道理。

CODE

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 1005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define SI(x) multiset<x>::iterator
#define MI map<int,int>::iterator
#define eps (1e-4)
#pragma GCC optimize(2)
LL read() {
    LL f=1,x=0;char s = getchar();
    while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
    while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
    return f*x;
}
void putpos(LL x) {
    if(!x) return ;
    putpos(x/10); putchar('0'+(x%10));
}
void putnum(LL x) {
    if(!x) putchar('0');
    else if(x < 0) putchar('-'),putpos(-x);
    else putpos(x);
}
void AIput(LL x,char c) {putnum(x);putchar(c);}

const int MOD = 998244353;
int n,m,s,o,k;
int dp[1<<10|5][MAXN<<1];
int fac[MAXN<<1],inv[MAXN<<1],invf[MAXN<<1];
int invp[MAXN<<1];
int C(int n,int m) {
    if(m < 0 || m > n) return 0;
    return fac[n] *1ll* invf[n-m] % MOD *1ll* invf[m] % MOD;
}
int F(int xx) {
    return C(m,xx) *1ll* invp[m] % MOD;
}
int xx[MAXN];
int main() {
    n = read(); m = read();
    for(int i = 1;i <= n;i ++) {
        xx[i] = read() + 1;
    }
    fac[0]=fac[1]=inv[0]=inv[1]=invf[0]=invf[1]=1;
    invp[0] = 1;
    for(int i = 2;i <= m+3;i ++) {
        fac[i] = fac[i-1] *1ll* i % MOD;
        inv[i] = (MOD-inv[MOD%i]) *1ll* (MOD/i) % MOD;
        invf[i] = invf[i-1] *1ll* inv[i] % MOD;
    }
    for(int i = 1;i <= m;i ++) invp[i] = invp[i-1] *1ll* inv[2] % MOD;
    dp[0][0] = 1;
    for(int j = 1;j <= m+1001;j ++) dp[0][j] = 1;
    int tp = (1<<n);
    for(int i = 1;i < tp;i ++) {
        for(int j = 1;j <= m+1001;j ++) {
            int kk = 1;
            dp[i][j] = dp[i][j-1];
            for(int k = n;k > 0;k --) {
                if(i & (1<<(k-1))) {
                    (dp[i][j] += kk*1ll*dp[i-(1<<(k-1))][j-1] % MOD *1ll* F(j-xx[k]) % MOD) %= MOD;
                    kk = MOD-kk;
                }
            }
        }
    }
    printf("%d\n",dp[tp-1][m+1001]);
    return 0;
}