正題

---

題目大意

有一個(gè)$n\times m$的網(wǎng)格，在上面填上$[1,k]$的數(shù)字，定義兩個(gè)長(zhǎng)度為$n$的序列$a_i,b_i$分別表示每一行/每一列的最大值。

求有多少種不同的合法$a,b$對(duì)。

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

---

解題思路

不難發(fā)現(xiàn)合法的$a,b$對(duì)只需要滿足它們的最大值相等。

那么枚舉最大值$i$，答案就是
$$\sum _{i=1}^k(i^n?(i?1{)}^n)(i^m?(i?1{)}^m)$$

看到這個(gè)式子果斷想到這是一個(gè)和$k$有關(guān)的$n+m+1$次多項(xiàng)式，又因?yàn)?span id="ze8trgl8bvbq" class="katex--inline">$k$很大而$n,m$很小直接上插值。

時(shí)間復(fù)雜度：$O(n\log n)$（視$n,m$同級(jí)）

---

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; }

總結(jié)

以上是生活随笔為你收集整理的YbOJ-网格序列【拉格朗日插值】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。