Submission #1354755
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> 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);
vector<ll> nmp = prod(tmp,tmp);
if (p&1) return prod(nmp,a);
return nmp;
}
ll dyn[2100][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 Info
Submission Time
2017-06-15 12:14:22+0900
Task
D - ~K Perm Counting
User
tlwpdus
Language
C++14 (GCC 5.4.1)
Score
0
Code Size
1528 Byte
Status
RE
Exec Time
142 ms
Memory
35032 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:57: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
0 / 900
Status
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
15 ms
34688 KB
example1
AC
15 ms
34688 KB
example2
RE
120 ms
34688 KB
example3
RE
112 ms
34688 KB
example4
AC
18 ms
34816 KB
handmade0
RE
108 ms
34688 KB
handmade1
AC
36 ms
34816 KB
handmade2
RE
109 ms
34688 KB
handmade3
AC
33 ms
34816 KB
handmade4
RE
109 ms
34688 KB
handmade5
AC
91 ms
34944 KB
handmade6
AC
62 ms
34944 KB
maxrand0
RE
109 ms
34688 KB
maxrand1
AC
132 ms
34944 KB
maxrand2
AC
142 ms
35032 KB
maxrand3
AC
80 ms
34944 KB
maxrand4
RE
109 ms
34688 KB
rand0
AC
116 ms
34944 KB
rand1
RE
110 ms
34688 KB
rand2
RE
108 ms
34688 KB
rand3
RE
108 ms
34688 KB
rand4
RE
108 ms
34688 KB
small0
AC
16 ms
34688 KB
small1
AC
15 ms
34688 KB
small2
RE
108 ms
34688 KB
supersmall0
RE
108 ms
34688 KB
supersmall1
AC
14 ms
34688 KB
supersmall2
AC
15 ms
34688 KB