dw制作asp网站模板, 天堂资源地址在线下载,做个人的网站怎么做,常州营销推广公司题目 t(t1e6)组样例#xff0c;每次给定一个n(n1e9)#xff0c;统计边长为n的上述三角形的等边三角形个数
其中等边三角形的三个顶点#xff0c;可以在所有黑色三角形白色三角形的顶点中任取#xff0c;
答案对1e97取模
思路来源
申老师 oeis A0003…题目 t(t1e6)组样例每次给定一个n(n1e9)统计边长为n的上述三角形的等边三角形个数
其中等边三角形的三个顶点可以在所有黑色三角形白色三角形的顶点中任取
答案对1e97取模
思路来源
申老师 oeis A000332
Solution to Problem #3
题解 oeis打一下前四项的表发现是C(n,4)并且还有说明
是等于长度为n时的等边三角形任取顶点时不限边长大小的等边三角形个数
看了一下证明感觉也是变相计数这里提供一种计数方式可能赛中还是会选择打表吧
计数方式
对于边长为n的三角形三个点都在三角形的三条边上的方案恰有n种
图示分别对应n2,3,4的情形 所以可以枚举每个边长i统计边长i的正向的三角形的个数每个的贡献是i
因为倒立的边长为i的三角形会在正向为2*i的三角形中被枚举到所以忽略 归纳/找规律可发现边长为n-i1的正向三角形的出现次数是i*(i1)/2有下式成立 恒等式的组合意义
从n3个数选4个数时可以枚举第三个数的位置左边i1个位置选2个右边选1个
但是确实没有看出来其与三角形选择方法的关联关系
代码
输出C(n3,4)即可即(n3)*(n2)*(n1)*n/24
#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairint,int P;
#define fi first
#define se second
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define pb push_back
#define all(a) a.begin(),a.end()
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { std::uniform_int_distributionll dist(l, r); return dist(gen); }
const int mod1e97,inv2(mod1)/2,inv6(mod1)/6;
int t,n;
int sol(int x){int a1ll*(n3)*(n2)%mod*inv6%mod;int b1ll*(n1)*n%mod*inv2%mod*inv2%mod;return 1ll*a*b%mod;
}
int main(){sci(t);while(t--){sci(n);printf(%d\n,sol(n));}return 0;
}
