Submission #1248434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248434		wedonttalkanymore	Soccer (JOI17_soccer)	C++20	0 / 100	1 ms	324 KiB

soccer

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1000000007;

inline int modadd(int a, int b) {
    a += b;
    return a < mod ? a : a - mod;
}

inline int modmul(ll a, ll b) {
    return (int)(a * b % mod);
}

vector<ll> merge(const vector<ll>& a, const vector<ll>& b, int k) {
    int na = a.size(), nb = b.size();
    int nc = min(k, na + nb - 2) + 1;
    vector<ll> c(nc);
    for (int i = 0; i < na; i++) {
        if (a[i]) {
            for (int j = 0; j < nb && i + j < nc; j++) {
                c[i + j] = (c[i + j] + a[i] * b[j]) % mod;
            }
        }
    }
    return c;
}

vector<ll> power(vector<ll> a, int e, int k) {
    vector<ll> r(1, 1);
    while (e) {
        if (e & 1) r = merge(r, a, k);
        a = merge(a, a, k);
        e >>= 1;
    }
    return r;
}

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

    if (fopen("zid.in", "r")) {
        freopen("zid.in", "r", stdin);
        freopen("zid.out", "w", stdout);
    }

    int n, m, k;
    cin >> n >> m >> k;

    static int dp[3][5005], odd[3][5005], even[3][5005];
    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) {
        int cur = i % 3, pre = (i - 1) % 3, pre2 = (i + 1) % 3;

        for (int j = 0; j <= k; j++) {
            dp[cur][j] = odd[cur][j] = even[cur][j] = 0;
        }

        for (int j = 0; j <= k; j++) {
            int a = dp[pre][j];
            int b = (i >= 2 ? odd[pre2][j] : 0);
            odd[cur][j] = modadd(a, b);

            int c = (i >= 2 && j >= 2 ? dp[pre2][j - 2] : 0);
            int d = (i >= 2 && j >= 2 ? even[pre2][j - 2] : 0);
            even[cur][j] = modadd(c, d);

            dp[cur][j] = modadd(odd[cur][j], even[cur][j]);
        }
    }

    vector<ll> f(k + 1);
    for (int i = 0; i <= k; i++) f[i] = dp[n % 3][i];

    vector<ll> res = power(f, m, k);
    cout << (k < res.size() ? res[k] : 0);

    return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen("zid.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen("zid.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 65