Yboj mesh sequence [Lagrange interpolation]

On the subject

---

The main idea of the topic

There is one $n\times m$ The grid of , Fill it in $[1,k]$ The number of , Define two lengths as $n$ Sequence $a_i,b_i$ Represent each line separately / The maximum value of each column .

Ask how many different legal $a,b$ Yes .

$1\le n,m\le 10^6,1\le k\le 10^9$

---

Their thinking

It is not difficult to find legal $a,b$ It is only necessary to satisfy that their maximum values are equal .

Then enumerate the maximum values $i$, The answer is
$$\sum _{i=1}^k(i^n-(i-1{)}^n)(i^m-(i-1{)}^m)$$

Seeing this formula, I decided that it was a sum of $k$ Relevant $n+m+1$ Sub polynomial , Again because $k$ It's big and $n,m$ Very small direct interpolation .

Time complexity ：$O(n\log n)$（ Depending on the $n,m$ At the same level ）

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=3e6+10,P=998244353;
ll n,m,k,pwn[N],pwm[N],f[N],inv[N],pre[N],suf[N],ans;
ll power(ll x,ll b){
    
	ll ans=1;
	while(b){
    
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
signed main()
{
    
	freopen("grid.in","r",stdin);
	freopen("grid.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&k);
	ll L=n+m+10;
	for(ll i=1;i<=L;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 i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;
	for(ll i=1;i<N;i++)inv[i]=inv[i-1]*inv[i]%P;
	pre[0]=k;suf[L]=k-L;suf[L+1]=1;
	for(ll i=1;i<=L;i++)pre[i]=pre[i-1]*(k-i)%P;
	for(ll i=L-1;i>=0;i--)suf[i]=suf[i+1]*(k-i)%P;
	for(ll i=0;i<=L;i++){
    
		ll w=f[i]*(i?pre[i-1]:1)%P*suf[i+1]%P;
		w=w*inv[i]%P*inv[L-i]%P*(((L-i)&1)?-1:1);
		ans=(ans+w)%P;
	}
	printf("%lld\n",(ans+P)%P);
	return 0;
}