AtCoder Grand Contest 005

Submission #1354767

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> 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

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

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

./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);
^

Test case

Set

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