代码片段1:
void chk(int k, int c[]) {
if(fl[k]) {
if(n == k) {
int tot = 0;
for(int j = 1; j <= k; j++) {
int t1 = c[j] % m;
tot += t1 * j * j;
}
ans = tot % m;
}
fl[k] = 0;
}
}
void mian() {
int l1[L] = {0}, l2[L] = {0}, C[L] = {0};
int *cur = l1, *nxt = l2;
cur[1] = 1;
chk(1, cur);
for(int i = 2; i < L; i++) {
int tot = 0;
for(int j = 1; j < i; j++) C[j] = cur[j] * (i - 1) * inv[j], tot += C[j];
for(int j = 1; j <= i; j++) nxt[j] = cur[j - 1] + tot, tot -= C[j];
swap(cur, nxt);
chk(i, cur);
}
}
signed main() {
n = read();
m = read();
fl[n] = 1;
inv[1] = 1;
for(int i = 2; i < L; i++)
inv[i] = (int)(m - m / i) * inv[m % i] % m;
mian();
// printf("%lld\n", ans);
writeln(ans);
return 0;
}
代码片段2:
void mian() {
int l1[L] = {0}, l2[L] = {0}, C[L] = {0};
int *cur = l1, *nxt = l2;
cur[1] = 1;
chk(1, cur);
for(int i = 2; i < L; i++) {
int tot = 0;
for(int j = 1; j < i; j++) C[j] = cur[j] * (i - 1) / j, tot += C[j];
for(int j = 1; j <= i; j++) nxt[j] = cur[j - 1] + tot, tot -= C[j];
swap(cur, nxt);
chk(i, cur);
}
}
相较片段1,片段2的 *inv[j] 被替换为 /j。
而且,片段1的逆元写法全WA,片段2直接除竟然通过了一小部分数据
这俩有区别吗?