Submission #597736

#	Time	Username	Problem	Language	Result	Execution time	Memory
597736		Deepesson	NoM (RMI21_nom)	C++17	100 / 100	90 ms	39132 KiB

Main

#include <bits/stdc++.h>
#define MAX 2005


using ll  = long long;
const ll MOD = 1e9+7;

ll binominal[MAX][MAX];
bool exbin[MAX][MAX];
ll dpbin(int a,int b){
    if(!b)return 1;
    if(!a)return 0;
    if(exbin[a][b])return binominal[a][b];
    exbin[a][b]=true;
    return binominal[a][b] = (dpbin(a-1,b)+dpbin(a-1,b-1))%MOD;
}

bool existe[MAX][MAX];
ll tab[MAX][MAX];
ll fat[MAX];
std::vector<int> tamanhos;
ll dp(int nunca_pegou,int pegou_uma_vez,int seq){
    if(seq==tamanhos.size()){
        //std::cout<<"Chegou! "<<nunca_pegou+pegou_uma_vez<<"\n";
        if(nunca_pegou+pegou_uma_vez==0)
            return 1;
        return 0;
    }
    if(existe[nunca_pegou][pegou_uma_vez])return tab[nunca_pegou][pegou_uma_vez];
    existe[nunca_pegou][pegou_uma_vez]=true;
   // std::cout<<nunca_pegou<<" "<<pegou_uma_vez<<" "<<seq<<"\n";
    int tem_q_pegar = tamanhos[seq];
    ll resposta=0;
    for(int i=0;i<=std::min(tem_q_pegar,pegou_uma_vez);++i){
        int necessita = tem_q_pegar-i;
        if(nunca_pegou<necessita)continue;
        ll chance1 = dpbin(nunca_pegou,necessita);
        ll chance2 = dpbin(pegou_uma_vez,i);
        ll total = (chance1*chance2)%MOD;
        ll res = dp(nunca_pegou-necessita,pegou_uma_vez-i+necessita,seq+1);
        ll totalres = (total*res)%MOD;
        ll fatty = fat[tem_q_pegar];
        ll truetotral = (fatty*totalres)%MOD;
        resposta=(resposta+truetotral)%MOD;
    }
    return tab[nunca_pegou][pegou_uma_vez]=resposta;
}

int main()
{
   // std::cout<<dpbin(10,6)<<"\n";
    int N,M;
    std::cin>>N>>M;
    fat[0]=1;
    for(int i=1;i!=MAX;++i)fat[i]=(fat[i-1]*i)%MOD;
    {
        int x = (2*N)/M;
        for(int i=0;i!=M;++i)tamanhos.push_back(x);
        for(int i=0;i!=((2*N)%M);++i)tamanhos[i]++;
        ll xa=0;
        for(int i=0;i!=M;++i){
            xa+=tamanhos[i];
            //std::cout<<tamanhos[i]<<" \n"[i==M-1];
        }
        assert(xa==(2*N));
    }
    ll bonus=1;
    for(int i=0;i!=N;++i)bonus=(bonus*2)%MOD;
    std::cout<<((dp(N,0,0)*bonus)%MOD)<<"\n";
}

Compilation message (stderr)

Main.cpp: In function 'll dp(int, int, int)':
Main.cpp:23:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     if(seq==tamanhos.size()){
      |        ~~~^~~~~~~~~~~~~~~~~

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