【题解】洛谷P1350 车的放置（矩阵公式推导）

洛谷P1350：https://www.luogu.org/problemnew/show/P1350

思路

把矩阵分为上下两块N与M

放在N中的有i辆车 则放在M中有k-i辆车

N的长为a 宽为b

M的长为a+c 宽为d

在每个矩阵中的放置种类公式如下：

A(长度,车辆)*C(宽度,车辆)

给出证明：

比如对于N来说

可以在a列中找出i列放入车所以是A(a,i)

而且有C(b,i)种选择列的方式

由此可得枚举放在N和M的车有几辆并计算两个矩阵种类之积即可

PS:对于矩阵M来说A为A(a+c-i,k-i) 而不是A(a+c,k-i) 因为每排只能放1辆而且有i辆已经放在N中了

代码

#include<iostream>

using namespace std;

#define mod 100003

#define ll long long

#define maxn 2005

ll a,b,c,d,k,ans;

ll fc[maxn][maxn];

ll A(ll n,ll m)

{

    ll sum=;

    for(ll i=;i<=m;i++)

    sum=sum%mod*(n-m+i)%mod;//排列递推

    return sum;

}

ll C(int n,int m)

{

    if(fc[n][m]) return fc[n][m];//记忆化

    if(m>n) return ;//如果放不下了

    if(n==m||m==) return fc[n][m]=;

    fc[n][m]=(C(n-,m-)%mod+C(n-,m)%mod)%mod;//组合递推

    return fc[n][m];

}

int main()

{

    cin>>a>>b>>c>>d>>k;

    for(ll i=;i<=k;i++)//枚举i辆车放在N中 k-i辆车放在M中

        ans=(ans+A(a,i)%mod*C(b,i)%mod*A(a+c-i,k-i)%mod*C(d,k-i)%mod)%mod;

    cout<<ans;

}

巴特西

【题解】洛谷P1350 车的放置（矩阵公式推导）

思路

代码

最新文章

热门文章