COE IV C 罚球

Alarm5854 · 2021-09-03 21:51:26 · 题解

来自本题出题人官方题解，过了近两个月才想起来发，写得很丑，赛时果然被爆标了。

题意

一开始有一个带 n 个点的环，从 1 到 n 顺时针排列。

设上一个点返回的状态为 x，则：

• 若 x=1，则这个环上第 i 个点有 \dfrac{a_i}{1000} 的概率返回 1 且删除这个点，有 \dfrac{b_i}{1000} 的概率返回 1 但保留这个点，有 \dfrac{1000-a_i-b_i}{1000} 的概率返回 2 且保留这个点。
• 若 x=2，则这个环上第 i 个点有 \dfrac{a_i+b_i}{1000} 的概率返回 1 且删除这个点，有 \dfrac{1000-a_i-b_i}{1000} 的概率返回 2 且保留这个点。

初始 x=1，从 1 号点开始进行上述操作，操作完后找到沿顺时针方向下一个点，这个点成为下一个操作的点。

求只剩一个点的期望操作次数，若期望次数为无穷大，输出 -1，否则输出这个概率对 10^6+33 取模的值，可以证明答案为有理数。

前置知识

期望，状压，高斯消元。

子任务 1

很明显，一开始就只有一个点，期望改变状态次数为 0。

期望得分 2 分。

子任务 2

这时每个点肯定会返回 2 且被保留，因此当 n>1 时期望次数为无穷大，n=1 时期望次数为 0。

期望得分 4 分（这里的期望得分均为结合前面的子任务的得分）。

子任务 3

这时每个点肯定会返回 1 且被删除，因此到 n 号点的时候就只剩一个点了，答案即为 n-1。

期望得分 8 分。

子任务 4

这时每个点肯定会返回 1 且被保留，因此情况同子任务 2。

期望得分 12 分。

子任务 5

这时 1 号点一直返回 2，设这是第 i 圈，则 i+1 号点会返回 1 并被删除，i+2\sim n 会返回 1 并被保留。第 i(i<n) 圈的操作次数为 n-i+1，第 n 圈不用操作，故答案为 \dfrac{n(n+1)}{2}-1。

期望得分 18 分。

子任务 6

这时每个点都本质相同，且没有任何点返回 2，设 f(n) 为剩 n 个点时的期望次数，则

得出

期望得分 24 分。

子任务 7

这时每个点仍然本质相同，设 f(n) 为剩 n 个点，且 x=1 的期望次数，g(n) 为剩 n 个点，且 x=2 的期望次数。

那么有

得出

期望得分 30 分。

子任务 8

其实就是子任务 6,7 的拓展版本，按照前面所说，则

解得

期望得分 49 分。

子任务 9

进入正题，由于 n\le11，于是可以想到状压。

从这里开始 a_i 表示前面的 a_{i+1}。

设 f(S,i) 表示剩余的点的状态为 S，现在在这个状态中第 i 个为 1 的地方 (0下标) ，上一个点的返回值为 1 的期望局数，g(S,i) 和 f(S,i) 的区别在于变成上一个点返回值为 2 的期望局数，则有：

这就是题目中的定义，f(S,i) 的转移为：

这样，可以考虑对于每一个 S\in[1,2^n),S\neq 2^k,k\in\mathbb{N}，都列出这样的 2\times |S| 元的线性方程，可以用高斯消元解决。

至于怎么高斯消元，需要对上述的式子进行变形：

这样就能够把高斯消元矩阵构造出来了，大小为 2n\times(2n+1)。

尤其需要注意的是如果出现了除以 0 的情况，一定要把这个答案弄成一个不在 [0,p) 范围内的数并进行特判，否则会出问题。

朴素的高斯消元复杂度为 O(n^3)，快速幂的复杂度为 O(\log p)，其中 \log p 与 n 同阶，故时间复杂度为 O(2^n\times n^4)（实际上是 O(2^n\times n^3\times \log p)）。

期望得分 75 分。

子任务 10

由于 p=10^6+33，所以考虑预处理逆元，这样可以将复杂度降至 O(2^n\times n^3)。

期望得分 83 分。

子任务 11

发现这个矩阵是个稀疏矩阵，每列非 0 的元素数量很少，对于一列为 0 的，就不需要进行减法，因为这是无效的，这样复杂度可以降至 O(2^n\times n^2)。

期望得分 100 分。

标程

//去掉注释后长度：2053字节
#include<ctime>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll p=1e6+33;
const ll N=18;
int read(){
    char c;
    int x=0,f=1;
    while(!isdigit(c=getchar()))
        f-=2*(c=='-');
    while(isdigit(c)){
        x=x*10+f*(c-48);
        c=getchar();
    }
    return x;
}
ll n,t,k,a[21],b[21],f[1<<N][21];
ll l[1<<N],g[1<<N],c[37][37],s[37];
ll inv[p];
void gauss(ll n){
    for(ll i=0;i<n;++i){
        ll t=i;
        for(ll j=i;j<n;++j){
            if(c[j][i]){
                t=j;
                break;
            }
        }
        if(!c[t][i])
            continue;
        swap(c[i],c[t]);
        for(ll j=i+1;j<n;++j){
            if(!c[j][i])//优化
                continue;
            ll x=c[j][i]*inv[c[i][i]];
            for(ll k=i;k<=n;++k){
                if(~c[j][k])
                    c[j][k]=(c[j][k]-x*c[i][k]%p+p)%p;
            }
        }
    }
    for(ll i=n-1;~i;--i){
        if(!c[i][i]||!~c[i][n])
            s[i]=-1;//这里的-1即为特殊值，需要特判
        else
            s[i]=c[i][n]*inv[c[i][i]]%p;
        if(!i)
            continue;
        for(ll j=i-1;~j;--j){
            if(~c[j][n]&&(~s[i]||!c[j][i]))//仍然需要特判-1
                c[j][n]=(c[j][n]-c[j][i]*s[i]%p+p)%p;
            else
                c[j][n]=-1;
            c[j][i]=0;
        }
    }
}
int main(){
    n=read();
    t=read();
    inv[1]=1;
    k=1<<n;
    for(ll i=2;i<p;++i)
        inv[i]=(p-p/i)*inv[p%i]%p;//线性处理逆元
    for(ll i=0;i<n;++i){
        a[i]=read()*inv[1000]%p;//提前进行转化
        b[i]=read()*inv[1000]%p;
    }
    for(ll i=1;i<k;++i)
        l[i]=l[i^(i&-i)]+1;
    for(ll i=0;i<n;++i)
        g[1<<i]=i;
    for(ll i=1;i<k;++i){
        if(l[i]==1)
            continue;
        memset(c,0,sizeof(c));//初始清空矩阵
        for(ll j=0,t=i;t;t^=t&-t,++j){
            ll x=g[t&-t];
            c[j*2][j*2]=1;
            c[j*2+1][j*2+1]=1;
            c[j*2][(j*2+2)%(l[i]*2)]=(p-b[x]%p)%p;
            c[j*2][(j*2+3)%(l[i]*2)]=(a[x]+b[x]-1+p)%p;//由于一开始进行了处理，所以就不再是a[x]+b[x]-1000了
            c[j*2+1][(j*2+3)%(l[i]*2)]=(a[x]+b[x]-1+p)%p;
            if(~f[i^(1<<x)][j%(l[i]-1)]||!a[x])
                c[j*2][l[i]*2]=(a[x]*f[i^(1<<x)][j%(l[i]-1)]+1)%p;
            else
                c[j*2][l[i]*2]=-1;
            if(~f[i^(1<<x)][j%(l[i]-1)]||!(a[x]+b[x]))
                c[j*2+1][l[i]*2]=((a[x]+b[x])*f[i^(1<<x)][j%(l[i]-1)]+1)%p;
            else
                c[j*2+1][l[i]*2]=-1;
        //c[j*2]为f所对应的位置，c[j*2+1]为g所对应的位置
        }
        gauss(l[i]*2);
        for(int j=0;j<l[i];++j)
            f[i][j]=s[j*2];
    }
    printf("%lld\n",f[k-1][0]);
    return 0;
}