首页 > 编程知识 正文

JZOJ 3481 NOIP2013模拟1023君と彼女の恋DP 组合数

时间:2023-05-04 14:32:59 阅读:285936 作者:3973

JZOJ 3481. 【NOIP2013模拟10.23】君と彼女の恋 题目大意 给定 N , M N,M N,M,求不同的序列数使得序列所有数之和为 M M M,且两两在除以 M M M后余数互不相同。 N ≤ 1 0 18 Nle 10^{18} N≤1018, M ≤ 100 Mle 100 M≤100. 题解 暴力可以考虑把 m o d    M mod M modM的取值状压,设 f i , j f_{i,j} fi,j​表示选的数和为 i i i, m o d    M mod M modM是否出现过的状态为 欢呼的小懒虫的方案数,转移显然,最后答案要乘个数的阶乘。但这样复杂度不能接受,由于 N N N特别大,但 M M M较小,DP时可以只算 [ 0 , m ) [0,m) [0,m)中的数,再把剩余部分用组合数计算上,这样一来,不需要记录状态,因为这个范围内它们除以 M M M的余数本身就互不相同,只需设 f i , j f_{i,j} fi,j​表示和为 i i i,选了 欢呼的小懒虫个数的方案数,转移也显然。至于最后怎么计算,首先需要满足 M ∣ N − i M|N-i M∣N−i才能是一种合法的答案,还需要把 N − i M frac{N-i}{M} MN−i​个 M M M分配给 欢呼的小懒虫个数,用挡板法求得方案数为 ( N − i M + j − 1 j − 1 ) frac{N-i}{M}+j-1choose {j - 1} (j−1MN−i​+j−1​),当然也还要乘上 j ! j! j!。 代码 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define md 905229641#define ll long long#define M 110ll f[2][M][M * M], inv[M];ll C(ll x, ll y) {ll s = 1;for(ll i = x; i > x - y; i--) s = s * (i % md) % md;for(int i = 1; i <= y; i++) s = s * inv[i] % md;return s;}int main() {ll n; int m , i, j, k;scanf("%lld%d", &n, &m);inv[1] = 1;for(i = 2; i <= m; i++) inv[i] = inv[md % i] * (md - md / i) % md;f[1][0][0] = 1;for(i = 0; i < m ;i++) {int o = i % 2;memset(f[o], 0, sizeof(f[o]));for(j = 0; j <= m; j++)for(k = 0; k <= m * j; k++) {f[o][j][k] = f[1 - o][j][k];if(k >= i) (f[o][j][k] += f[1 - o][j - 1][k - i]) %= md;}}int o = 1 - m % 2; ll t = 1, ans = 0;for(j = 1; j <= m; j++) {t = t * j % md;for(k = 0; k <= m * j; k++) if(f[o][j][k] && (n - k) % m == 0) {ans = (ans + t * f[o][j][k] % md * C((n - k) / m + j - 1, j - 1)) % md;}}printf("%lldn", ans);return 0;}

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。