Submission #1354767


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 924844033;
ll fac[2100];
ll res;
int n, k;

vector<ll> prod(vector<ll> a, vector<ll> b) {
    int i,j;
    vector<ll> c(n+1,0);
    for (i=0;i<=n;i++) {
        for (j=0;j<=i;j++) c[i] += (a[j]*b[i-j])%MOD;
        c[i] %= MOD;
    }
    return c;
}

vector<ll> base;
vector<ll> power(vector<ll> a, int p) {
    if (p==0) return base;
    vector<ll> tmp = power(a,p/2);
    if (p&1) return prod(prod(tmp,tmp),a);
    return prod(tmp,tmp);
}

ll dyn[4200][2100];

vector<ll> calc(int p) {
    int i, j;
    if (p==0) return base;
    memset(dyn,0,sizeof(dyn));
    dyn[0][0] = dyn[0][1] = dyn[1][0] = 1;
    dyn[1][1] = 2;
    for (i=2;i<p;i++) {
        dyn[i][0] = 1;
        for (j=1;j<=i/2+1;j++) {
            dyn[i][j] = (dyn[i-1][j]+dyn[i-2][j-1])%MOD;
        }
    }
    vector<ll> ad(n+1,0);
    for (i=0;i<=n;i++) ad[i] = dyn[p-1][i];
    return ad;
}

int main() {
    int i;

    fac[0] = 1;
    for (i=1;i<=2010;i++) fac[i] = (fac[i-1]*i)%MOD;
    scanf("%d%d",&n,&k);
    base.assign(n+1,0);
    base[0] = 1;
    int s = 1, p, q, a, b;
    p = 2*(n-(n-1)/k*k); q = 2*min(k,n-k)-p;
    a = (n-1)/k; b = a-1;
    vector<ll> fd = prod(power(calc(a),p),power(calc(b),q));
    for (i=0;i<=n;i++) {
        res += (((s*fac[n-i])%MOD)*fd[i])%MOD;
        s = -s;
        res %= MOD;
    }
    res += MOD;
    res %= MOD;
    printf("%lld\n",res);


    return 0;
}

Submission Info

Submission Time
Task D - ~K Perm Counting
User tlwpdus
Language C++14 (GCC 5.4.1)
Score 900
Code Size 1530 Byte
Status AC
Exec Time 154 ms
Memory 69448 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:54:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 5
AC × 28
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All example0, example1, example2, example3, example4, handmade0, handmade1, handmade2, handmade3, handmade4, handmade5, handmade6, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, rand0, rand1, rand2, rand3, rand4, small0, small1, small2, supersmall0, supersmall1, supersmall2
Case Name Status Exec Time Memory
example0 AC 27 ms 69120 KB
example1 AC 27 ms 69120 KB
example2 AC 19 ms 69120 KB
example3 AC 19 ms 69120 KB
example4 AC 30 ms 69248 KB
handmade0 AC 18 ms 69120 KB
handmade1 AC 47 ms 69376 KB
handmade2 AC 36 ms 69376 KB
handmade3 AC 45 ms 69376 KB
handmade4 AC 33 ms 69376 KB
handmade5 AC 103 ms 69376 KB
handmade6 AC 73 ms 69376 KB
maxrand0 AC 77 ms 69424 KB
maxrand1 AC 144 ms 69436 KB
maxrand2 AC 154 ms 69444 KB
maxrand3 AC 92 ms 69376 KB
maxrand4 AC 65 ms 69376 KB
rand0 AC 128 ms 69448 KB
rand1 AC 24 ms 69248 KB
rand2 AC 24 ms 69248 KB
rand3 AC 19 ms 69120 KB
rand4 AC 76 ms 69376 KB
small0 AC 29 ms 69248 KB
small1 AC 27 ms 69248 KB
small2 AC 19 ms 69248 KB
supersmall0 AC 19 ms 69120 KB
supersmall1 AC 27 ms 69120 KB
supersmall2 AC 27 ms 69120 KB