https://www.luogu.org/problemnew/show/P2181

對于某條對角線，除去從兩端出發(fā)的對角線，其他的都與它有1個(gè)交點(diǎn)。

每個(gè)點(diǎn)有(n-3)條對角線，每條對角線和其余C(n-2,2)條對角線都有1個(gè)交點(diǎn)，共有n個(gè)點(diǎn)，重復(fù)計(jì)算交點(diǎn)再除以2，重復(fù)計(jì)算直線再除以2。

即n(n-3)/2條對角線，每條對角線和(n-2)(n-3)/2條對角線都有1個(gè)交點(diǎn)，重復(fù)計(jì)算交點(diǎn)再除以2。（錯(cuò)了，并非所有對角線都相交）

---

畫圖手?jǐn)?shù)，按規(guī)律數(shù)的話，發(fā)現(xiàn)n=4，1個(gè)交點(diǎn)；n=5，5個(gè)交點(diǎn)=sum(1,2)+2sum(1,1)；n=6，15個(gè)交點(diǎn)=sum(1,3)+2sum(1,2)+3sum(1,1)；n=7，35個(gè)交點(diǎn)=sum(1,4)+2sum(1,3)+3sum(1,2)+4sum(1,1)。

所以我們首先得到一個(gè)n復(fù)雜度的解法。利用這個(gè)解法打表看看。

#include<bits/stdc++.h> using namespace std; #define ll long longll sum(ll a1,ll an){return (an-a1+1)*(a1+an)/2; }int main(){for(int n=3;n<=20;n++){ll ans=0;for(int i=1;i<=n-3;i++){ans+=1ll*i*sum(1,n-2-i);}printf("n=%d ans=%lld\n",n,ans);}} n=3 ans=0 n=4 ans=1 n=5 ans=5 n=6 ans=15 n=7 ans=35 n=8 ans=70 n=9 ans=126 n=10 ans=210 n=11 ans=330 n=12 ans=495 n=13 ans=715 n=14 ans=1001 n=15 ans=1365 n=16 ans=1820 n=17 ans=2380 n=18 ans=3060 n=19 ans=3876 n=20 ans=4845

再試試大點(diǎn)的會不會爆，結(jié)果看不太出來，用ull和ll的結(jié)果沒啥不同，賭他不溢出。

#include<bits/stdc++.h> using namespace std; #define ll long longunsigned ll sum(ll a1,ll an){return (an-a1+1)*(a1+an)/2; }int main(){int n;scanf("%d",&n);//for(int n=99999;n<=100000;n++){unsigned ll ans=0;for(int i=1;i<=n-3;i++){ans+=1llu*i*sum(1,n-2-i);}//printf("n=%d ans=%llu\n",n,ans);printf("%llu\n",ans);//} }

事實(shí)證明是沒有溢出。所以上面是正確的解法。

這道題還有用公式的解法，降低了一個(gè)維度。除了用組合數(shù)學(xué)的知識直接得到（4個(gè)不同的點(diǎn)確定一個(gè)交點(diǎn)，直接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

所以上式是一個(gè)關(guān)于n的四次多項(xiàng)式。設(shè)為an^4+bn^3+cn^2+dn+e=0。

代入前5項(xiàng)強(qiáng)行算出來吧。還是說有別的計(jì)算方法？

的確有！（差分?jǐn)?shù)列只要得到等差數(shù)列即可）

寫出差分表之后，差分表的每行第0項(xiàng)組成第0對角線，即c0,c1,c2,c3,0,0,0...。原序列的通項(xiàng)滿足

hn=c0C(n,0)+c1C(n,1)+c2C(n,2)+c3C(n,3)，利用這個(gè)形式甚至可以求出前n項(xiàng)和。（組合數(shù)的求和sum(k=0~n,C(k,p))=C(k+1,p+1)）

---

參考https://blog.csdn.net/wu_tongtong/article/details/79115921

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yinku/p/10328616.html

總結(jié)

以上是生活随笔為你收集整理的洛谷 - P2181 - 对角线 - 打表 - 组合数学的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。