Codeforces Round #554 (Div. 2) Editorial
Difference between en7 and en8, changed 325 character(s)
*Some tutorials are not available yet. Please be patient. ;)*↵

[problem:1152A]↵
------------------↵
Author: [user:xuanquang1999,2019-04-24]  ↵
Development: [user:xuanquang1999,2019-04-24], [user:Akikaze,2019-04-24], [user:GreenGrape,2019-04-24]  ↵
Theme development: [user:Akikaze,2019-04-24], [user:GreenGrape,2019-04-24]  ↵
Editorialist: [user:xuanquang1999,2019-04-24]  ↵


<spoiler summary="Tutorial">↵
[tutorial:1152A]↵
</spoiler>↵


<spoiler summary="Solution (xuanquang1999)">↵
Submission link: [submission:53259456]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main(int argc, char* argv[])↵
{↵
    int n, m;↵
    scanf("%d%d", &n, &m);↵

    vector<int> a(n), b(m);↵
    for(int i = 0; i < n; ++i)↵
        scanf("%d", &a[i]);↵
    for(int i = 0; i < m; ++i)↵
        scanf("%d", &b[i]);↵

    int c0 = 0, c1 = 0;↵
    for(int i = 0; i < n; ++i)↵
        if (a[i]%2 == 0)↵
            ++c0;↵
        else↵
            ++c1;↵

    int k0 = 0, k1 = 0;↵
    for(int i = 0; i < m; ++i)↵
        if (b[i]%2 == 0)↵
            ++k0;↵
        else↵
            ++k1;↵

    int ans = min(c1, k0) + min(c0, k1);↵

    printf("%d", ans);↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵


[problem:1152B]↵
------------------↵
Author: [user:Akikaze,2019-04-24]  ↵
Development: [user:Akikaze,2019-04-24]
, [user:xuanquang1999,2019-04-24]  ↵
Theme development: [user:Akikaze,2019-04-24]  ↵
Editorialist: [user:Akikaze,2019-04-24]  ↵


<spoiler summary="Tutorial">↵
[tutorial:1152B]↵
</spoiler>↵


<spoiler summary="Solution 1 - Greedy (Akikaze)">↵
Submission link: [submission:53259692]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#pragma comment(linker, "/stack:247474112")↵
#pragma GCC optimize("Ofast")↵

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

#define endl '\n'↵

int x;↵

bool isCompletion(int z) {↵
int bitval = 0;↵
z += 1; while (z % 2 == 0) {z /= 2; bitval++;}↵
return (z == 1);↵
}↵

int MSB(int z) {↵
for (int i=20; i>=0; i--) {↵
if ((z >> i) & 1) return i;↵
}↵
return -1;↵
}↵

void Input() {↵
cin >> x;↵
}↵

void Solve() {↵
int i = 0; vector<int> xorCmd;↵
while (isCompletion(x)) {↵
i = i + 1;↵
if (i % 2 == 0) {x++; continue;}↵
int r = MSB(x);↵
if ((1 << r) != x) r++;↵
x = (x ^ ((1 << r) - 1)); xorCmd.push_back(r);↵
}↵
cout << i << endl;↵
for (auto z: xorCmd) cout << z << " "; cout << endl;↵
}↵

int main(int argc, char* argv[]) {↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL); Input(); Solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Solution 2 - BFS (Akikaze)">↵
Submission link: [submission:53259743]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#pragma comment(linker, "/stack:247474112")↵
#pragma GCC optimize("Ofast")↵

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

#define endl '\n'↵

int x; vector<vector<int>> vis(2, vector<int>(1048576, INT_MAX));↵
vector<vector<pair<int, int>>> Last(2, vector<pair<int, int>>(1048576, {-1LL, -1LL}));↵

int isCompletion(int z) {↵
int bitval = 0;↵
z += 1; while (z % 2 == 0) {z /= 2; bitval++;}↵
if (z != 1) return -1;↵
return bitval;↵
}↵

void Input() {↵
cin >> x;↵
}↵

void Solve() {↵
queue<pair<int, int>> Q;↵
vis[0][x] = 0; Q.push({0, x});↵
int p1 = -1, p2 = -1;↵
while (!Q.empty()) {↵
pair<int, int> Token = Q.front();↵
int p = Token.first, z = Token.second; Q.pop();↵
if (isCompletion(z) != -1) {p1 = p; p2 = z; break;}↵
if (p == 1) {↵
if (vis[0][z+1] == INT_MAX) {↵
vis[0][z+1] = vis[1][z] + 1;↵
Last[0][z+1] = {1, z}; Q.push({0, z+1});↵
}↵
}↵
else {↵
for (int i=0; i<20; i++) {↵
int t = (z ^ ((1 << i) - 1));↵
if (vis[1][t] != INT_MAX) continue;↵
vis[1][t] = vis[0][z] + 1;↵
Last[1][t] = {0, z}; Q.push({1, t});↵
}↵
}↵
}↵

cout << vis[p1][p2] << endl;↵

vector<int> xorCmd;↵
while (Last[p1][p2] != make_pair(-1, -1)) {↵
pair<int, int> Token = Last[p1][p2];↵
int z = Token.first, t = Token.second;↵
if (p1 == 1) xorCmd.push_back(isCompletion(p2 ^ t));↵
p1 = z; p2 = t;↵
}↵

reverse(xorCmd.begin(), xorCmd.end());↵
for (auto z: xorCmd) cout << z << " ";↵
}↵

int main(int argc, char* argv[]) {↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL); Input(); Solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵


[problem:1152C]↵
------------------↵
Author: [user:stefdasca,2019-04-24]  ↵
Development: [user:stefdasca,2019-04-24], [user:Akikaze,2019-04-24]  ↵
Theme development: [user:xuanquang1999,2019-04-24], [user:neko_nyaa,2019-04-24]  ↵
Editorialist: [user:stefdasca,2019-04-24]  ↵


<spoiler summary="Tutorial">↵
[tutorial:1152C]↵
</spoiler>↵


<spoiler summary="Solution (implemented by stefdasca)">↵
Submission link: [submission:53259956]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include<bits/stdc++.h>↵
#pragma GCC optimize("O3")↵
using namespace std;↵
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());↵
long long rand_seed()↵
{↵
long long a = rng();↵
    return a;↵
}↵
long long a, b;↵
int main()↵
{↵
    ios_base::sync_with_stdio(false);↵
    cin.tie(NULL);↵
    cin >> a >> b;↵
    long long dif = abs(a - b);↵
    vector<int>v;↵
    for(int i = 1; i * i <= dif; ++i)↵
    {↵
        if(dif % i == 0)↵
        {↵
            v.push_back(i);↵
            if(i * i != dif)↵
                v.push_back(dif / i);↵
        }↵
    }↵
    long long ans = (1LL<<62);↵
    int vl = 0;↵
    sort(v.begin(), v.end());↵
    for(int i = 0; i < v.size(); ++i)↵
    {↵
        int nr = v[i];↵
        if(a % nr != b % nr)↵
            continue;↵
        if(a % nr == 0)↵
        {↵
            long long pans = (a * b)/__gcd(a, b);↵
            if(pans < ans)↵
                ans = pans, vl = 0;↵
        }↵
        else↵
        {↵
            long long pans = ((nr - a % nr + a) * (nr - b % nr + b))/__gcd((nr - a % nr + a), (nr - b % nr + b));↵
            if(pans < ans)↵
                ans = pans, vl = nr - a % nr;↵
        }↵
    }↵
    cout << vl;↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Solution (implemented by Akikaze)">↵
Submission link: [submission:53260012]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#pragma comment(linker, "/stack:247474112")↵
#pragma GCC optimize("Ofast")↵

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

#define endl '\n'↵

int a, b;↵

void Input() {↵
cin >> a >> b;↵
}↵

void Solve() {↵
if (a == b) {cout << "0\n"; return;}↵

vector<int> Divisors;↵
for (int i=1; i<=sqrt(max(a,b) - min(a,b)); i++) {↵
if ((max(a,b) - min(a,b)) % i != 0) continue;↵
int j = (max(a,b) - min(a,b)) / i;↵
Divisors.push_back(i);↵
if (i != j) Divisors.push_back(j);↵
}↵

pair<long long, int> Token = make_pair(LLONG_MAX, INT_MAX);↵
for (auto d: Divisors) {↵
if (a % d == b % d) {↵
int k = (d - a % d) % d;↵
pair<long long, int> NewToken = make_pair(1LL * (0LL + a + k) / __gcd(0LL+a+k, 0LL+b+k) * (0LL + b + k), k);↵
Token = min(Token, NewToken);↵
}↵
}↵

cout << Token.second << endl;↵
}↵

int main(int argc, char* argv[]) {↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL); Input(); Solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵


[problem:1152D]↵
------------------↵
Author: [user:_kun_,2019-04-24]  ↵
Development: [user:_kun_,2019-04-24]  ↵
Theme development: [user:xuanquang1999,2019-04-24]  ↵
Editorialist: [user:_kun_,2019-04-24]  ↵


<spoiler summary="Tutorial">↵
[tutorial:1152D]↵
</spoiler>↵


<spoiler summary="Solution (_kun_)">↵
Submission link: [submission:53260068]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
// Dmitry _kun_ Sayutin (2019)↵

#include <bits/stdc++.h>↵

using std::cin;↵
using std::cout;↵
using std::cerr;↵

using std::vector;↵
using std::map;↵
using std::array;↵
using std::set;↵
using std::string;↵

using std::pair;↵
using std::make_pair;↵

using std::tuple;↵
using std::make_tuple;↵
using std::get;↵

using std::min;↵
using std::abs;↵
using std::max;↵
using std::swap;↵

using std::unique;↵
using std::sort;↵
using std::generate;↵
using std::reverse;↵
using std::min_element;↵
using std::max_element;↵

#ifdef LOCAL↵
#define LASSERT(X) assert(X)↵
#else↵
#define LASSERT(X) {}↵
#endif↵

template <typename T>↵
T input() {↵
    T res;↵
    cin >> res;↵
    LASSERT(cin);↵
    return res;↵
}↵

template <typename IT>↵
void input_seq(IT b, IT e) {↵
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);↵
}↵

#define SZ(vec)         int((vec).size())↵
#define ALL(data)       data.begin(),data.end()↵
#define RALL(data)      data.rbegin(),data.rend()↵
#define TYPEMAX(type)   std::numeric_limits<type>::max()↵
#define TYPEMIN(type)   std::numeric_limits<type>::min()↵

const int mod = 1000 * 1000 * 1000 + 7;↵
int add(int a, int b) {↵
    return (a + b >= mod ? a + b - mod : a + b);↵
}↵

const int max_n = 1001;↵
pair<int, bool> dp[2 * max_n][2 * max_n];↵

int main() {↵
    std::iostream::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
    cout.tie(nullptr);↵

    // code here↵
    int n = input<int>();↵
    n *= 2;↵

    assert(n / 2 < max_n);↵
        ↵
    ↵
    dp[0][0] = make_pair(0, true);↵
    ↵
    for (int len = 1; len <= n; ++len) {↵
        for (int bal = 0; bal <= n; ++bal) {↵
            // (len, bal) -> (len - 1, bal + 1)↵
            // (len, bal) -> (len - 1, bal - 1)↵

            int sum = 0;↵
            bool has = false;↵

            if (bal != 0) {↵
                sum = add(sum, dp[len - 1][bal - 1].first);↵
                has = has or dp[len - 1][bal - 1].second;↵
            }↵

            if (bal + 1 <= len - 1) {↵
                sum = add(sum, dp[len - 1][bal + 1].first);↵
                has = has or dp[len - 1][bal + 1].second;↵
            }↵

            if (has)↵
                dp[len][bal] = make_pair(add(sum, 1), false);↵
            else↵
                dp[len][bal] = make_pair(sum, true);↵
        }↵
    }↵
    ↵
    cout << dp[n][0].first << "\n";↵
    ↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵


[problem:1152E]↵
------------------↵
Author: [user:xuanquang1999,2019-04-24]  ↵
Development: [user:xuanquang1999,2019-04-24]  ↵
Theme development: [user:xuanquang1999,2019-04-24]  ↵
Editorialist: [user:xuanquang1999,2019-04-24]  ↵


<spoiler summary="Tutorial">↵
*This [tutorial wasn't available yet. Quang felt a bit exhausted after the round and asked me to postpone it. Given that we were a bit rushing at the last minutes to properly give the best F possible, this is understandable. ;)*:1152E]
</spoiler>↵


<spoiler summary="Solution (xuanquang1999)">↵
Submission link: [submission:53260100]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

typedef pair<int, int> pii;↵

class Indexer {↵
private:↵
    map<int, int> id;↵
    vector<int> num;↵

public:↵
    int getId(int x) {↵
        if (!id.count(x)) {↵
            id[x] = num.size();↵
            num.push_back(x);↵
        }↵
        return id[x];↵
    }↵

    int getNum(int id) {↵
        return num[id];↵
    }↵

    int size() {↵
        return id.size();↵
    }↵
};↵

struct Edge {↵
    int u, v;↵
    bool avail;↵
};↵

class Graph {↵
private:↵
    int n;↵
    vector<Edge> e;↵
    vector<vector<int> > adj;↵

    vector<int> pos;↵
    list<int> path;↵

    void dfs(list<int>::iterator it, int u) {↵
        for(; pos[u] < adj[u].size(); ++pos[u]) {↵
            int id = adj[u][pos[u]];↵
            if (e[id].avail) {↵
                e[id].avail = false;↵
                int v = e[id].u + e[id].v - u;↵
                dfs(path.insert(it, u), v);↵
            }↵
        }↵
    }↵

public:↵
    Graph(int n): n(n) {↵
        adj.assign(n, vector<int>());↵
    }↵

    void addEdge(int u, int v) {↵
        adj[u].push_back(e.size());↵
        adj[v].push_back(e.size());↵
        e.push_back({u, v, false});↵
    }↵

    vector<int> eulerPath() {↵
        for(Edge &p: e)↵
            p.avail = true;↵
        path.clear();↵
        pos.assign(n, 0);↵

        vector<int> odd;↵
        for(int u = 0; u < n; ++u)↵
            if (adj[u].size() % 2 == 1)↵
                odd.push_back(u);↵
        if (odd.empty()) {↵
            odd.push_back(0);↵
            odd.push_back(0);↵
        }↵

        if (odd.size() > 2)↵
            return vector<int>();↵
        dfs(path.begin(), odd[0]);↵
        path.insert(path.begin(), odd[1]);↵

        return vector<int>(path.begin(), path.end());↵
    }↵
};↵

int main() {↵
    int n;↵
    scanf("%d", &n);↵

    vector<int> bprime(n-1);↵
    for(int i = 0; i < n-1; ++i)↵
        scanf("%d", &bprime[i]);↵

    vector<int> cprime(n-1);↵
    for(int i = 0; i < n-1; ++i)↵
        scanf("%d", &cprime[i]);↵

    Indexer ind;↵
    for(int i = 0; i < n-1; ++i) {↵
        if (bprime[i] > cprime[i]) {↵
            puts("-1");↵
            return 0;↵
        }↵

        bprime[i] = ind.getId(bprime[i]);↵
        cprime[i] = ind.getId(cprime[i]);↵
    }↵

    int k = ind.size();↵
    Graph g(k);↵
    for(int i = 0; i < n-1; ++i)↵
        g.addEdge(bprime[i], cprime[i]);↵

    vector<int> a = g.eulerPath();↵

    if (a.size() < n)↵
        puts("-1");↵
    else {↵
        for(int i = 0; i < n; ++i)↵
            printf("%d ", ind.getNum(a[i]));↵
        puts("");↵
    }↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵


[problem:1152F1]↵
------------------↵
[problem:1152F2]↵
------------------↵
Author: [user:MofK,2019-04-24]  ↵
Development: [user:MofK,2019-04-24], [user:xuanquang1999,2019-04-24], [user:Akikaze,2019-04-24]  ↵
Theme development: [user:xuanquang1999,2019-04-24], [user:Akikaze,2019-04-24]  ↵
Editorialist: [user:MofK,2019-04-24], [user:Akikaze,2019-04-24]  ↵


<spoiler summary="Tutorial - F1 (Small version)">↵
[tutorial:1152F1]↵
</spoiler>↵

<spoiler summary="Tutorial - F2 (Large version)">↵
[tutorial:1152F2]↵
</spoiler>↵


<spoiler summary="Solution F1 (xuanquang1999)">↵
Submission link: [submission:53260139]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int MOD = 1000000007;↵

void add(int &a, long long b) {↵
    a = (a + b) % MOD;↵
}↵

int main() {↵
    int n, k, m;↵
    scanf("%d%d%d", &n, &k, &m);↵

    vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(1<<m, 0)));↵
    dp[0][0][0] = 1;↵

    for(int i = 0; i < n; ++i) {↵
        for(int j = 0; j <= k; ++j) {↵
            for(int mask = 0; mask < (1<<m); ++mask) {↵
                int newMask = (mask << 1) % (1<<m);↵

                // Not visit planet i+1↵
                add(dp[i+1][j][newMask], dp[i][j][mask]);↵

                // Visit planet i+1↵
                if (j < k) {↵
                    int insertWays = __builtin_popcount(mask) + 1;↵
                    add(dp[i+1][j+1][newMask|1], 1LL*insertWays*dp[i][j][mask]);↵
                }↵
            }↵
        }↵
    }↵

    int ans = 0;↵
    for(int mask = 0; mask < (1<<m); ++mask)↵
        add(ans, dp[n][k][mask]);↵

    printf("%d", ans);↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Solution F2 (xuanquang1999)">↵
Submission link: [submission:53260164]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int MOD = 1000000007;↵

void add(int &a, long long b) {↵
    a = (a + b) % MOD;↵
}↵

struct Matrix {↵
    vector<vector<int>> a;↵
    int n, m;↵

    Matrix(int n, int m): n(n), m(m) {↵
        a.assign(n, vector<int>(m, 0));↵
    }↵

    friend Matrix operator * (Matrix a, Matrix b) {↵
        Matrix c(a.n, b.m);↵
        for(int i = 0; i < a.n; ++i)↵
            for(int j = 0; j < b.m; ++j)↵
                for(int k = 0; k < a.m; ++k)↵
                    add(c.a[i][j], 1LL * a.a[i][k] * b.a[k][j]);↵
        return c;↵
    }↵
};↵

Matrix identity(int n) {↵
    Matrix res(n, n);↵
    for(int i = 0; i < n; ++i)↵
        res.a[i][i] = 1;↵
    return res;↵
}↵

void power(Matrix &a, int n, Matrix &b) {↵
    while (n > 0) {↵
        if (n&1) b = a * b;↵
        a = a * a;↵
        n >>= 1;↵
    }↵
}↵

int n, k, m;↵

int toId(int j, int mask) {↵
    return j * (1<<m) + mask;↵
}↵

int main() {↵
    scanf("%d%d%d", &n, &k, &m);↵

    Matrix dp((k+1) * (1<<m), 1);↵
    dp.a[0][0] = 1;↵

    Matrix f((k+1) * (1<<m), (k+1) * (1<<m));↵

    for(int j = 0; j <= k; ++j) {↵
        for(int mask = 0; mask < (1<<m); ++mask) {↵
            int newMask = (mask << 1) % (1<<m);↵
            int cur = toId(j, mask);↵

            f.a[toId(j, newMask)][cur] = 1;↵
            if (j < k)↵
                f.a[toId(j+1, newMask|1)][cur] = __builtin_popcount(mask) + 1;↵
        }↵
    }↵

    power(f, n, dp);↵

    int ans = 0;↵
    for(int mask = 0; mask < (1<<m); ++mask)↵
        add(ans, dp.a[toId(k, mask)][0]);↵

    printf("%d", ans);↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Solution F2 (veryheckingfast by MofK)">↵
Submission link: [submission:53260183]↵

<spoiler summary="Source code in plain text">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

const int mod = 1e9 + 7;↵

void add(long long &a, long long b) {↵
    a = (a + b) % mod;↵
}↵

long long f[2][1005][1024];↵
int pc[1024];↵

long long solve(int n, int k, int m) {↵
    memset(f, 0, sizeof f);↵
    f[0][0][0] = 1;↵
    for (int i = 0; i < n; ++i) {↵
        int x = i & 1, y = 1 - x;↵
        memset(f[y], 0, sizeof f[y]);↵
        for (int j = 0; j <= k; ++j) {↵
            for (int mask = 0; mask < (1 << m); ++mask) {↵
                int new_mask = mask >> 1;↵
                add(f[y][j][new_mask], f[x][j][mask]);↵
                add(f[y][j+1][new_mask + (1<<m-1)], f[x][j][mask] * (pc[mask] + 1));↵
            }↵
        }↵
    }↵
    long long ret = 0;↵
    for (int mask = 0; mask < (1 << m); ++mask)↵
        add(ret, f[n&1][k][mask]);↵
    return ret;↵
}↵

typedef vector <vector <long long>> mat;↵
mat operator *(const mat &a, const mat &b) {↵
    mat c(a.size(), vector <long long>(b[0].size(), 0));↵
    for (int i = 0; i < a.size(); ++i)↵
        for (int j = 0; j < b.size(); ++j)↵
            for (int k = 0; k < b[0].size(); ++k)↵
                add(c[i][k], a[i][j] * b[j][k]);↵
    return c;↵
}↵
mat operator +(const mat &a, const mat &b) {↵
    mat c = a;↵
    for (int i = 0; i < a.size(); ++i)↵
        for (int j = 0; j < a[0].size(); ++j)↵
            add(c[i][j], b[i][j]);↵
    return c;↵
}↵

mat A(int m) {↵
    mat a(1 << m, vector <long long>(1 << m, 0));↵
    for (int i = 0; i < (1 << m - 1); ++i)↵
        a[i][i*2] = a[i][i*2 + 1] = 1;↵
    return a;↵
}↵
mat B(int m) {↵
    mat b(1 << m, vector <long long>(1 << m, 0));↵
    for (int i = 0; i < (1 << m - 1); ++i) {↵
        b[i + (1<<m-1)][i*2] = pc[i] + 1;↵
        b[i + (1<<m-1)][i*2 + 1] = pc[i] + 2;↵
    }↵
    return b;↵
}↵
mat U(int m) {↵
    mat u(1 << m, vector <long long>(1 << m, 0));↵
    for (int i = 0; i < (1 << m); ++i)↵
        u[i][i] = 1;↵
    return u;↵
}↵
mat O(int m) {↵
    return mat(1 << m, vector <long long>(1 << m, 0));↵
}↵

void convo(vector <mat> &a, vector <mat> b, int m, int k) {↵
    int sz = min(k + 1, (int)(a.size() + b.size() + 1));↵
    a.resize(sz, O(m));↵
    for (int i = sz - 1; i >= 0; --i) {↵
        a[i] = a[i] * b[0];↵
        for (int j = 1; j <= i && j < b.size(); ++j)↵
            a[i] = a[i] + a[i-j] * b[j];↵
    }↵
}↵
long long solve3(int n, int k, int m) {↵
    vector <mat> ans, mul;↵
    --n;↵
    ans = mul = {A(m), B(m)};↵
    while (n) {↵
        if (n & 1) convo(ans, mul, m, k);↵
        convo(mul, mul, m, k);↵
        n >>= 1;↵
    }↵
    long long ret = 0;↵
    for (int i = 0; i < (1 << m); ++i)↵
        add(ret, ans[k][i][0]);↵
    return ret;↵
}↵

int main(void) {↵
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);↵
    int n, k, m;↵
    for (int i = 1; i < 1024; ++i) pc[i] = pc[i - (i&-i)] + 1;↵
    while (cin >> n >> k >> m)↵
        cout << solve3(n, k, m) << endl;↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

</spoiler>↵

<spoiler summary="Bonus">↵
Solve the problem in (or faster than) $\mathcal{O} \left( \log(n) \cdot k^2 \cdot {\left( 2^m \right)}^3 \right)$.↵
</spoiler>↵


-----↵


<spoiler summary="Authors' logs (miscellaneous things during our preparations)">↵

<spoiler summary="Log-1">↵
~xuanquang1999,2019-04-24 actually proposed ~10 problems yet our dear ~_kun_,2019-04-24 denied half of them.  ↵
I also proposed 4 and got denied 3 first one as well :-P  ↵
![ ](https://i.imgur.com/AfZq1cH.jpg)↵
</spoiler>↵

<spoiler summary="Log-2">↵
Problem B is the last invented problem. I was walking around the computer labs, thinking of some photoshopped Catzilla cat memes, which led to me thinking of enlarging cute kittens, then coming up with this problem.↵

Ironicly though, my model greedy solution would actually shrink the cats instead.↵

Anyway, I forgot this picture about longcat:  ↵
![ ](https://i.imgur.com/oOCSxZm.jpg)↵
</spoiler>↵

<spoiler summary="Log-3">↵
~neko_nyaa,2019-04-24 and I after I finished writing statements of B:  ↵
![ ](https://i.imgur.com/CWUlEg2.jpg)↵
</spoiler>↵

<spoiler summary="Log-4">↵
~MofK,2019-04-24 went haywire after seeing first AC of problem F2 by ~dreamoon,2019-04-24. Poor MofK, he wrote a superbly veryheckingfast solution for F2 and was still outmatched. :<  ↵
P/s: Funny, in Codeforces both solutions have the same max execution time :D↵
![ ](https://i.imgur.com/THeFzTM.jpg)↵
</spoiler>↵

</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English AkiLotus 2019-04-25 11:47:29 1 Tiny change: '\n while (isCompleti' -> '\n while (!isCompleti'
en9 English AkiLotus 2019-04-25 08:45:07 39
en8 English AkiLotus 2019-04-25 08:26:59 325
en7 English AkiLotus 2019-04-24 22:23:21 78
en6 English AkiLotus 2019-04-24 22:20:44 276 (published)
en5 English AkiLotus 2019-04-24 21:54:43 17437
en4 English AkiLotus 2019-04-24 21:18:25 1324
en3 English AkiLotus 2019-04-24 20:31:39 157 Tiny change: 'er than) $mathcal{O}' -> 'er than) $\mathcal{O}'
en2 English AkiLotus 2019-04-24 19:44:21 3163
en1 English AkiLotus 2019-04-24 18:44:09 600 Initial revision (saved to drafts)