Submission #9437198 - AtCoder Grand Contest 005 | AtCoder

// ===================================

//   author: M_sea

//   website: http://m-sea-blog.com/

// ===================================

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cmath>

#define re register

using namespace std;

inline int read()

{

    int X = 0, w = 1;

    char c = getchar();

    while (c < '0' || c > '9')

    {

        if (c == '-')

            w = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9')

        X = X * 10 + c - '0', c = getchar();

    return X * w;

}

const int N = 2000 + 10;

const int mod = 924844033;

int n, k;

int a[N << 1], cnt = 0;

int fac[N], dp[N << 1][N][2];

int main()

{

    n = read(), k = read();

    for (re int i = 1; i <= k; ++i)

    {

        for (re int j = i; j <= n; j += k)

            a[++cnt] = j == i;

        for (re int j = i; j <= n; j += k)

            a[++cnt] = j == i;

    }

    dp[0][0][0] = 1;

    for (re int i = 0; i < cnt; ++i)

        for (re int j = 0; j <= n; ++j)

        {

            dp[i + 1][j][0] = (dp[i][j][0] + dp[i][j][1]) % mod;

            if (!a[i + 1])

                dp[i + 1][j + 1][1] = dp[i][j][0];

        }

    fac[0] = 1;

    for (re int i = 1; i <= n; ++i)

        fac[i] = 1ll * fac[i - 1] * i % mod;

    int ans = 0;

    for (re int i = 0; i <= n; ++i)

    {

        int w = 1ll * (dp[cnt][i][0] + dp[cnt][i][1]) * fac[n - i] % mod;

        if (i & 1)

            ans = (ans - w + mod) % mod;

        else

            ans = (ans + w) % mod;

    }

    printf("%d\n", ans);

    return 0;

}

Submission
Task D - ~K Perm Counting
User name M_sea
Created time 2020/01/12 16:57:12
Language C++14 (GCC 5.4.1)
Status AC
Score 900
Source length 1273 Byte
File name
Exec time 32 ms
Memory usage 63104 KB