Submission #1126983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126983		seoul_korea	Zapina (COCI20_zapina)	C++20	22 / 110	20 ms	328 KiB

zapina

/**
 faksld fjkladsj kfolsdajk l fjkdlas jflksadklj fjklsd
**/
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

mt19937 rng(time(0));

const int N = 1000, MOD = (int)1e9 + 7;
void add(int& a, int b)
{
    a += b;
    if(a < 0) a += MOD;
    a %= MOD;
}

int n;
namespace Subtask1
{
    int gr[N], ans = 0;
    void Backtrack(int p)
    {
        if(p == n + 1)
        {
            vector<int> c(n + 1);
            REP(i, n)
                c[gr[i]]++;
            bool ok = 0;
            REP(i, n)
                if(c[i] == i)
                    ok = 1;
            ans += ok;
            return;
        }
        REP(i, n)
        {
            gr[p] = i;
            Backtrack(p + 1);
        }
    }

    void Solve()
    {
        Backtrack(1);
        cout << ans;
    }
}

int POW(int a, int b)
{
    int res = 1;
    for(; b; b >>= 1, a = 1ll * a * a % MOD) if(b & 1) res = 1ll * res * a % MOD;
    return res;
}

int dp[N][N], C[N][N];

signed main(void)
{
    cin.tie(nullptr)->sync_with_stdio(false);
    #define TASK ""
    if(fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    cin >> n;
    if(n <= 7) return Subtask1::Solve(), 0;
    else
    {
        FOR(i, 0, n)
        {
            C[i][0] = 1;
            REP(j, i)
            {
                C[i][j] = C[i - 1][j];
                add(C[i][j], C[i - 1][j - 1]);
            }
        }
        int tot = POW(n, n);
        dp[0][0] = 1;
        FOR(i, 0, n - 1)
        {
            FOR(j, 0, n)
            {
                FOR(k, 0, n - j)
                {
                    if(k != i + 1)
                    {
                        add(dp[i + 1][j + k], 1ll * dp[i][j] * C[n - j][k] % MOD);
                    }
                }
            }
        }
        cout << (tot - dp[n][n]) % MOD;
    }
    return 0;
}

Compilation message (stderr)

zapina.cpp: In function 'int main()':
zapina.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zapina.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 55