中山皇冠建设开发有限公司网站,wordpress电话按钮,一键生成各种app软件,WORDPRESS免费中国主题https://www.luogu.org/problemnew/show/P2181 对于某条对角线#xff0c;除去从两端出发的对角线#xff0c;其他的都与它有1个交点。 每个点有(n-3)条对角线#xff0c;每条对角线和其余C(n-2,2)条对角线都有1个交点#xff0c;共有n个点#xff0c;重复计算交点再除以2…https://www.luogu.org/problemnew/show/P2181 对于某条对角线除去从两端出发的对角线其他的都与它有1个交点。 每个点有(n-3)条对角线每条对角线和其余C(n-2,2)条对角线都有1个交点共有n个点重复计算交点再除以2重复计算直线再除以2。 即n(n-3)/2条对角线每条对角线和(n-2)(n-3)/2条对角线都有1个交点重复计算交点再除以2。错了并非所有对角线都相交 画图手数按规律数的话发现n41个交点n55个交点sum(1,2)2sum(1,1)n615个交点sum(1,3)2sum(1,2)3sum(1,1)n735个交点sum(1,4)2sum(1,3)3sum(1,2)4sum(1,1)。 所以我们首先得到一个n复杂度的解法。利用这个解法打表看看。 #includebits/stdc.h
using namespace std;
#define ll long longll sum(ll a1,ll an){return (an-a11)*(a1an)/2;
}int main(){for(int n3;n20;n){ll ans0;for(int i1;in-3;i){ans1ll*i*sum(1,n-2-i);}printf(n%d ans%lld\n,n,ans);}} n3 ans0
n4 ans1
n5 ans5
n6 ans15
n7 ans35
n8 ans70
n9 ans126
n10 ans210
n11 ans330
n12 ans495
n13 ans715
n14 ans1001
n15 ans1365
n16 ans1820
n17 ans2380
n18 ans3060
n19 ans3876
n20 ans4845 再试试大点的会不会爆结果看不太出来用ull和ll的结果没啥不同赌他不溢出。 #includebits/stdc.h
using namespace std;
#define ll long longunsigned ll sum(ll a1,ll an){return (an-a11)*(a1an)/2;
}int main(){int n;scanf(%d,n);//for(int n99999;n100000;n){unsigned ll ans0;for(int i1;in-3;i){ans1llu*i*sum(1,n-2-i);}//printf(n%d ans%llu\n,n,ans);printf(%llu\n,ans);//}} 事实证明是没有溢出。所以上面是正确的解法。 这道题还有用公式的解法降低了一个维度。除了用组合数学的知识直接得到4个不同的点确定一个交点直接C(n,4)还可以暴力求解这里介绍一下高阶差分。 首先我们由打表代码得到 0 1 5 15 35 70 126 一阶差分 1 4 10 20 35 56 二阶差分 3 6 10 15 21 三阶差分 3 4 5 6 四阶差分 1 1 1 五阶差分 0 0 所以上式是一个关于n的四次多项式。设为an^4bn^3cn^2dne0。 代入前5项强行算出来吧。还是说有别的计算方法 的确有差分数列只要得到等差数列即可 写出差分表之后差分表的每行第0项组成第0对角线即c0,c1,c2,c3,0,0,0...。原序列的通项满足 hnc0C(n,0)c1C(n,1)c2C(n,2)c3C(n,3)利用这个形式甚至可以求出前n项和。组合数的求和sum(k0~n,C(k,p))C(k1,p1) 参考https://blog.csdn.net/wu_tongtong/article/details/79115921 转载于:https://www.cnblogs.com/Yinku/p/10328616.html
