Submission #498648

#	Time	Username	Problem	Language	Result	Execution time	Memory
498648		model_code	NoM (RMI21_nom)	C++17	100 / 100	78 ms	328 KiB

Main

// nom_100_panaete.cpp
#include <bits/stdc++.h>

using namespace std;
const int MOD = 1000000007;
const int N = 2005;
int n,d,L,R,X,newL,newR,puse,ramase,K,F[N],I[N],comb(int,int),cat,rest,A[N],B[N],*a,*b;
inline int suma(int a,int b)
{
    a=(a+b)%MOD;
    return a;
}
inline int prod(int a,int b)
{
    a=1LL*a*b%MOD;
    return a;
}
inline int comb(int n,int k)
{
    return prod(F[n],prod(I[k],I[n-k]));
}
void init(),procesare();

int main()
{
    init();
    while(ramase)
    {
        K=cat;
        if(rest)
        {
            K++;
            rest--;
        }
        newL=3*n;
        newR=-1;
        for(X=L; X<=R; X++)procesare();
        L=newL;
        R=newR;
        puse+=K;
        ramase-=K;
        swap(a,b);
    }
    int Sol=a[n];
    for(int i=1; i<=n; i++)Sol=prod(2,Sol);
    cout<<Sol<<'\n';
    return 0;
}
void init()
{
    a=A;
    a[0]=1;
    b=B;
    cin>>n>>d;
    cat=2*n/d;   /// dimensiunea standard a unei grupe
    rest=2*n%d;  /// numarul de grupe mai mari cu 1 fata de dimensiunea standard
    ramase=2*n;  /// numarul de valori pe care le mai am de pus
    F[0]=1;      /// initializare calcul factoriale
    for(int i=1; i<=2000; i++)F[i]=prod(i,F[i-1]); /// calcul factoriale
    int x=F[2000],e=MOD-2,r=1;
    for(; e; e>>=1,x=prod(x,x))r=(e&1)?prod(r,x):r; /// calcul (2000!)^(-1)
    I[2000]=r; /// initializare calcul inverse factoriale
    for(int i=2000; i>=1; i--)I[i-1]=prod(i,I[i]); /// calcul inverse factoriale [(i-1)!]^(-1) = i * (i!)^(-1)
}
void procesare()
{
    /// se completeaza o noua grupa de dimensiune K
    /// puse = numarul de valori deja folosite in grupele anterioare
    /// U2 = X = numarul de valori folosite de doua ori[tip 2]
    /// U1 = Y = numarul de valori folosite o data[tip 1]
    /// U0 = Z = numarul de valori nefolosite inca[tip 0]
    int Y=puse-2*X,Z=n-X-Y;
    int maxY=min(Y,K),maxZ=min(Z,K);
    int minY=K-maxZ;
    newL=min(newL,X+minY);
    newR=max(newR,X+maxY);
    for(int UY=minY,UZ=K-minY; UY<=maxY; UY++,UZ--)
        b[X+UY]=suma(b[X+UY],prod(F[K],prod(a[X],prod(comb(Y,UY),comb(Z,UZ)))));
    a[X]=0;
}

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