Problem A. 最近公共祖先 (commonants.c/cpp/pas)
注意
Input file: commonants.in
Output file: commonants.out
Time Limit : 0.5 seconds
Memory Limit: 512 megabytes
題面
最近公共祖先\(\text{(Lowest Common Ancestor,LCA)}\)是指在一個樹中同時擁有給定的兩個點作為后
代的最深的節點，
為了學習最近公共祖先，你得到了一個層數為\(n+1\)的滿二叉樹，其中根節點的深度為\(0\)，其他節點的深度為父節點的深度\(+1\)，你需要求出二叉樹上所有點對 \(\texttt{(i,j)}\),（\(i\),\(j\)可以相等，也可以\(i > j\)）的最近公共祖先的深度之和對\(10^9+7\)取模后的結果，
輸入格式
一行一個整數\(n\)，
輸出格式
一行一個整數表示所有點對 \(\texttt{(i,j)}\),（\(i\),\(j\)可以相等，也可以\(i > j\)）的最近公共祖先的深度之和對\(10^9+7\)取模后的結果，
樣例
\(\texttt{input\#1}\)
2
\(\texttt{input\#2}\)
19260817
\(\texttt{output\#1}\)
22
\(\texttt{output\#2}\)
108973412
資料范圍與提示
樣例\(1\)解釋：
樹一共有\(7\)個節點（一個根節點和兩個子節點），其中 \(\texttt{(4,4),(5,5),(6,6),(7,7)}\) 共\(4\)對的最近公共祖先深度為\(2\)，\(\texttt{(4,2),(2,4),(5,2),(2,5),(5,4),(4,5),(2,2),(6,3),(3,6),(3,7),(7,3),(6,7),}\)\(\texttt{(7,6),(3,3)}\)共\(14\)對最近公共祖先深度是\(1\)，其他的點對最近公共祖先深度為\(0\)，所以答案為\(22\)，
對于\(20%\)的資料，\(n \le 10\)，
對于\(50%\)的資料，\(n \le 10^6\) ，
對于\(100%\)的資料，\(1 \le n \le 10^9\) ，
題解
對于一顆有\(n\)層的滿二叉樹很顯然符合以下幾點
1.第\(i\)層的點的個數為\(2^i\)，
2.以第\(i\)層的點為根節點的子樹大小為\(2^{n-i+1}-1\)，
3.以第\(i\)層的點為\(\text{LCA}\)的點對個數為\(2^{2n-i+1}-2^i\)
觀察上面的圖（好丑）,很明顯\(1,2\)都是對的，
對于一顆以第\(i\)層的節點為根的子樹：
①它的左子樹與右子樹上的點的\(\text{LCA}\)都為根節點，所以點對個數為
②這棵子樹的左子樹與根節點的\(\text{LCA}\)都為根節點，右子樹也是，所以有\(2^{n-i+1}-2\)對點，
③根節點與根節點的\(\text{LCA}\)也是根節點，點對個數為1，
點對\(\texttt{(u,v)}\)與點對\(\texttt{(v,u)}\)在\(u \neq v\)時是兩個不同的點對，
所以將上述①②相加乘二再加③就是以子樹根節點為\(\text{LCA}\)的點對的數量為：
因為第\(i\)層的點的個數為\(2^i\)，所以以第\(i\)層的點為\(\text{LCA}\)的點對個數為：
\[\LARGE 2^{2n-i+1}-2^i \]因為一共有\(n+1\)層，從\(0-n\)層，所以答案為：
\[\LARGE \sum_{i=0}^{n} (2^{2n-i+1}-2^i) \times i \]\[\LARGE =\sum_{i=0}^{n} i \times 2^{2n-i+1}-i \times 2^i \]但這樣復雜度為\(\Theta (nlog_n)\)過不了，，將上面的式子展開：
\[\LARGE \sum_{i=0}^{n} i \times 2^{2n-i+1} - \sum_{i=0}^{n} i \times 2^i \]\[\LARGE T_n=\sum_{i=0}^{n} i \times 2^{2n-i+1} \]\[\LARGE =2^{2n} + 2 \times 2^{2n-1} + 3 \times 2^{2n-2}+...+n \times 2^{n+1} \]\[\LARGE 2T_n=2^{2n+1} + 2 \times 2^{2n} + 3 \times 2^{2n-1}+...+n \times 2^{n+2} \]\[\Large 2T_n-T_n=2^{2n+1} + 2^{2n} + 2^{2n-1}+...+2^{n+2} - n \times 2^{n+1} \]\[\LARGE T_n=2^{2n+1} + 2^{2n} + 2^{2n-1}+...+2^{n+2} - n \times 2^{n+1} \]很明顯前\(n\)項為等比數列，利用等比數列求和公式可以很快求出，
\[\LARGE T_n=\sum_{i=0}^{n} i \times 2^i \]\[\LARGE =2 + 2 \times 2^2 + 3 \times 2^3 +...+ n \times 2^n \]\[\LARGE 2T_n=2^2 + 2 \times 2^3 + 3 \times 2^4 + ... + n \times 2^{n+1} \]\[\LARGE T_n-2T_n=2 + 2^2 + 2^3 +...+2^n- n \times 2^{n+1} \]很明顯也是等比數列，將這兩個相加就是答案了，
快速冪是\(log\)，所以復雜度是\(\Theta(log_n)\)
\(Code\)
#include<bits/stdc++.h>
typedef long long ll;
ll n;
const ll mod=1000000007;
inline void read(ll &T) {
ll x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
inline ll qpow(ll a,ll b) {
ll ans=1,base=a;
while(b) {
if(b&1) ans=(ans*base)%mod;
base=(base*base)%mod;
b>>=1;
}
return ans%mod;
}
int main() {
read(n);
ll qwq=(((2*qpow(2,2*n+1))%mod-qpow(2,n+2)+5*mod)%mod-n*qpow(2,n+1)+5*mod)%mod;
ll qaq=((((2*qpow(2,n))%mod)-2+5*mod)%mod-n*qpow(2,n+1)+5*mod)%mod;
//std::cout<<qwq<<'\n'<<qaq<<'\n';
std::cout<<(qwq+qaq+5*mod)%mod;//加上一個模數再取模是為了處理負數的情況
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/98171.html
標籤：C++
上一篇：笛卡爾積簡單輸出