Submission #646023

#	Time	Username	Problem	Language	Result	Execution time	Memory
646023		Kripton	NoM (RMI21_nom)	C++14	100 / 100	71 ms	368 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
int lgput(int a,int b)
{
    int rez=1;
    while(b)
    {
        if(b%2)
            rez=1LL*rez*a%MOD;
        a=1LL*a*a%MOD;
        b/=2;
    }
    return rez;
}
template <const int MOD> struct numar{
    int x;
    numar(int x=0){
        this->x=x;
    }
    bool operator!=(const numar &other) const{
        return x!=other.x;
    }
    numar& operator=(const numar &other){
        x=other.x;
        return *this;
    }
    numar operator+(const numar &other) const{
        return numar(x+other.x>=MOD?x+other.x-MOD:x+other.x);
    }
    numar operator-(const numar &other) const{
        return numar(x-other.x<0?x-other.x+MOD:x-other.x);
    }
    numar operator*(const numar &other) const{
        return numar(1LL*x*other.x%MOD);
    }
    numar operator/(const numar &other) const{
        return numar(1LL*x*lgput(other.x,MOD-2)%MOD);
    }
    void afis(){
        cout<<x;
    }
};
numar <MOD> fact[4001],invfact[4001];
numar <MOD> dp[2][2001];
int exist[2],exidr[2];
numar <MOD> comb(int a,int b)
{
    if(b>a)
        return 0;
    return fact[a]*invfact[b]*invfact[a-b];
}
numar <MOD> put[4001];
int main()
{
    int n,m,i,j,l;
    cin>>n>>m;
    fact[0]=1;
    put[0]=1;
    for(i=1;i<=2*n;i++)
        put[i]=put[i-1]*2;
    for(i=1;i<=2*n;i++)
        fact[i]=fact[i-1]*i;
    invfact[2*n]=lgput(fact[2*n].x,MOD-2);
    for(i=2*n-1;i>=0;i--)
        invfact[i]=invfact[i+1]*(i+1);
    int cnt2=2*n%m;//2*n/m+1
    int cnt1=m-cnt2;//2*n/m;
    int k=2*n/m;
    int sum=k;
    dp[1][n-k]=comb(n,k)*put[k]*fact[k];
    exist[1]=n-k;
    exidr[1]=n-k;
    for(i=1;i<=cnt1-1;i++)
    {
        for(j=0;j<=n;j++)
            dp[1-(i&1)][j]=0;
        exist[1-(i&1)]=n+1;
        exidr[1-(i&1)]=-1;
        for(j=exist[i&1];j<=exidr[i&1];j++)
            if(dp[i&1][j]!=0)
            {
                int unu=(n-j)*2-sum;
                if(unu<0)
                    break;
                for(l=max(j-k,0);l<=j;l++)
                {
                    if(k-(j-l)>unu)
                        break;
                    dp[1-(i&1)][l]=dp[1-(i&1)][l]+dp[i&1][j]*fact[k]*comb(j,j-l)*put[j-l]*comb(unu,k-(j-l));
                    exist[1-(i&1)]=min(exist[1-(i&1)],l);
                    exidr[1-(i&1)]=max(exidr[1-(i&1)],l);
                }
            }
        sum+=k;
    }
    k++;
    for(;i<=cnt1+cnt2-1;i++)
    {
        for(j=0;j<=n;j++)
            dp[1-(i&1)][j]=0;
        exist[1-(i&1)]=n+1;
        exidr[1-(i&1)]=-1;
        for(j=exist[i&1];j<=exidr[i&1];j++)
            if(dp[i&1][j]!=0)
            {
                int unu=(n-j)*2-sum;
                if(unu<0)
                    break;
                for(l=max(j-k,0);l<=j;l++)
                {
                    if(k-(j-l)>unu)
                        break;
                    dp[1-(i&1)][l]=dp[1-(i&1)][l]+dp[i&1][j]*fact[k]*comb(j,j-l)*put[j-l]*comb(unu,k-(j-l));
                    exist[1-(i&1)]=min(exist[1-(i&1)],l);
                    exidr[1-(i&1)]=max(exidr[1-(i&1)],l);
                }
            }
        sum+=k;
    }
    dp[m%2][0].afis();
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 18 / 18
• Subtask 5: 48 / 48