CSP模拟58联测20 牵着她的手

题目大意

考虑所有$n$行$m$列的矩阵，矩阵中每个元素的值都在$1$到$k$之间。对于这样的矩阵$A$，按照下面规则构造序列$x_1,x_2,\cdots ,x_{n+m}$：

• 对于$1\le i\le n$，$x_i$为$A$中第$i$行的最大值
• 对于$1\le i\le m$，$x_{n+i}$为$A$中第$i$列的最大值

求能构造出多少种不同的序列。

输出答案模$10^9+7$后的值。

有$T$组数据。

$1\le T\le 1000,\sum n,\sum m\le 10^5,k\le 10^9$

时间限制$3000ms$，空间限制$512MB$。

题解

首先，我们可以发现，$x_1$到$x_n$的最大值要等于$x_{n+1}$到$x_{n+m}$的最大值。

然而，当$x_1$到$x_n$的最大值和$x_{n+1}$到$x_{n+m}$的最大值相等时，这个序列一定合法。

为什么呢？我们可以把最大值的列和最大值的行相交的位置填上最大值，在这一行的其他位置填上其他数来满足列的要求，在这一列的其他位置填上其他数来满足行的要求，并在其他位置填$1$，即可构造出这个序列。

我们可以枚举最大值来计算答案。

$$ans=\sum _{i=1}^k[i^n-(i-1{)}^n]\times [i^m-(i-1{)}^m]$$

这样做是$O(k\log n)$的，我们考虑优化。

我们可以发现，这是一个关于$k$的$n+m$次多项式，那么整个和式就是一个关于$k$的$n+m+1$次多项式。那么，我们计算出前$n+m+2$项之后，用拉格朗日差值法，就可以优化到$O(n^2)$。

因为差值的时候，$i$的取值是连续的，那么差值的式子为

$$f(x)=\sum _{i=1}^N{y}_i\prod _{j=1,j\ne i}^N\frac{x-j}{i-j}=\sum _{i=1}^N{y}_i\times \frac{\prod _{j=1,j\ne i}^{N}x-j}{\prod _{j=1,j\ne i}^{N}i-j}$$

其中$N=n+m+2$。

对后面的式子，我们考虑如何快速来求。

$$\prod _{j=1,j\ne i}^{N}i-j=(\prod _{j=1}^{i-1}i-j)\times (\prod _{j=i+1}^{N}i-j)=(i-1)!\times (N-i)!\times (-1{)}^{N-i}$$

预处理出每个数的阶乘，这部分就可以$O(1)$求出。

当$x>N$时，$\prod _{j=1,j\ne i}^{N}x-j=(\prod _{j=1}^{N}x-j)\times \frac{1}{x-i}$，其中$\prod _{j=1}^{N}x-j$可以在插值之前$O(n)$求出，$\frac{1}{x-i}$可以用逆元来求。

当$x\le N$时，我们一开始已经计算出来了，这部分可以直接输出。

那么，分子就可以$O(\log n)$求出。

这样，我们就可以把拉格朗日插值的时间复杂度降到$O(n\log n)$。

总时间复杂度为$O(\sum n\log n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const long long mod=1e9+7;
int T;
long long n,m,k;
long long ans,x[N+5],y[N+5],jc[N+5];
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void init(){jc[0]=1;for(int i=1;i<=N;i++) jc[i]=jc[i-1]*i%mod;
}
long long gt(long long vx){long long re=0,wt=1;for(int i=1;i<=n+m+2;i++){wt=wt*((vx-x[i]+mod)%mod)%mod;}for(int i=1;i<=n+m+2;i++){long long p,q;p=y[i]*wt%mod*mi((vx-x[i]+mod)%mod,mod-2)%mod;if(n+m+2-i&1) q=(mod-jc[i-1]*jc[n+m+2-i]%mod)%mod;else q=jc[i-1]*jc[n+m+2-i]%mod;re=(re+p*mi(q,mod-2)%mod)%mod;}return re;
}
int main()
{init();scanf("%d",&T);while(T--){scanf("%lld%lld%lld",&n,&m,&k);ans=0;for(int i=1;i<=n+m+2;i++){x[i]=i;y[i]=(y[i-1]+(mi(i,n)-mi(i-1,n))*(mi(i,m)-mi(i-1,m))%mod+mod)%mod;}if(k<=n+m+2) printf("%lld\n",y[k]);else printf("%lld\n",gt(k));}return 0;
}