Codeforces 215C - Crosses (枚舉幾何參數)

問題描述

（題目原文缺失，從代碼推測）在 n×m 網格中放置「十字」形狀，由參數 a,b,c,d 定義。枚舉 a,b,d 計算 c，統計合法放置數。答案對大數取模？

代碼邏輯分析

int qiu(int a,int b,int d) { // 根據 a,b,d 反推 c
    int ss = s;
    if(d >= b) {
        if(ss % d == 0 && ss/d >= a) return ss/d;
        ss -= a*b;
        if(d!=b && ss % (d-b) == 0) { int c = ss/(d-b); if(c<=a) return c; }
    } else {
        ss = ss - a*b + a*d;
        if(ss % d == 0) return ss/d;
    }
    return 0;
}
void dos(int a,int b,int c,int d) { // 一般情況計數
    int aa=max(a,c), bb=max(b,d);
    ans += (n-aa+1)*(m-bb+1);
}
void ffdos(int a,int b) { // 特殊情況
    ans += (n-a+1)*(m-b+1);
}
void fdos(int a,int b) { // 另一特殊情況
    ans += ((a+1)/2)*((b+1)/2)*(n-a+1)*(m-b+1);
}

枚舉主循環

for(i=1;i<=n;i+=2)
  for(j=1;j<=m;j+=2) {
    if(i*j > s) break;
    if(i*j == s) { fdos(i,j); continue; }
    for(k=1;k<=m;k+=2) {
        int c = qiu(i,j,k);
        if(!c || c>n || c%2==0) continue;
        if(c>=i && k>=j) ffdos(c,k);
        else dos(i,j,c,k);
    }
}

說明

代碼較為緊湊，缺乏題目上下文。核心思想：枚舉十字兩臂長度參數，通過幾何關係推導另一參數，按情況分類計數放置方式。需結合原題（CF 215C）理解具體幾何定義。