对称性和连通性看上去是没什么关系的问题，但是Zeratul为了强行出一道暴力题，想出了这样一个问题： 一个 n × n n×n的01矩阵，有多少种情况使得它满足： 这个01矩阵具有中心对称性，即旋转180度后不变。 这个矩阵不存在0，或者所有的0都在同一个四连块里。

这是一个有趣的问题！为了解决这个问题，我们可以考虑使用组合数学的方法。首先，我们来看中心对称性的情况。

对于一个 n × n 的矩阵来说，如果它具有中心对称性，那么对于每一个位置 (i, j)，都需要找到一个位置 (n-i+1, n-j+1)，使得它们的值相等。由于这个矩阵只包含 0 和 1，我们可以分两种情况讨论：

1. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 0，那么这两个位置可以是任意位置，所以有 2^(n^2/4) 种可能性。
2. 如果 (i, j) 和 (n-i+1, n-j+1) 的值都为 1，那么这两个位置也可以是任意位置，所以有 2^(n^2/4) 种可能性。

因此，对于中心对称性的情况，总共有 2^(n^2/4) × 2^(n^2/4) = 2^(n^2/2) 种可能性。

接下来，我们来看不存在 0 或所有的 0 在同一个四连块里的情况。

如果不存在 0，那么所有的位置都必须是 1，所以只有一种可能性。

如果所有的 0 都在同一个四连块里，那么这个四连块可以是任意大小的矩形，从 1 × 1 到 (n-1) × (n-1)。对于一个 k × k 的矩形来说，有 (n-k+1)^2 种可能性。所以，对于所有可能的 k，总共有 ∑[(n-k+1)^2] 种可能性。

综上所述，满足条件的矩阵总共有 2^(n^2/2) + 1 + ∑[(n-k+1)^2] 种可能性。

相关问题

Zeratul给出了一个数组a[1...n]。 你需要计算，这个数组除了a[i]a[i]以外，数组中其他数的总乘积是多少。答案对10^9取模。

答案是：

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000000
using namespace std;
const int maxn=1e5+5;
ll read(){ll ret=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}while(ch>='0'&&ch<='9'){ret=(ret<<1)+(ret<<3)+ch-'0';ch=getchar();}return ret*f;}
int n;
ll a[maxn];
ll pre[maxn],suf[maxn];
int main(){
    n=read();
    ll prod=1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        prod=prod*a[i]%MOD;
    }
    pre[0]=suf[n+1]=1;
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]*a[i]%MOD;
    for(int i=n;i>=1;i--) suf[i]=suf[i+1]*a[i]%MOD;
    for(int i=1;i<=n;i++){
        printf("%lld ",(prod*qpow(a[i],MOD-2)%MOD*pre[i-1]%MOD*suf[i+1]%MOD+MOD)%MOD);
    }
    printf("\n");
    return 0;
}

笑话时间：
我听说程序员们最怕的是紫屏。但是有时候出现一个紫屏非常的开心，因为它至少说明一个BUG，而不是苦于排除不知道在哪里的问题！

Zeratul有一个长度为n的字符串，字符串只包含0和1两种字符。 现在他想知道，这个字符串中有多少非空子串满足“0和1两种字符的个数相等”。

算法1：

暴力枚举

对于每个子串都判断一遍是否满足条件，时间复杂度O(n^3)。

算法2：

前缀和

对于每一个位置i，维护一个前缀和p[i]表示从1~i中0的个数减去1的个数。如果有一个子串s[l,r]满足0和1的个数相等，那么有p[r]-p[l-1]=0。因此我们可以枚举左右端点，然后计算前缀和之差是否为0。时间复杂度O(n^2)。

算法3：

哈希

我们可以将0视为-1，将1视为1，那么0和1个数相等的子串就是和为0的子串。因此我们可以维护一个前缀和q[i]表示从1~i的和，然后对于每个位置i，我们在之前出现过的所有位置中查找是否有一个位置j，使得q[i]-q[j]=0，如果有，那么i和j之间的子串就是一个满足条件的子串。我们可以用哈希表来维护之前出现过的每个前缀和所对应的位置。时间复杂度O(n)。

C++ 代码