记录编号	584638	评测结果	MMMMMMMMMMMMMMMM
题目名称	魔药	最终得分	0
用户昵称	元始天尊	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-14 14:26:38	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
int f[10010][10010];
unsigned long long d=1e9+7;
string s;
unsigned long long A(int m,int n)
{
    unsigned long long ans=1;
    for(int i=m-n+1;i<=m;i++)
    {
        ans*=i%d;
    }
    return ans%d;
}
unsigned long long C(int m,int n)
{
    return A(m,n)/A(n,n);
}
unsigned long long F(int i,int j,int m)
{
    if(f[i][j]) return f[i][j];
    if(f[i][i-j+1]) return f[i][j]=f[i][i-j+1];
    if(j==1||j==i) return f[i][j]=2;
    if(m>(i+1)/2&&j<(i+1)/2) 
    {
        return f[i][j]=F(i,i-j+1,m);      
    }
    if(m<(i+1)/2&&j>(i+1)/2)
    {
        return f[i][j]=F(i,i-j+1,m);
    }
    return f[i][j]=(F(i-1,j-1,m)%d+F(i-1,j,m)%d)%d;
}
int main()
{
    freopen("sleeping.in","r",stdin);
    freopen("sleeping.out","w",stdout);
    unsigned long long m,n,ans1=0,ans2=0,len,sum;
    cin>>n>>m>>s;
    len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='1') sum++;
    }
    if(n>m)
    {
        ans1=(F(n,m,m)/(n-1))%d;
    }
    if(n==m)
    {
        if(n%2==0) 
        {
            if(sum!=n/2)
            {
                ans1=0;
            }
            else ans1=1;
        }
        else
        {
            if(sum==n/2||sum==n/2+1)
            {
                ans1=1;
            }
            else ans1=0;
        }
    }
    if(m>n) ans1=0; 
    ans2=C(n,sum)-ans1;
    cout<<ans1<<" "<<ans2<<endl;
        return 0;
}