免费公司网站制作,如何成立网站,道滘网站仿做,深圳好的网站制作哪家快正题 题目大意
有一个nmn\times mnm的网格#xff0c;在上面填上[1,k][1,k][1,k]的数字#xff0c;定义两个长度为nnn的序列ai,bia_i,b_iai,bi分别表示每一行/每一列的最大值。
求有多少种不同的合法a,ba,ba,b对。 1≤n,m≤106,1≤k≤1091\leq n,m\leq 10^6,1\leq k\le…正题 题目大意
有一个n×mn\times mn×m的网格在上面填上[1,k][1,k][1,k]的数字定义两个长度为nnn的序列ai,bia_i,b_iai,bi分别表示每一行/每一列的最大值。
求有多少种不同的合法a,ba,ba,b对。
1≤n,m≤106,1≤k≤1091\leq n,m\leq 10^6,1\leq k\leq 10^91≤n,m≤106,1≤k≤109 解题思路
不难发现合法的a,ba,ba,b对只需要满足它们的最大值相等。
那么枚举最大值iii答案就是 ∑i1k(in−(i−1)n)(im−(i−1)m)\sum_{i1}^k(i^n-(i-1)^n)(i^m-(i-1)^m)i1∑k(in−(i−1)n)(im−(i−1)m)
看到这个式子果断想到这是一个和kkk有关的nm1nm1nm1次多项式又因为kkk很大而n,mn,mn,m很小直接上插值。
时间复杂度O(nlogn)O(n\log n)O(nlogn)视n,mn,mn,m同级 code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N3e610,P998244353;
ll n,m,k,pwn[N],pwm[N],f[N],inv[N],pre[N],suf[N],ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{freopen(grid.in,r,stdin);freopen(grid.out,w,stdout);scanf(%lld%lld%lld,n,m,k);ll Lnm10;for(ll i1;iL;i){pwn[i]power(i,n);pwm[i]power(i,m);f[i](f[i-1](pwn[i]-pwn[i-1])*(pwm[i]-pwm[i-1])%P)%P;}inv[0]inv[1]1;for(ll i2;iN;i)inv[i]P-inv[P%i]*(P/i)%P;for(ll i1;iN;i)inv[i]inv[i-1]*inv[i]%P;pre[0]k;suf[L]k-L;suf[L1]1;for(ll i1;iL;i)pre[i]pre[i-1]*(k-i)%P;for(ll iL-1;i0;i--)suf[i]suf[i1]*(k-i)%P;for(ll i0;iL;i){ll wf[i]*(i?pre[i-1]:1)%P*suf[i1]%P;ww*inv[i]%P*inv[L-i]%P*(((L-i)1)?-1:1);ans(answ)%P;}printf(%lld\n,(ansP)%P);return 0;
}
