2018.8.18T3（容斥）

矩阵（matrix）

【题目描述】
有一个 n 行 m 列的矩阵，你需要将每一格染上黑色或白色。
有 q 次询问，每次询问给出 ai,bi，你需要求出至少有 ai 行，至少
有 bi 列全是黑格的方案数。对 998244353 取模。
【输入数据】
第一行三个整数 n，m，q，接下来 q 行每行两个整数 ai，bi
【输出数据】
q 行，每行一个整数表示答案。
【样例输入】
3 4 1
1 2
【样例输出】
169
【数据范围】
测试点编号 特殊条件

对于 100%的数据，0<=ai<=n，0<=bi<=m

---

考试的时候受到了T1的影响，没有来推这题的式子…
其实这题很好想

我们的思路肯定是强制某些行必须染满，某些列也必须染满，算出对应的贡献之后把重复的容斥掉
我们先不考虑重复的影响，我们考虑单个情况的贡献
假设我们强制x$x$行y$y$列必须染满(x>=ai,y>=bi)$(x>=a_i,y>=b_i)$，剩下的随意
那么这种情况对应的贡献就是
Cxn∗Cym∗2(n−x)(m−y)$C_n^x\ast C_m^y\ast 2^{(n-x)(m-y)}$

现在棘手的问题是怎么进行容斥，也就是没选取一对x,y$x,y$，他贡献的系数到底是多少
我们从小到大枚举x,y$x,y$我们保证每次当前的行列的答案正确，对后面的影响我们到后面进行容斥
我们考虑对于任意ai<=x′<x,bi<=y′<y$a_i<=x^{\prime }<x,b_i<=y^{\prime }<y$的(x′,y′)$(x^{\prime },y^{\prime })$
他的答案对(x,y)$(x,y)$的影响
显而易见的，由于其他的格子我们允许随意染色，故对于x′,y′$x^{\prime },y^{\prime }$，如果他的贡献系数为fx′,y′$f_{x^{\prime },y^{\prime }}$，他会导致x,y$x,y$的答案也被算了fx′,y′$f_{x^{\prime },y^{\prime }}$次
但是这样仍然不好处理并且空间时间都不能接受，我们可以把行列分开处理
这样时间和空间上都能接受，最后把两种的贡献乘起来即可

我们理一下思路
对于x$x$行，我们令faix$f_x^{a_i}$表示对应的贡献系数，令fbiy$f_y^{b_i}$表示列的贡献系数
那么ans=∑nx=aifaix∗Cxn∗∑my=bi∗fbiy∗Cym∗2(n−x)(m−y)$ans=\sum _{x=a_i}^n{f}_x^{a_i}\ast C_n^x\ast \sum _{y=b_i}^m\ast f_y^{b_i}\ast C_m^y\ast 2^{(n-x)(m-y)}$
组合数和2的幂都和a,b$a,b$无关，我们可以预处理出来
我们现在细致的思考怎么计算faix$f_x^{a_i}$
其实这部分和之前行列同时考虑类似
对于任意a<=x′<=x$a<=x^{\prime }<=x$，他都会使当前的贡献减去对应的系数
同时这x′$x^{\prime }$行是在x$x$行里任选的，所以我们还要乘以一个组合数
所以faix=1−∑x−1x′=aifaix′∗Cx′x$f_x^{a_i}=1-\sum _{x^{\prime }=a_i}^{x-1}{f}_{x^{\prime }}^{a_i}\ast C_x^{x^{\prime }}$
fbiy$f_y^{b_i}$同理

代码中fa$fa$数组表示fax$f_x^a$，fb$fb$数组表示fby$f_y^b$
gi,j$g_{i,j}$表示Cin∗Cjm∗2(n−i)(m−j)$C_n^i\ast C_m^j\ast 2^{(n-i)(m-j)}$

这题时限卡得比较紧，如果全开long$long$ long$long$并且写得不优美的话可能会挂

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,j,k) for(int i = j;i <= k;++i)
#define repp(i,j,k) for(int i = j;i >= k;--i)
#define rept(i,x) for(int i = linkk[x];i;i = e[i].n)
#define P pair<int,int>
int C[4010][4010] , fa[4010] , fb[4010] , g[4010][4010] , mi[16000100];
int n , m;
int ans;
const int p = 998244353;

namespace fastIO{
    #define BUF_SIZE 100000
    #define OUT_SIZE 100000
    bool IOerror = 0;
    inline char nc(){
        static char buf[BUF_SIZE],*p1 = buf+BUF_SIZE, *pend = buf+BUF_SIZE;
        if(p1 == pend){
            p1 = buf; pend = buf+fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1){ IOerror = 1; return -1;}
        }
        return *p1++;
    }
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){
        bool sign = 0; char ch = nc(); x = 0;
        for(; blank(ch); ch = nc());
        if(IOerror)return;
        if(ch == '-') sign = 1, ch = nc();
        for(; ch >= '0' && ch <= '9'; ch = nc()) x = x*10+ch-'0';
        if(sign) x = -x;
    }
    inline void read(ll &x){
        bool sign = 0; char ch = nc(); x = 0;
        for(; blank(ch); ch = nc());
        if(IOerror) return;
        if(ch == '-') sign = 1, ch = nc();
        for(; ch >= '0' && ch <= '9'; ch = nc()) x = x*10+ch-'0';
        if(sign) x = -x;
    }
    #undef OUT_SIZE
    #undef BUF_SIZE
};
using namespace fastIO;
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    read(n);read(m);
    int tmp = max(n,m);
    C[0][0] = 1;
    mi[0] = 1;
    rep(i,1,n*m) mi[i] = (mi[i-1]<<1)%p;
    rep(i,1,tmp)
    {
        C[i][0] = C[i][i] = 1;
        rep(j,1,i-1)
            C[i][j] = (C[i-1][j] + C[i-1][j-1])%p;
    }   
    rep(i,0,n) rep(j,0,m) 
    g[i][j] = (ll)C[n][i] * C[m][j] % p*mi[(n-i)*(m-j)]%p;
    int q;read(q);
    rep(x,1,q)
    {
        int a,b;read(a); read(b);
        fa[a] = 1;
        rep(i,a+1,n)
        {
            fa[i] = 1;
            rep(j,a,i-1)
                fa[i] = ((fa[i] - (ll)fa[j] * C[i][j]%p)%p + p)%p;
        }
        fb[b] = 1;
        rep(i,b+1,m)
        {
            fb[i] = 1;
            rep(j,b,i-1)
                fb[i] = ((fb[i] - (ll)fb[j] * C[i][j]%p)%p + p)%p;
        }
        ans = 0;
        rep(i,a,n)
            rep(j,b,m)
                ans = (ans + (ll)g[i][j] * fa[i]%p * fb[j])%p;
        printf("%d\n",ans);
    }
    return 0;
}