JZOJ 3481. 【NOIP2013模拟10.23】君と彼女の恋（DP+组合数）

JZOJ 3481. 【NOIP2013模拟10.23】君と彼女の恋

题目大意

• 给定$N,M$，求不同的序列数使得序列所有数之和为$M$，且两两在除以$M$后余数互不相同。
• N ≤ 1 0 18 N\le 10^{18} N≤1018，$M\le 100$.

题解

• 暴力可以考虑把$\mathrm{m}\mathrm{o}\mathrm{d}M$的取值状压，设 f i , j f_{i,j} fi,j​表示选的数和为$i$，$\mathrm{m}\mathrm{o}\mathrm{d}M$是否出现过的状态为$j$的方案数，转移显然，最后答案要乘个数的阶乘。
• 但这样复杂度不能接受，由于$N$特别大，但$M$较小，DP时可以只算$[0,m)$中的数，再把剩余部分用组合数计算上，
• 这样一来，不需要记录状态，因为这个范围内它们除以$M$的余数本身就互不相同，只需设 f i , j f_{i,j} fi,j​表示和为$i$，选了$j$个数的方案数，转移也显然。
• 至于最后怎么计算，首先需要满足$M|N-i$才能是一种合法的答案，还需要把 N − i M \frac{N-i}{M} MN−i​个$M$分配给$j$个数，用挡板法求得方案数为 ( N − i M + j − 1 j − 1 ) \frac{N-i}{M}+j-1\choose {j - 1} (j−1MN−i​+j−1​)，当然也还要乘上$j!$。

代码

#include
#include
#include
using namespace std;
#define md 905229641
#define ll long long
#define M 110
ll 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("%lld\n", ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！