CF1924 div1E 题解

· · 题解

题目链接

今天随便看到这题，就来口胡一下做法。

首先对于 nm\geq k 有一个显然的 DP，设答案为 f_{n,m}：

(n+m-2)(f_{n,m}-1)=\left(\sum_{i=0}^{n-1}f_{i,m}\right)+\left( \sum_{i=0}^{m-1}f_{n,i}\right)\quad \texttt{(1)}

而对于 nm<k 的地方取值为零，现在要考虑优化这个 DP。

尝试对 n,m 方向上各做一次差分，就可以发现对于充分大的 nm 有

f_{n,m}=f_{n-1,m}+f_{n,m-1}-f_{n-1,m-1} \quad \texttt{(2)}

说是充分大，实际上只要 n,m 在包围 nm<k 区域的轮廓线（轮廓线上的点本身有 nm\geq k）之外就有这个式子。如 n=23,m=15 时，设 a_{i,j} 表示 \texttt{(2)} 是否成立（成立为 0，不成立为 1）就得到了轮廓线：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 
0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

固定 k，则答案的生成函数可以表示为这种形式

F(x,y)=(x+y-xy)F(x,y)+R(x,y)

这里 R 就是一个补误差的项，顾及 \texttt{(2)} 不成立的情况。 也是一个二元幂级数，它只在轮廓线上的取值可能非零（因为 nm<k 的位置本身都是 0，做差分当然还是 0，没有影响）。设轮廓线的点集为 S_k，则

R(x,y)=\sum_{(i,j)\in S_k}[i\leq n][j\leq m](f_{i,j}-f_{i-1,j}-f_{i,j-1}+f_{i-1,j-1})x^iy^j

容易发现其只有 \Theta(n+m) 项，要提取 F 的 x^ny^m 系数，就只需要对若干连续的点 i,j 求出

[x^iy^j]\frac{1}{1-(x+y-xy)}

这个东西是什么？因为 1-(x+y-xy)=(1-x)(1-y)，所以它总是 1（对于自然数 i,j）。答案就是 R(1,1)。

至于轮廓线上的点怎么求 f 值，直接用 \texttt{(1)} 计算就可以。不过要注意使用前缀和优化一下。

回来补个代码，实现细节还是稍有点麻烦的：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#define N 2000003
#define ll long long
#define p 1000000007
using namespace std;

int inv[N];

void init(int n){
    inv[1] = 1;
    for(int i=2;i<=n;++i) inv[i] = (ll)(p-p/i)*inv[p%i]%p;
}

ll ans,k;
int n,m;
vector<int> fr[N>>1];
int st[N],len[N]; 

inline int F(const int& i,const int& j){
    if(j<st[i]||j-st[i]>=fr[i].size()) return 0;
    return fr[i][j-st[i]];
}

inline int G(const int& i,const int& j){
    return F(i,j)-F(i-1,j)-F(i,j-1)+F(i-1,j-1);
}

int main(){
    init(2000000);
    int T,px,py;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%lld",&n,&m,&k);
        if((ll)n*m<k){
            puts("0");
            continue;
        }
        if((ll)n*m==k){
            puts("1");
            continue;
        }
        if(n<m) swap(n,m);
        int fir = (k%n==0?k/n:k/n+1);
        st[fir-1] = n,ans = 0;
        for(int i=fir;i<=m;++i){
            st[i] = k%i==0?k/i:k/i+1; // 确定轮廓线在当前行的起始位置
            int L = st[i-1]-st[i]+1,sum = 0;
            fr[i].resize(L);
            if(st[i]<i){ // 利用对称性简化计算
                px = i,py = st[i];
                fr[i][0] = F(py,px);
            }else fr[i][0] = 1;
            sum = fr[i][0],ans += G(i,st[i]);
            for(int j=1;j<L-1;++j){
                fr[i][j] = (ll)sum*inv[i+j+st[i]-2]%p+1;
                ans += G(i,j+st[i]);
                sum = (sum+fr[i][j])%p;
            }
            if(L==1) continue;
            if(L+st[i]>=i){  // 同样利用对称性
                for(int j=1;;++j){
                    px = L-1+st[i]-st[i-j];
                    if(px>=fr[i-j].size()||px<0) break;
                    sum = (sum+fr[i-j][px])%p;
                }
                fr[i][L-1] = (ll)sum*inv[i+L+st[i]-3]%p+1;
            }else{
                px = i,py = L-1+st[i];
                fr[i][L-1] = fr[py][px-st[py]];
            }
            ans += G(i,L-1+st[i]);
        }
        for(int i=fir;i<=m;++i) fr[i].clear();
        printf("%lld\n",(ans%p+p)%p);
    }
    return 0; 
}