CF295C Greg and Friends

zztqwq · 2021-05-14 16:00:28 · 题解

下文中大写 K 表示输入的变量，小写 k 表示枚举的变量。

假设有 tot_5 个 50\mathrm{kg} 的人，tot_1 个 100\mathrm{kg} 的人，f(pos,j,k) 表示这一轮结束后船在 pos 岸（0 为出发岸，1 为对岸），对岸 50\mathrm{kg} 的有 j 个，100\mathrm{kg} 的有 k 个，方案数是多少。那么有两种情况：

I. pos=0：

其中 c_5,c_1 是枚举的变量，满足 0\le c_5\le tot_5-j，0\le c_1\le tot_1-k，0< 50c_5+100c_1\le K。

II. pos=1：

同理，0\le c_5\le j，0\le c_1\le k，0<50c_5+100c_1\le K。

初始值为 f(0,0,0)=1，其余为 0。枚举轮数（一来一回算两轮）i，i 对应的 pos 就是 i\bmod 2。当 f(i\bmod 2,n,n)\not= 0\;(i\bmod 2=1) 时则最小值为 i。如果 i>4n 时还没有答案，那么一定无解。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
const int mod=1e9+7,N=310;
inline int qpow(int a,int n)
{
    int ans=1;
    while(n)
    {
        if(n&1)ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
        n>>=1;
    }
    return ans;
}
int inv[N],p[N];
int binom(int n,int m){return (long long)p[n]*inv[n-m]%mod*inv[m]%mod;}
int f[2][60][60];
int main()
{
    p[0]=inv[0]=1;
    for(int i=1;i<=50;i++)p[i]=(long long)p[i-1]*i%mod,inv[i]=qpow(p[i],mod-2);
    int n=read(),K=read(),tot5=0,tot1=0;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        tot5+=(x==50);
        tot1+=(x==100);
    }
    f[0][0][0]=1;
    for(int i=1;i<=4*n;i++)
    {
        for(int j=0;j<=tot5;j++)
            for(int k=0;k<=tot1;k++)
                f[i&1][j][k]=0;
        for(int j=0;j<=tot5;j++)
        {
            for(int k=0;k<=tot1;k++)
            {
                if(i&1)
                {
                    for(int c5=0;c5<=tot5-j;c5++)
                    {
                        for(int c1=0;c1<=tot1-k;c1++)
                        {
                            if(!c5&&!c1)continue;
                            if(50*c5+100*c1>K) continue;
                            f[1][j+c5][k+c1]+=(long long)binom(tot5-j,c5)*binom(tot1-k,c1)%mod*f[0][j][k]%mod;
                            f[1][j+c5][k+c1]%=mod;
                        }
                    }
                }
                else
                {
                    for(int c5=0;c5<=j;c5++)
                    {
                        for(int c1=0;c1<=k;c1++)
                        {
                            if(!c5&&!c1)continue;
                            if(50*c5+100*c1>K) continue;
                            f[0][j-c5][k-c1]+=(long long)binom(j,c5)*binom(k,c1)%mod*f[1][j][k]%mod;
                            f[0][j-c5][k-c1]%=mod;
                        }
                    }
                }
            }
        }
        if(f[i&1][tot5][tot1])
        {
            printf("%d\n%d",i,f[i&1][tot5][tot1]);
            return 0;
        }
    }
    printf("-1\n0");
    return 0;
}