題目鏈接

https://atcoder.jp/contests/agc035/tasks/agc035_f

題解

B題難度的F題……然而我還是不會
假設第\(i\)行染的長度是\(a_i\), 第\(j\)列是\(b_j\)
考慮什么情況下兩種方案會重復: 若存在\(i,j\)使得\(a_i+1=j\)且\(b_j=i\), 那么令\(a'_i=j-1,b'_j=i+1\)可以得到一樣的結果。
那么我們也就是要計算不存在\(a_i+1=j\)且\(b_j=i\)的序列\(a,b\)個數。
充分性證明: 設存在兩個不同的方案\(a,b\)和\(a',b'\)滿足上面的條件且產生了同樣的結果。設\(j\)為最小的滿足\(b_j\ne b'_j\)的位置。若\(j=1\)則結論顯然成立，若\(j>1\)則有\(a_{b'_j}\ge j\)且\(a'_{b'_j}\le j-1\), 又因為\(a'_{b'_j}\ne j-1\)故\(a'_{b'_j}\le j-2\). 因此\(a'_{b'_j}\lt j-1\lt a_{b'_j}\). 又因為\(b_{j-1}=b'_{j-1}\)，兩矩陣第\(b'_j\)行第\((j-1)\)列不可能相等，矛盾。
然后容斥一下就好: \(\sum^\min(n,m)_{k=0}(-1)^k{m\choose k}{n\choose k}k!(m+1)^{n-k}(n+1)^{m-k}\)
時間復雜度\(O(n+m)\).

代碼

#include<bits/stdc++.h> #define llong long long using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 5e5; const int P = 998244353; llong fact[N+3],finv[N+3]; int n,m;llong quickpow(llong x,llong y) {llong cur = x,ret = 1ll;for(int i=0; y; i++){if(y&(1ll<<i)) {y-=(1ll<<i); ret = ret*cur%P;}cur = cur*cur%P;}return ret; } llong comb(llong x,llong y) {return x<0||y<0||x<y?0ll:fact[x]*finv[y]%P*finv[x-y]%P;}int main() {fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1ll)%P;scanf("%d%d",&n,&m); int lim = min(n,m); llong pwn = quickpow(n+1,m-lim),pwm = quickpow(m+1,n-lim); llong ans = 0ll;for(int i=lim; i>=0; i--){llong cur = comb(m,i)*comb(n,i)%P*fact[i]%P*pwn%P*pwm%P;if(i&1) {ans = (ans-cur+P)%P;} else {ans = (ans+cur)%P;}pwn = pwn*(n+1ll)%P,pwm = pwm*(m+1ll)%P;}printf("%lld\n",ans);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的AtCoder AGC035F Two Histograms (组合计数、容斥原理)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。