扫雷题解

题目大意

$a_{i,j}\in[0,1]$ 表示该格是否有雷，$b_{i,j}$ 为该格所处九宫格内雷的数量。对于所有可能的 $a$，求出 $\sum b_{i,j}$ 的总和 $(\bmod 998244353)$。

$n\leq 10^{20090327}$

Solution

首先明确一点，矩阵上有角落、棱、内部三种区划，该区划内联通的格子数分别为 $4$、$6$、$9$。

题目要求的是这个：$\sum\limits_a \sum\limits_i \sum\limits_j b_{i,j}$，我们单独去分析一个格点可能的情况：

设该格点联通格子数量为 $k$，那么可以遍历雷的数量 $i\in [0,k-1]$。首先明显的是联通格子外的点可以随便放，即 $2^{n^2-k}$。接着我们考虑联通格子内，共有 $\binom{k-1}{i}$ 种可能，雷的数量 $i$ 即对这个格子的贡献。所以可得下式：

$$ \sum\limits_{i=0}^{k-1} 2^{n^2-k}\binom{k-1}{i}i $$

提一个 $2^{n^2}$ 出来：

$$ 2^{n^2}\sum\limits_{i=0}^{k-1} 2^{-k}\binom{k-1}{i}i $$

这个式子在乘上情况数量就是 $\sum\limits_a\sum\limits_i\sum\limits_j b_{i,j}$ 了。

因为 $k$ 仅可能为 $4$、$6$、$9$，所以我们一个一个求出来这三种情况的贡献。

考虑三种情况的数量，这是十分显然的。角落就是 $4$ 个，棱共有 $4(n-2)$ 个，内部共 $(n-2)^2$ 个。把这些数量分别乘上对应的贡献加起来就好了。

最后的答案要乘上一个 $2^{n^{2}}$，因为刚刚提出来了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include<bits/stdc++.h>
using namespace std;

#define int long long

const int P=998244353,phi=998244352,N=1e3+5;

string s;
int n,m;
int res[6]={0,0,48,5120,1376256,209715199};
int ans;

int qpow(int a,int b)
{
    int c=1;
    for(;b;b>>=1,a=a*a%P)
        if(b&1)
            c=c*a%P;
    return c;
}

signed main()
{
    cin>>s;
    int len=(int)s.size();
    for(int i=0;i<len;i++)
        n=(n*10%P+(s[i]^48))%P;
    for(int i=0;i<len;i++)
        m=(m*10%phi+(s[i]^48))%phi;
    if(n<=5)
        return printf("%lld\n",res[n]),0;
    int t4=qpow(2,phi-4)*12%P;
    int t6=qpow(2,phi-6)*80%P;
    int t9=qpow(2,phi-9)*1024%P;
    (ans+=t4*4)%=P;
    (ans+=t6*4%P*(n-2)%P)%=P;
    (ans+=t9*qpow(n-2,2)%P)%=P;
    ans=ans*qpow(2,m*m%phi)%P;
    printf("%lld\n",ans);
    return 0;
}