题目链接
前言
前置知识点：卢卡斯定理，威尔逊定理，不会可以百度，这里给出大概内容。
卢卡斯定理：考虑求 \(\binom{n}{k} \mod p\)。则其值等于 \(p\) 进制分解后的组合的乘积。
威尔逊定理：对于任意素数 \(p\)，有 \((p-1)! \equiv -1 \pmod p\)。
解法
考虑答案的情况为长度为 \(a_1\) 的环 \(k_1\) 个，\(a_2\) 的环 \(k_2\) 个，以此类推，直到 \(m\)，且满足 \(a_1 < a_2 < a_3 < \dots < a_n\)，同时还有 \(\sum\limits_{i=1}^{m} k_i = K\)。
则有答案为 \(\dfrac{n!}{\prod\limits_{i=1}^{m} {(a_i!)}^{k_i} k_i!} \prod\limits_{i=1}^{m} {(a_i-1)!}^{k_i}\)。化简一下，就是 \(\dfrac{n!}{\prod\limits_{i=1}^{m} {a_i}^{k_i} k_i!}\)。这是基础的。
然后看到模数很小，考虑对于模数下手。
由于 \(2005 = 5\times 401\)，所以做完 \(5\)，\(401\) 后，使用 CRT 就好了。
尝试开发性质。
性质一：\(a_m \le p\)。证明可以通过观察左侧内容得出。
性质二：\(\forall n \ge p,a_m = p\)，考虑 \(a_m < p\)，发现答案一定为 \(0\)。
性质三：考虑应用性质二，因此有：令 \(q = n/p\)，则 \(a_m = q\)，证明显然。
因此应用性质三。发现方案数为 \(\dbinom{n}{q\cdot p} \dfrac{\prod_{i=1}^{q}\binom{i\times p}{p}}{q!} \times {(p-1)!}^q\)。
考虑拆分这个式子，根据卢卡斯定理，可以得到前面一项 \(\equiv 1\)，根据威尔逊定理，最后一项 \(\equiv {(-1)}^q\)。
然后考虑第二项，不难拆分成 \(\dfrac{\prod_{i=1}^{q} i\cdot \binom{i\times p - 1}{p-1}}{q!}\)，然后变成了\(\prod_{i=1}^{q} \binom{i\times p - 1}{p-1}\)。考察这个式子，发现根据卢卡斯定理，同样等于 1。
综上，这一大坨式子，本质为 \({(-1)}^q\)。
然后，问题就可以转化到非常小的范围内了，可以 DP，不会的可以去问 DS，这里给出大概内容。
设 \(dp[i][j]\) 表示前 \(i\) 个人，形成了 \(j\) 个大小为 \(k\) 的圈，那么我们就有两种方案，往前面的圈塞东西，或者增加一个新的大小为 \(l\) 的圈。然后直接大力 DP，做完了。
Code
这里需要注意判数组越界，不然容易RE。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
const int N = 405;
LL n,k,l;
LL chs[N],dp[N][N];
LL DP(LL x,LL y,LL mod){memset(dp,0,sizeof dp);// cout << x << " " << y << " " << mod << "\n";for(int i=l;i<=x;i++){chs[i] = 1;for(int j=i-l+1;j<i;j++)chs[i] = chs[i] * j % mod;}dp[0][0] = 1;for(int i=1;i<=y;i++)for(int j=i*l;j<=x;j++){dp[i][j] = dp[i][j-1] * (j-1) + dp[i-1][j-l] * chs[j];dp[i][j] %= mod;}return dp[y][x];
}
LL solve(int p){if(l > p) return 0;if(l * k > n) return 0;int q = n / p;if(q > k) return 0;if((k - q) * l > n % p) return 0;LL res = DP(n%p,k-q,p);if(q & 1) res = (p -res)% p;return res;
}
int main(){IOS;cin >> n >> k >> l;LL ans1,ans2;ans1 = solve(5);ans2 = solve(401);// cout << ans1 << " " << ans2 << "\n";while(ans2 % 5 != ans1)ans2 += 401;ans2 %= 2005;cout << ans2;return 0;
}