题解：擬二等辺三角形

naughty-naught / 2024-10-15 / 原文

Problem Link

擬二等辺三角形

题面翻译

定义一个三角形为“伪等腰三角形”需满足以下三个条件：

三边长度都为自然数。
三边长度各不相同。
有其中两条边的长度之差为 $1$。

现在给你一个数 $n$，求周长小于等于 $n$ 的“伪等腰三角形”个数，答案对 $1000000007$ 取模。

Solution

不难发现周长最小的“伪等腰三角形”的三边长为 $(2, 3, 4)$，故若给出的 $n$ 需大于 $8$。

锚定 $b = a+1$，对 $n$ 进行奇偶性讨论（令三角形表示为 $(a, b, c)$）。

$n$ 为偶数。

设 $res$ 为构成 $(2, 3, 3)$ 之后剩下的值（即 $n-8$），不难发现把余下的值对半任意放到 $(2, 3)$ 中即可，方案数即为（式子中的 $res$ 由前文已除以 $2$）:

\[ {res \times(res+1) \div 2} \]

$n$ 为奇数

设 $res$ 为构成 $(2, 3, 2)$ 之后剩下的值（即 $n-7$），与偶数类似，只是 $(2, 3)$ 中至少要放 $1$ 使得“三边长度各不相同”。

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define Mod 1000000007
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}

ll n;

ll hts(ll a, ll b)
{
    ll res = 1;
    while(b) 
    {
        if( b & 1 ) (res *= a) %= Mod;
        (a *= a) %= Mod, b >>= 1;
    }
    return res;
}

ll solve(ll n)
{
    if( n <= 8 ) return 0;
    if( (n & 1) == 0 ) {ll res = (n-8) / 2  % Mod; return res * ((res+1) % Mod) % Mod * hts(2, Mod-2) % Mod;}
    else {ll res = (n-7)/ 4 % Mod; return ( res * 2 % Mod * res % Mod + ((n-7)/2 & 1 ? res*2+1 : 0 ) % Mod) % Mod;}
}

int main()
{
    n = lread();
    printf("%lld\n", solve(n));
    return 0;
}