题解：CF295C Greg and Friends

· · 题解

题目传送门：CF295C。

思路

本文中令船最多的载重（即题目中的 k）设为 m，50 千克的人的个数为 x，100 千克的人的个数为 y。

我们考虑最劣情况，发现就是一个人把另一个拉过去后又自己回来然后又拉下一个人，以此类推，因此最多又 2n 个往返次数，即 4n 个过程（指船从一边到另一边的过程，后文均延用此定义），所以当过程数大于 4n 时，就说明无解。

我们设 f_{i,j,k} 表示现在是第 i 个过程，这个过程结束后，还有 j 个 50 千克，k 个 100 千克的人没有过河的方案数，很明显一开始没有人渡河，所以 f_{0,x,y}=1，接下来我们考虑转移。

  1. 如果 i 是奇数，说明现在是到达对岸的过程，我们枚举这一次渡河的 50 千克的人数 a 与 100 千克的人数 b，则 f_{i,j,k} 将要增加的贡献为 f_{i-1,j+a,k+b}\times C_{j+a}^a\times C_{k+b}^b。
  2. 如果 i 是偶数，说明现在是从对岸回来的过程，我们再次枚举这一次渡河的 50 千克的人数 a 与 100 千克的人数 b，则 f_{i,j,k} 将要增加的贡献为 f_{i-1,j-a,k-b}\times C_{x-j+a}^a\times C_{y-k+b}^b。

每当进行 1 步骤的转移时，我们判断 f_{i,0,0} 是否不为 0，如果不为 0，则输出答案，最后如果 i>4n 说明无解。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=60,mod=1e9+7;
int f[4*N][N][N],C[N][N],x,y,n,m;
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
main(){
    n=read(),m=read();
    for (int i=1;i<=n;i++){
        int xx=read();
        if (xx==50) x++;
        else y++;
    }
    C[0][0]=1;
    for (int i=1;i<=n;i++){
        C[i][0]=1;
        for (int j=1;j<=n;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    }
    f[0][x][y]=1;
    for (int i=1;i<=4*n;i++)
        for (int j=0;j<=x;j++)
            for (int k=0;k<=min(y,n-j);k++){
                if (i&1){
                    for (int a=0;a<=x-j;a++)
                        for (int b=0;b<=y-k;b++)
                            if (!(a==0&&b==0)&&50*a+100*b<=m)
                                f[i][j][k]=(f[i][j][k]+f[i-1][j+a][k+b]*C[j+a][a]%mod*C[k+b][b]%mod)%mod;
                    if (f[i][0][0]){
                        cout <<i<<endl<<f[i][0][0];
                        return 0;
                    }
                }
                else{
                    for (int a=0;a<=j;a++)
                        for (int b=0;b<=k;b++)
                            if (!(a==0&&b==0)&&50*a+100*b<=m)
                                f[i][j][k]=(f[i][j][k]+f[i-1][j-a][k-b]*C[x-j+a][a]%mod*C[y-k+b][b]%mod)%mod;
                }
            }
    puts("-1\n0");
    return 0;
}