擬二等辺三角形
题面翻译
定义一个三角形为“伪等腰三角形”需满足以下三个条件：
-
三边长度都为自然数。
-
三边长度各不相同。
-
有其中两条边的长度之差为 \(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;
}
Tips
-
\(10^{12}\) 的输入已经爆
int了，需要开long long。 -
记得特判 \(n\) 小于等于 \(8\) 的情况。