题解归档 - cf220D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf220D
• 本地来源：problems/cf220D/idea.md
• 题目链接：https://codeforces.com/contest/220/problem/D
• 原始标题：220D Little Elephant and Triangle

思路

220D Little Elephant and Triangle

题意

网格 [0,w]×[0,h] 上共有 (w+1)(h+1) 个整点。求有序三元组 (P1,P2,P3) 的个数，使得三点不共线且三角形面积为正整数（等价于叉积为偶且非零）。答案对 1e9+7 取模。

思路

1. 总方案减去非法

有序互异三点共 N(N-1)(N-2)，N=(w+1)(h+1)。

• 共线：枚举每条极大格点直线（水平/竖直/斜率 a:b 且 gcd(a,b)=1），若线上有 L 个点，贡献 L(L-1)(L-2)。实现上对方向 (a,b) 按 canonical 起点分块，用 v 分组聚合 y 方向，再减去 u 方向上的剩余 x 区间。
• 半整数面积（叉积为奇）：按四点奇偶 (x%2,y%2) 分类计数，枚举 64 种奇偶组合，用行列式奇偶判定。

答案：N(N-1)(N-2) - collinear - odd_area。

2. 复杂度

外层 a,b 互质且 min(w/a,h/b)≥2；内层按 v 块 O(h/b)，均摊后约 O(wh log max(w,h))，4000 规模在 C++ -O3 下约 1–2 分钟（本地 WSL）；小数据与 brute 一致。

样例

• 2 1 → 36
• 2 2 → 240
• 10 10 → 1032528

参考

Codeforces Round #136 Editorial (220D)

代码

来源：problems/cf220D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:05:41
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=1000000007;
ll cx[2],cy[2],n[4],w,h,i,j,k,a,b,x,y,zc,pd,cur,ans,col,odd,N,u,v,xl,xr,xhi,cnt;
ll f(ll L){
    if(L<3) return 0;
    return L*(L-1)%mod*(L-2)%mod;
}
void add(ll &s,ll v){
    s=(s+v)%mod;
}
void add_part2_up(ll a,ll b){
    for(v=0;(v+1)*b<=h+b;v++){
        xl=max(0LL,h-(v+1)*b+1);
        xr=min(b-1,h-v*b);
        cnt=max(0LL,xr-xl+1);
        if(cnt==0) continue;
        xhi=min(w,w-a*v);
        if(xhi>=a) add(col,cnt%mod*((xhi-a+1)%mod)%mod*f(1+v)%mod);
        for(u=0;u<v;u++){
            xl=max(a,w-a*(u+1)+1);
            xr=min(w,w-a*u);
            if(xl<=xr){
                xl=max(xl,xhi+1);
                if(xl<=xr) add(col,cnt%mod*((xr-xl+1)%mod)%mod*f(1+u)%mod);
            }
        }
    }
}
void add_part2_dn(ll a,ll b){
    for(v=0;v*b<=h;v++){
        xl=max(h-b+1,v*b);
        xr=min(h,(v+1)*b-1);
        cnt=max(0LL,xr-xl+1);
        if(cnt==0) continue;
        xhi=min(w,w-a*v);
        if(xhi>=a) add(col,cnt%mod*((xhi-a+1)%mod)%mod*f(1+v)%mod);
        for(u=0;u<v;u++){
            xl=max(a,w-a*(u+1)+1);
            xr=min(w,w-a*u);
            if(xl<=xr){
                xl=max(xl,xhi+1);
                if(xl<=xr) add(col,cnt%mod*((xr-xl+1)%mod)%mod*f(1+u)%mod);
            }
        }
    }
}
void add_up(ll a,ll b){
    for(v=0;v*b<=h;v++){
        cnt=min(b,h+1-v*b);
        xhi=min(a-1,w-a*v);
        if(xhi>=0) add(col,cnt%mod*((xhi+1)%mod)%mod*f(1+v)%mod);
        for(u=0;u<v;u++){
            xl=max(0LL,w-a*(u+1)+1);
            xr=min(a-1,w-a*u);
            if(xl<=xr){
                xl=max(xl,xhi+1);
                if(xl<=xr) add(col,cnt%mod*((xr-xl+1)%mod)%mod*f(1+u)%mod);
            }
        }
    }
    add_part2_up(a,b);
}
void add_dn(ll a,ll b){
    for(v=0;v*b<=h;v++){
        cnt=min(b,h+1-v*b);
        xhi=min(a-1,w-a*v);
        if(xhi>=0) add(col,cnt%mod*((xhi+1)%mod)%mod*f(1+v)%mod);
        for(u=0;u<v;u++){
            xl=max(0LL,w-a*(u+1)+1);
            xr=min(a-1,w-a*u);
            if(xl<=xr){
                xl=max(xl,xhi+1);
                if(xl<=xr) add(col,cnt%mod*((xr-xl+1)%mod)%mod*f(1+u)%mod);
            }
        }
    }
    add_part2_dn(a,b);
}
int main(){
    cin>>w>>h;
    cx[0]=w/2+1;
    cx[1]=w+1-cx[0];
    cy[0]=h/2+1;
    cy[1]=h+1-cy[0];
    for(i=0;i<4;i++) n[i]=cx[i/2]*cy[i%2];
    N=(w+1)*(h+1);
    odd=0;
    for(i=0;i<4;i++){
        for(j=0;j<4;j++){
            for(k=0;k<4;k++){
                pd=(i/2*(j%2-k%2)+i%2*(k/2-j/2)+j/2*k%2-k/2*j%2)&1;
                if(pd==1) odd=(odd+n[i]*n[j]%mod*n[k])%mod;
            }
        }
    }
    col=0;
    if(w+1>=3) add(col,(h+1)*f(w+1));
    if(h+1>=3) add(col,(w+1)*f(h+1));
    for(a=1;a<=w;a++){
        for(b=1;b<=h;b++){
            if(__gcd(a,b)!=1) continue;
            if(1+min(w/a,h/b)<3) continue;
            add_up(a,b);
            add_dn(a,b);
        }
    }
    ans=N%mod;
    ans=ans*(N-1)%mod*(N-2)%mod;
    ans=(ans+mod-col)%mod;
    ans=(ans+mod-odd)%mod;
    cout<<ans<<"\n";
    return 0;
}