求问:
  • 板块灌水区
  • 楼主WZwangchongming
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/2/7 21:00
  • 上次更新2025/2/8 09:33:21
查看原帖
求问:
933906
WZwangchongming楼主2025/2/7 21:00

代码片段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直接除竟然通过了一小部分数据

这俩有区别吗?

2025/2/7 21:00
加载中...