网站栏目设计怎么写,用vps做网站,怎么帮公司做网站建设,网站域名备案资料题目大意
考虑所有 n n n行 m m m列的矩阵#xff0c;矩阵中每个元素的值都在 1 1 1到 k k k之间。对于这样的矩阵 A A A#xff0c;按照下面规则构造序列 x 1 , x 2 , ⋯ , x n m x_1,x_2,\cdots,x_{nm} x1,x2,⋯,xnm#xff1a;
对于 1 ≤ i ≤ n 1\leq i\leq n …题目大意
考虑所有 n n n行 m m m列的矩阵矩阵中每个元素的值都在 1 1 1到 k k k之间。对于这样的矩阵 A A A按照下面规则构造序列 x 1 , x 2 , ⋯ , x n m x_1,x_2,\cdots,x_{nm} x1,x2,⋯,xnm
对于 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n x i x_i xi为 A A A中第 i i i行的最大值对于 1 ≤ i ≤ m 1\leq i\leq m 1≤i≤m x n i x_{ni} xni为 A A A中第 i i i列的最大值
求能构造出多少种不同的序列。
输出答案模 1 0 9 7 10^97 1097后的值。
有 T T T组数据。 1 ≤ T ≤ 1000 , ∑ n , ∑ m ≤ 1 0 5 , k ≤ 1 0 9 1\leq T\leq 1000,\sum n,\sum m\leq 10^5,k\leq 10^9 1≤T≤1000,∑n,∑m≤105,k≤109
时间限制 3000 m s 3000ms 3000ms空间限制 512 M B 512MB 512MB。 题解
首先我们可以发现 x 1 x_1 x1到 x n x_n xn的最大值要等于 x n 1 x_{n1} xn1到 x n m x_{nm} xnm的最大值。
然而当 x 1 x_1 x1到 x n x_n xn的最大值和 x n 1 x_{n1} xn1到 x n m x_{nm} xnm的最大值相等时这个序列一定合法。
为什么呢我们可以把最大值的列和最大值的行相交的位置填上最大值在这一行的其他位置填上其他数来满足列的要求在这一列的其他位置填上其他数来满足行的要求并在其他位置填 1 1 1即可构造出这个序列。
我们可以枚举最大值来计算答案。 a n s ∑ i 1 k [ i n − ( i − 1 ) n ] × [ i m − ( i − 1 ) m ] ans\sum\limits_{i1}^k[i^n-(i-1)^n]\times [i^m-(i-1)^m] ansi1∑k[in−(i−1)n]×[im−(i−1)m]
这样做是 O ( k log n ) O(k\log n) O(klogn)的我们考虑优化。
我们可以发现这是一个关于 k k k的 n m nm nm次多项式那么整个和式就是一个关于 k k k的 n m 1 nm1 nm1次多项式。那么我们计算出前 n m 2 nm2 nm2项之后用拉格朗日差值法就可以优化到 O ( n 2 ) O(n^2) O(n2)。
因为差值的时候 i i i的取值是连续的那么差值的式子为 f ( x ) ∑ i 1 N y i ∏ j 1 , j ≠ i N x − j i − j ∑ i 1 N y i × ∏ j 1 , j ≠ i N x − j ∏ j 1 , j ≠ i N i − j f(x)\sum\limits_{i1}^Ny_i\prod\limits_{j1,j\neq i}^N\dfrac{x-j}{i-j}\sum\limits_{i1}^Ny_i\times \dfrac{\prod\limits_{j1,j\neq i}^Nx-j}{\prod\limits_{j1,j\neq i}^Ni-j} f(x)i1∑Nyij1,ji∏Ni−jx−ji1∑Nyi×j1,ji∏Ni−jj1,ji∏Nx−j
其中 N n m 2 Nnm2 Nnm2。
对后面的式子我们考虑如何快速来求。 ∏ j 1 , j ≠ i N i − j ( ∏ j 1 i − 1 i − j ) × ( ∏ j i 1 N i − j ) ( i − 1 ) ! × ( N − i ) ! × ( − 1 ) N − i \prod\limits_{j1,j\neq i}^Ni-j(\prod_{j1}^{i-1}i-j)\times (\prod\limits_{ji1}^Ni-j)(i-1)!\times (N-i)!\times (-1)^{N-i} j1,ji∏Ni−j(j1∏i−1i−j)×(ji1∏Ni−j)(i−1)!×(N−i)!×(−1)N−i
预处理出每个数的阶乘这部分就可以 O ( 1 ) O(1) O(1)求出。
当 x N xN xN时 ∏ j 1 , j ≠ i N x − j ( ∏ j 1 N x − j ) × 1 x − i \prod\limits_{j1,j\neq i}^Nx-j(\prod\limits_{j1}^Nx-j)\times \dfrac{1}{x-i} j1,ji∏Nx−j(j1∏Nx−j)×x−i1其中 ∏ j 1 N x − j \prod\limits_{j1}^Nx-j j1∏Nx−j可以在插值之前 O ( n ) O(n) O(n)求出 1 x − i \dfrac{1}{x-i} x−i1可以用逆元来求。
当 x ≤ N x\leq N x≤N时我们一开始已经计算出来了这部分可以直接输出。
那么分子就可以 O ( log n ) O(\log n) O(logn)求出。
这样我们就可以把拉格朗日插值的时间复杂度降到 O ( n log n ) O(n\log n) O(nlogn)。
总时间复杂度为 O ( ∑ n log n ) O(\sum n\log n) O(∑nlogn)。
code
#includebits/stdc.h
using namespace std;
const int N200005;
const long long mod1e97;
int T;
long long n,m,k;
long long ans,x[N5],y[N5],jc[N5];
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
void init(){jc[0]1;for(int i1;iN;i) jc[i]jc[i-1]*i%mod;
}
long long gt(long long vx){long long re0,wt1;for(int i1;inm2;i){wtwt*((vx-x[i]mod)%mod)%mod;}for(int i1;inm2;i){long long p,q;py[i]*wt%mod*mi((vx-x[i]mod)%mod,mod-2)%mod;if(nm2-i1) q(mod-jc[i-1]*jc[nm2-i]%mod)%mod;else qjc[i-1]*jc[nm2-i]%mod;re(rep*mi(q,mod-2)%mod)%mod;}return re;
}
int main()
{init();scanf(%d,T);while(T--){scanf(%lld%lld%lld,n,m,k);ans0;for(int i1;inm2;i){x[i]i;y[i](y[i-1](mi(i,n)-mi(i-1,n))*(mi(i,m)-mi(i-1,m))%modmod)%mod;}if(knm2) printf(%lld\n,y[k]);else printf(%lld\n,gt(k));}return 0;
}
