2020年牛客多校第5回C題
4352 ワード
2次元配列c c c cを設定し、0にできない.
c[0][j]=c[1][j]c[0][j]=c[1][j]c[0][j]=c[1][j]
更に1つの配列A A A Aと配列B B Bを取って、0にすることができます
a[i]=A[i]+c[0][i]a[i]=A[i]+c[0][i]a[i]=A[i]+c[0][i]
b [ i ] = B [ i ] + c [ 1 ] [ i ] b[i]=B[i]+c[1][i] b[i]=B[i]+c[1][i]
与えられたN=4,M=4,k=2 N=4,M=4,k=2 N=4,M=4,k=2
c c c配列にc[0][1]=c[0][2]=c[1]=c[1]=c[1]=c[2]=1 c[0][1]=c[0][2]=c[1][1]=c[1][2]=1 c[0][1]=c[0][2]=c[1][1]=c[0][2]=c[1][1]=c[1][2]=1;
では、あなたのA A A配列はA[1]=2、A[2]=0 A[1]=2、A[2]=0 A[1]=2、A[2]=0
B B B B配列は、B[1]=0、B[3]=2 B[1]=0、B[3]=2 B[1]=0、B[3]=2とすることができる.
このようにして,a=a=a={3 3 3,1}b={1 1,3 3 3}となるa b ab配列を構築した.
c c c配列が決定され、Σi=1 kc[0][i]=rsumlimits_{i=1}^{k}c[0][i]=r i=1Σk c[0][i]=rであると、A,B A,B A,B A,B配列の組合せ数*(A,B配列中の元素はいずれも0**であることに注意)C(N−r+k−1,k−1)∗C(M−r+k−1,k−1)C(N−r+k−k−1,k−1)C(N−r+k−1,k−1)*C(M−r+k−1,k−1)C(N−r+k−k−1,k−1)C(N−r+k−k−1,k−1)C(N−r(N−r+k−k−1)C(M−r+k−1,k−1),C(n,m)C(n,m)C(n,m)は、n n n n個がm m m個を取る組合せ数(s u m(c[0])+s u m(A)=Nかつs u m(c[1])+s u m(B)=M sum(c[0])+sum(A)=Nかつsum(c[1])+sum(B)=M sum(c[1])+sum(B)=M sum(c[0])+sum(c[0])+sum(A)=Nかつsum(c[1]+sum(c[1])+sum(B)=Mこそ合法的である)を表すので、このようなc配列カウント(すなわち上の組合せ数積)を積)するc配列すべてのi=1に相当する...k i=1...k i=1...kのいずれもm i n(a i,b i)>=c[0][i]min(a_i,b_i)>=c[0][i]min(ai,bi)>=c[0][i]のab配列が1回カウントされている
下を見てください
a,b a,b a,b数列を決定するMIN MIN数列を考慮すると、MIN[i]=m i n(a[i],b[i])MIN[i]=min(a[i],b[i])MIN[i]=min(a[i],b[i])MIN[i]=min(a[i],b[i])
明らかにこのa,b a,b a,b数列の寄与は∏i＝1＝kMIN［i］prodlimits＿である.{i=1}^{=k}MIN[i]i=1∏=k MIN[i]
**次に、決定されたM I N MIN MIN配列M I N x MIN_について説明する.x MINx、そしてa,b a,b a,bも確定**
乗算をカウント寄与に分解しようとした.
それは明らかに特定のM I N x MIN_に対してx MINx配列、カウントすべき回数は∏i=1 kMINx[i]prodlimits_{i=1}^{k}MIN_x[i] i=1∏kMINx[i].
では、このカウントを特定のc c c配列とA,B A,B A,Bの組み合わせに分けて行けばいいです.
どのようなc c c配列とA,B A,B A,B配列からなるa,b a,b配列がこのM I N x MIN_を形成するか考えてみましょう.x MINx配列(注意、a、b配列も特定です)ですね.
任意のi=1に対して明らかに..k i=1..k i=1..kはいずれもc[0][i]<=MINX[i]c[0][i]<=MIN_X[i] c[0][i]<=MINX[i]
このようなc c c配列とA,B A,B A,Bの組み合わせによって形成されるa,b a,b a,b配列のM I N MIN配列には必ずM I N x MIN_x MINx配列は同じです.一つしかない
このようなc c c c配列はいくつありますか?
明らかに∏i=1 kMINx[i]prodlimits_{i=1}^{k}MIN_x[i]i=1∏k MINx[i]個、c[0]c[0]c[0]配列の各ビット数がMINX MIN_以下である限りX MINXでいいです.
すなわち,問題は完全にカウント問題に変換され,すなわち,すべてのc c c配列から生じるA,B A,B配列の種数の和に変換される.
同じc c c配列に対応するA,B A,B A,B配列の個数は同じであり,同じとr r rのような種数にはC(r−1,k−1)C(r−1,k−1)C(r−1,k−1)C(r−1,k−1)挿板法があることが容易に分かる.
N=3,M=3,K=2 N=3,M=3,K=2 N=3,M=3,K=2を例にとると
c[0]=c[0]=c[0]={1 1 1,1}の場合、対応するA,B A,B A,B配列の組み合わせは、
A 1 = A_1= A1={ 0 0 0, 1 1 1}, B 1 B_1 B 1={0,1,0,1,0,1}ではa 1=1,2 a_1=1,2 a1=1,2, b 1 = 1 , 2 b_1=1,2 b1=1,2, M I N 1 = 1 , 2 MIN_1=1,2 MIN1=1,2
A 2 = 0 , 1 , B 2 = 1 , 0 A_2=0,1,B_2=1,0 A 2=0,1,B 2=1,0ならa 2=1,2 a_2=1,2 a2=1,2, b 2 = 2 , 1 b_2=2,1 b2=2,1, M I N 2 = 1 , 1 MIN_2=1,1 MIN2=1,1
次はa 3=2,1 a_3=2,1 a3=2,1, b 3 = 1 , 2 b_3=1,2 b3=1,2, M I N 3 = 1 , 1 MIN_3=1,1 MIN3=1,1
a 4 = 2 , 1 a_4=2,1 a4=2,1, b 4 = 2 , 1 b_4=2,1 b4=2,1, M I N = 2 , 1 MIN=2,1 MIN=2,1
これでこのc c cをカウントすると、以上の4種類のa,b a,b a,bを1回カウントすることになります
c c cの他の配列を手動でシミュレートして上の説明に合わせるとすぐに解けます.
やはり分からないのは私が説明できないことです
コード:
c[0][j]=c[1][j]c[0][j]=c[1][j]c[0][j]=c[1][j]
更に1つの配列A A A Aと配列B B Bを取って、0にすることができます
a[i]=A[i]+c[0][i]a[i]=A[i]+c[0][i]a[i]=A[i]+c[0][i]
b [ i ] = B [ i ] + c [ 1 ] [ i ] b[i]=B[i]+c[1][i] b[i]=B[i]+c[1][i]
与えられたN=4,M=4,k=2 N=4,M=4,k=2 N=4,M=4,k=2
c c c配列にc[0][1]=c[0][2]=c[1]=c[1]=c[1]=c[2]=1 c[0][1]=c[0][2]=c[1][1]=c[1][2]=1 c[0][1]=c[0][2]=c[1][1]=c[0][2]=c[1][1]=c[1][2]=1;
では、あなたのA A A配列はA[1]=2、A[2]=0 A[1]=2、A[2]=0 A[1]=2、A[2]=0
B B B B配列は、B[1]=0、B[3]=2 B[1]=0、B[3]=2 B[1]=0、B[3]=2とすることができる.
このようにして,a=a=a={3 3 3,1}b={1 1,3 3 3}となるa b ab配列を構築した.
c c c配列が決定され、Σi=1 kc[0][i]=rsumlimits_{i=1}^{k}c[0][i]=r i=1Σk c[0][i]=rであると、A,B A,B A,B A,B配列の組合せ数*(A,B配列中の元素はいずれも0**であることに注意)C(N−r+k−1,k−1)∗C(M−r+k−1,k−1)C(N−r+k−k−1,k−1)C(N−r+k−1,k−1)*C(M−r+k−1,k−1)C(N−r+k−k−1,k−1)C(N−r+k−k−1,k−1)C(N−r(N−r+k−k−1)C(M−r+k−1,k−1),C(n,m)C(n,m)C(n,m)は、n n n n個がm m m個を取る組合せ数(s u m(c[0])+s u m(A)=Nかつs u m(c[1])+s u m(B)=M sum(c[0])+sum(A)=Nかつsum(c[1])+sum(B)=M sum(c[1])+sum(B)=M sum(c[0])+sum(c[0])+sum(A)=Nかつsum(c[1]+sum(c[1])+sum(B)=Mこそ合法的である)を表すので、このようなc配列カウント(すなわち上の組合せ数積)を積)するc配列すべてのi=1に相当する...k i=1...k i=1...kのいずれもm i n(a i,b i)>=c[0][i]min(a_i,b_i)>=c[0][i]min(ai,bi)>=c[0][i]のab配列が1回カウントされている
下を見てください
a,b a,b a,b数列を決定するMIN MIN数列を考慮すると、MIN[i]=m i n(a[i],b[i])MIN[i]=min(a[i],b[i])MIN[i]=min(a[i],b[i])MIN[i]=min(a[i],b[i])
明らかにこのa,b a,b a,b数列の寄与は∏i＝1＝kMIN［i］prodlimits＿である.{i=1}^{=k}MIN[i]i=1∏=k MIN[i]
**次に、決定されたM I N MIN MIN配列M I N x MIN_について説明する.x MINx、そしてa,b a,b a,bも確定**
乗算をカウント寄与に分解しようとした.
それは明らかに特定のM I N x MIN_に対してx MINx配列、カウントすべき回数は∏i=1 kMINx[i]prodlimits_{i=1}^{k}MIN_x[i] i=1∏kMINx[i].
では、このカウントを特定のc c c配列とA,B A,B A,Bの組み合わせに分けて行けばいいです.
どのようなc c c配列とA,B A,B A,B配列からなるa,b a,b配列がこのM I N x MIN_を形成するか考えてみましょう.x MINx配列(注意、a、b配列も特定です)ですね.
任意のi=1に対して明らかに..k i=1..k i=1..kはいずれもc[0][i]<=MINX[i]c[0][i]<=MIN_X[i] c[0][i]<=MINX[i]
このようなc c c配列とA,B A,B A,Bの組み合わせによって形成されるa,b a,b a,b配列のM I N MIN配列には必ずM I N x MIN_x MINx配列は同じです.一つしかない
このようなc c c c配列はいくつありますか?
明らかに∏i=1 kMINx[i]prodlimits_{i=1}^{k}MIN_x[i]i=1∏k MINx[i]個、c[0]c[0]c[0]配列の各ビット数がMINX MIN_以下である限りX MINXでいいです.
すなわち,問題は完全にカウント問題に変換され,すなわち,すべてのc c c配列から生じるA,B A,B配列の種数の和に変換される.
同じc c c配列に対応するA,B A,B A,B配列の個数は同じであり,同じとr r rのような種数にはC(r−1,k−1)C(r−1,k−1)C(r−1,k−1)C(r−1,k−1)挿板法があることが容易に分かる.
N=3,M=3,K=2 N=3,M=3,K=2 N=3,M=3,K=2を例にとると
c[0]=c[0]=c[0]={1 1 1,1}の場合、対応するA,B A,B A,B配列の組み合わせは、
A 1 = A_1= A1={ 0 0 0, 1 1 1}, B 1 B_1 B 1={0,1,0,1,0,1}ではa 1=1,2 a_1=1,2 a1=1,2, b 1 = 1 , 2 b_1=1,2 b1=1,2, M I N 1 = 1 , 2 MIN_1=1,2 MIN1=1,2
A 2 = 0 , 1 , B 2 = 1 , 0 A_2=0,1,B_2=1,0 A 2=0,1,B 2=1,0ならa 2=1,2 a_2=1,2 a2=1,2, b 2 = 2 , 1 b_2=2,1 b2=2,1, M I N 2 = 1 , 1 MIN_2=1,1 MIN2=1,1
次はa 3=2,1 a_3=2,1 a3=2,1, b 3 = 1 , 2 b_3=1,2 b3=1,2, M I N 3 = 1 , 1 MIN_3=1,1 MIN3=1,1
a 4 = 2 , 1 a_4=2,1 a4=2,1, b 4 = 2 , 1 b_4=2,1 b4=2,1, M I N = 2 , 1 MIN=2,1 MIN=2,1
これでこのc c cをカウントすると、以上の4種類のa,b a,b a,bを1回カウントすることになります
c c cの他の配列を手動でシミュレートして上の説明に合わせるとすぐに解けます.
やはり分からないのは私が説明できないことです
コード:
#include
#define ll long long
#define endl '
'
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int MX=1e6+7;
const int mod=998244353;
const double pi=3.1415926535897932384;
double isp=1e-13;
using namespace std;
ll qpow(ll a,ll b,ll MOD=mod){for(ll ans=1;;a=a*a%MOD,b>>=1){if(b&1)ans=ans*a%MOD;if(!b)return ans;}}
ll inv(ll a,ll MOD=mod){return qpow(a,MOD-2,MOD);}// MOD
ll exgcd(ll a,ll b,ll &x,ll &y){if(b==0){x=1,y=0;return a;}ll ret=exgcd(b,a%b,y,x);y-=a/b*x;return ret;}
ll getInv(int a,int mod){ll x,y;ll d=exgcd(a,mod,x,y);return d==1?(x%mod+mod)%mod:-1;}// a mod ， -1， MOD
ll p[MX],np[MX],in[MX];
ll C(ll n,ll m)
{
return p[n]*np[m]%mod*np[n-m]%mod;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
p[0]=np[0]=in[1]=1;
for(int i=1;i>t;
while(t--)
{
int n,m,k;
cin>>n>>m>>k;
ll ans=0;
for(int i=k;i<=min(n,m);i++)
{
ans=(ans+1ll*C(i-1,k-1)*C(n-i+k-1,k-1)%mod*C(m-i+k-1,k-1))%mod;
}
cout<