AtCoder Grand Contest 005

Submission #1354758

Source codeソースコード

#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> power(vector<ll> a, int p) {
    if (p==0) {
        vector<ll> tmp(n+1,0);
        tmp[0] = 1;
        return tmp;
    }
    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;
    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);
    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

Task問題 D - ~K Perm Counting
User nameユーザ名 tlwpdus
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 RE
Score得点 0
Source lengthソースコード長 1511 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Compiler messageコンパイルメッセージ

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

Test case

Set

Set name Score得点 / Max score Cases
Sample - example0,example1,example2,example3,example4
All 0 / 900 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
example0 AC 27 ms 69120 KB
example1 AC 27 ms 69120 KB
example2 RE
example3 RE
example4 AC 31 ms 69248 KB
handmade0 RE
handmade1 AC 48 ms 69376 KB
handmade2 RE
handmade3 AC 46 ms 69248 KB
handmade4 RE
handmade5 AC 104 ms 69376 KB
handmade6 AC 74 ms 69376 KB
maxrand0 RE
maxrand1 AC 145 ms 69436 KB
maxrand2 AC 154 ms 69448 KB
maxrand3 AC 93 ms 69376 KB
maxrand4 RE
rand0 AC 129 ms 69444 KB
rand1 RE
rand2 RE
rand3 RE
rand4 RE
small0 AC 29 ms 69248 KB
small1 AC 28 ms 69120 KB
small2 RE
supersmall0 RE
supersmall1 AC 27 ms 69120 KB
supersmall2 AC 27 ms 69120 KB