SP6408 KKKCT2 - Counting Triangles 2 题解

hzoi_Shadow · 2025-03-27 16:07:12 · 题解

题目传送门

前置知识

等差数列求和公式

解法

考虑枚举直角顶点 (i,j),0 \le i \le x,0 \le j \le y，然后分为了 8 种贡献情况。

设 \begin{cases} a=\min(i,y-j) \\ b=\min(x-i,j) \\ c=\min(i,j) \\ d=\min(x-i,y-j) \end{cases}，8 种情况的贡献分别为 a,d,b,c,ad,bd,ac,ad，加起来后得到 (a+b+1)(c+d+1)-1，但没有什么可以优化的地方。

观察乘积项，以 ac 为例，考虑固定 i 这个常量，统计 j 的贡献，分讨 0,y-j,j,y 划分成的三个区间内部的转移即可。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
using namespace std;
const ll p=2009;
ll s1(ll n)
{
    return n*(n+1)/2;
}
ll s2(ll n)
{
    return n*(n+1)*(2*n+1)/6;
}
ll ask(ll up,ll a,ll b)
{
    ll ans=0;
    ans+=s1(min(a,up))+max(0ll,(up-a))*a;//2e8
    ans+=s2(min(min(a,b)-1,up));//2e12
    if(min(min(a,b)-1,up)<min(max(a,b),up))
        ans+=(min(min(a,b)-1,up)+1+min(max(a,b),up))*(min(max(a,b),up)-min(min(a,b)-1,up))/2*min(a,b);//2e12
    ans+=max(0ll,(up-max(a,b)))*a*b;//1e12
    return ans;
}
int main()
{
// #define Isaac
#ifdef Isaac
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
#endif
    int t,x,y,i,j;
    ll ans;
    cin>>t;
    for(;t>=1;t--)
    {
        cin>>x>>y;  ans=0;
        // a=min(i,y-j),b=min(x-i,j),c=min(i,j),d=min(x-i,y-j)
        for(i=0;i<=x;i++)
        {
            ans+=ask(y,i,x-i);// bc+c
            ans+=ask(y,x-i,i);// ad+d
        }
        for(i=0;i<=y;i++)
        {
            ans+=ask(x,y-i,i);// ac+a
            ans+=ask(x,i,y-i);// bd+b
        }
        cout<<ans%p<<endl;
    }   
    return 0;
}