제출 #1281652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281652		SSKMF	Tents (JOI18_tents)	C++20	48 / 100	2095 ms	576 KiB

tents

#include <bits/stdc++.h>
using namespace std;

const int mod(1000000007);
int factorial[3001] , invers_factorial[3001];

inline int Exponentiere (int baza , int exponent)
{
    int rezultat = 1;
    for ( ; exponent ; exponent >>= 1 , baza = 1LL * baza * baza % mod)
        { if (exponent & 1) { rezultat = 1LL * rezultat * baza % mod; } }

    return rezultat;
}

inline int Aranjamente (const int total , const int luate)
{
    return total < 0 || luate < 0 || total < luate ? 0 : 1LL * factorial[total] * invers_factorial[total - luate] % mod;
}

inline int Combinari (const int total , const int luate)
{
    return total < 0 || luate < 0 || total < luate ? 0 : 1LL * factorial[total] * invers_factorial[luate] % mod * invers_factorial[total - luate] % mod;
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    factorial[0] = 1;
    for (int valoare = 1 ; valoare <= 3000 ; valoare++)
        { factorial[valoare] = 1LL * factorial[valoare - 1] * valoare % mod; }

    invers_factorial[3000] = Exponentiere(factorial[3000] , mod - 2);
    for (int valoare = 2999 ; valoare >= 0 ; valoare--)
        { invers_factorial[valoare] = 1LL * invers_factorial[valoare + 1] * (valoare + 1) % mod; }

    int linii , coloane;
    cin >> linii >> coloane;

    int modalitati = 1000000006;
    for (int luate_1 = 0 ; luate_1 <= linii ; luate_1++) {
        for (int luate_2 = 0 ; linii - luate_1 - 2 * luate_2 >= 0 && coloane - luate_2 - 2 * luate_1 >= 0 ; luate_2++)
        {
            const int factor = 1LL * Combinari(linii , luate_1) * Aranjamente(coloane , 2 * luate_1) % mod * Exponentiere(Exponentiere(2 , luate_1) , mod - 2) % mod *
                                     Combinari(coloane - 2 * luate_1 , luate_2) % mod * Aranjamente(linii - luate_1 , 2 * luate_2) % mod * Exponentiere(Exponentiere(2 , luate_2) , mod - 2) % mod;

            int __linii = linii - luate_1 - 2 * luate_2 , __coloane = coloane - luate_2 - 2 * luate_1;
            for (int luate_3 = 0 ; luate_3 <= min(__linii , __coloane) ; luate_3++) {
                if ((modalitati += 1LL * factor % mod * Combinari(__linii , luate_3) % mod * Aranjamente(__coloane , luate_3) % mod * Exponentiere(4 , luate_3) % mod) >= mod)
                    { modalitati -= mod; }
            }
        }
    }
    
    cout << modalitati;
    return 0;
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52