擬二等辺三角形

· · 题解

擬二等辺三角形

题面翻译

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

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

Solution

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

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

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

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

设 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;
}

Tips