【题解】洛谷 P7245 灯光效果

· · 题解

分析 + 题解

容易发现，被操作的区域恰好可以分成 (m-1)^2 个子矩阵，其中每个子矩阵总是同时异或 1。

具体地，对于所有满足 1 \le i < m，1 \le j < m 的 (i,j)，以 (x_i+1,y_j+1)，(x_{i+1},y_{j+1}) 为顶点的子矩阵满足上述条件。

枚举 (i,j)，该子矩阵元素个数为 (x_{i+1}-x_i)(y_{j+1}-y_j)，在一次操作中被异或 1 的概率为 p=\dfrac{ij(m-i)(m-j)}{(C_m^2)^2}。

说明：一共有 (C_m^2)^2 种选择，其中 i_1 \le i，j_1 \le j，i_2 > i，j_2 > j 的情况有 ij(m-i)(m-j) 种。

设 k 次操作后该子矩阵为全 1（异或了奇数次 1）的概率为 f(p)，则答案为 \sum_{(i,j)} cnt \times f(p)，而 f(p) 可以通过一个简单的 DP（严格来说算递推）求得：

设 dp[i][j] 表示第 i 次操作后该子矩阵为全 j 的概率，则有：

dp[i][j]=dp[i-1][1-j] \times p +dp[i-1][j] \times (1-p)

其中 f(p)=dp[k][1]。但这样单次计算是 O(k) 的，不足以通过此题（可以得到 60 分）。

构造如下矩阵，使用矩阵快速幂即可在 O(log_2k) 时间复杂度内进行单次计算。

1-p&p\\ p&1-p \end{bmatrix}

总时间复杂度为 O(m^2 log_2k)。

代码

如果还有不清楚的，就看代码吧。

#include<bits/stdc++.h>
using namespace std;
const int P=998244353;
inline void add(int &a,int b)
{
    a=a+b-(a+b>=P?P:0);
}
inline void mul(int &a,int b)
{
    a=1ll*a*b%P;
}
inline int get_sum(int a,int b)
{
    return a+b-(a+b>=P?P:0);
}
inline int get_product(int a,int b)
{
    return 1ll*a*b%P;
}
inline int get_square(int x)
{
    return get_product(x,x);
}
inline int get_power(int a,int n)
{
    int res=1;
    while(n>0)
    {
        res=(n&1)?get_product(res,a):res;
        mul(a,a);
        n>>=1;
    }
    return res;
}
inline int get_inv(int x)
{
    return get_power(x,P-2);
}
//以上是模运算中的加、乘、平方、快速幂、求逆 
const int max_m=1e3+5;
int x[max_m],y[max_m];
struct matrix
{
    int v[2][2];
    inline matrix(int p=0)//matrix 的构造函数，用概率 p 构造上述矩阵 
    {
        v[0][0]=v[1][1]=P+1-p;
        v[0][1]=v[1][0]=p;
    }
};
inline matrix operator * (const matrix &a,const matrix &b)//定义矩阵乘法 
{
    static matrix res;//static 变量会沿用上一次的结果，若需初始化必须在定义后赋值 
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
        {
            res.v[i][j]=0;
            for(int k=0;k<2;++k)
                add(res.v[i][j],get_product(a.v[i][k],b.v[k][j]));
        }
    return res;
}
inline matrix get_power(matrix a,int n)//矩阵快速幂 
{
    static matrix res;
    res.v[0][0]=1;
    res.v[0][1]=res.v[1][0]=res.v[1][1]=0;
    while(n)
    {
        if(n&1)
            res=res*a;
        a=a*a;
        n>>=1;
    }
    return res;
}
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k); 
    for(int i=1;i<=m;++i)
        scanf("%d",x+i);
    for(int i=1;i<=m;++i)
        scanf("%d",y+i);
    int inv_all=get_square(get_inv((1ll*m*(m-1)>>1)%P));//概率的分母 
    int ans=0;
    for(int i=1;i<m;++i)
        for(int j=1;j<m;++j)
        {
            int cnt=get_product(x[i+1]-x[i],y[j+1]-y[j]);//元素个数 
            int p=get_product(get_product(get_product(i,j),get_product(m-i,m-j)),inv_all);//概率 
            add(ans,get_product(cnt,get_power(matrix(p),k).v[0][1]));
        }
    printf("%d\n",ans);
    return 0;
}