题目传送门
分析：
我们考虑求最终交集恰好为某个矩形的答案
发现这玩意不好求，我们退而求其次
求最终交集包含某个矩形的答案
这个就可以做了，考虑一个全1矩形贡献范围为给一个矩形内部+1，差分一下变成两个角+1，两个角-1
差分后的贡献可以转化为一个全1矩形对左上右上左下右下的贡献，这个做四次单调栈DP就好了
一个(n*m)的矩形会被他内部:
(1*1)的矩形算(n*m)次
(1*2)的矩形算(n*(m-1))次
(2*1)的矩形算((n-1)*m)次
(2*2)的矩形算((n-1)*(m-1))次
发现(n*m+(n-1)*(m-1)-n*(m-1)-(n-1)*m=1)这个矩形就只被算一次了
于是我们求最终交集包含的矩形的答案，只需要求得大小为(1*1,1*2,2*1,2*2)的矩形的答案就好了
复杂度(O(n^2logK))
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#define maxn 2005
#define INF 0x3f3f3f3f
#define MOD 998244353
using namespace std;
inline int getint()
{
int num=0,flag=1;char c;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
return num*flag;
}
int n,m,K;
char s[maxn][maxn];
long long f[4][maxn][maxn],g[maxn][maxn];
int sum[maxn][maxn];
long long ans;
int stk[maxn],tp;
inline long long ksm(long long num,long long k)
{
long long ret=1;
for(;k;k>>=1,num=num*num%MOD)if(k&1)ret=ret*num%MOD;
return ret;
}
inline void solve()
{
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)sum[i][j]=(s[i][j]-48)?sum[i-1][j]+1:0;
for(int i=1;i<=n;i++)for(int j=1,cnt=tp=0;j<=m;j++)
{
while(tp&&sum[i][stk[tp]]>=sum[i][j])cnt-=sum[i][stk[tp]]*(stk[tp]-stk[tp-1]),--tp;
cnt+=sum[i][j]*(j-stk[tp]);
g[i][j]=cnt,stk[++tp]=j;
}
}
int main()
{
n=getint(),m=getint(),K=getint();
for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
solve();
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
f[0][i+1][j+1]+=g[i][j];
f[1][i][j+1]+=g[i][j];
f[2][i+1][j]+=g[i][j];
f[3][i][j]+=g[i][j];
}
for(int i=1;i<=n;i++)reverse(s[i]+1,s[i]+m+1);
solve();
for(int i=1;i<=n;i++)reverse(g[i]+1,g[i]+m+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
f[0][i+1][j]-=g[i][j];
f[1][i][j]-=g[i][j];
f[2][i+1][j]-=g[i][j];
f[3][i][j]-=g[i][j];
}
reverse(s+1,s+n+1);
solve();
reverse(g+1,g+n+1);
for(int i=1;i<=n;i++)reverse(g[i]+1,g[i]+m+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
f[0][i][j]+=g[i][j];
f[1][i][j]+=g[i][j];
f[2][i][j]+=g[i][j];
f[3][i][j]+=g[i][j];
}
for(int i=1;i<=n;i++)reverse(s[i]+1,s[i]+m+1);
solve();
reverse(g+1,g+n+1);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
f[0][i][j+1]-=g[i][j];
f[1][i][j+1]-=g[i][j];
f[2][i][j]-=g[i][j];
f[3][i][j]-=g[i][j];
}
for(int k=0;k<4;k++)
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
f[k][i][j]=f[k][i][j]-f[k][i-1][j-1]+f[k][i-1][j]+f[k][i][j-1];
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
ans=(ans+ksm(f[0][i][j]%MOD,K))%MOD;
ans=(ans-ksm(f[1][i][j]%MOD,K))%MOD;
ans=(ans-ksm(f[2][i][j]%MOD,K))%MOD;
ans=(ans+ksm(f[3][i][j]%MOD,K))%MOD;
}
printf("%lld
",(ans+MOD)%MOD);
}
