清北学堂培训2019.4.4
生活随笔
收集整理的這篇文章主要介紹了
清北学堂培训2019.4.4
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
第一次培訓，心情有點激動（盡管沒了清明節(jié)），還見到了各地的dalao們，十分開森
Day 1（李昊dalao）
上午篇
上午呢，主要講了關于高精，快速冪，膜模意義下的運算，篩素數(shù)，費馬小定理以及歐拉定理，歐拉函數(shù)。。。
我印象最深刻的，便是dalao的c++必備head（頭文件及各種令人窒息的define）
?讓人頭腦一熱QAQ
高精度（先全部考慮非負數(shù)）
高精度主要分為以下幾個部分
1.高精度加法:
思路：模擬豎式運算
注意：進位
優(yōu)化：壓位
2.高精度減法：
思路：同加法相似，模擬豎式運算，進位變?yōu)橥宋?/p>
注意：結果為負數(shù)的情況
?
3.高精乘
思路：類似，模擬豎式運算，考慮進位
注意：結果為0的情況
4.高精除以單精（高精除以高精在日常并不常用）
至于負數(shù)的情況呢QAQ
加法：
?一個數(shù)是負數(shù)：變?yōu)闇p法 ?兩個數(shù)是負數(shù)：全部變?yōu)檎龜?shù)算加法，最后取負減法：
?被減數(shù)是負數(shù)：全部變?yōu)檎龜?shù)算加法，最后取負 ?減數(shù)是負數(shù)：減數(shù)取負，變?yōu)榧臃?/span> ?都是負數(shù)：都取負，變?yōu)闇p法，即（-減數(shù)）-（-被減數(shù)）乘法：
?統(tǒng)計負數(shù)個數(shù)s ?都變?yōu)榉秦摂?shù)計算，若s為奇數(shù)，最后取負除法同理。。。
膜模意義下的運算
這一個就聽得十分有意思（畢竟我提前了解了一下）
這里需注意：無除法運算（很容易遺忘）
性質：
?滿足基本的交換律、分配率、結合律 ?對中間結果取模不影響最終答案快速冪：
1.分治
int calc(int a,int b,int c) {if(b==1){return a;}int tmp=calc(a,b/2,c);tmp=tmp*tmp%c;if(b&1){tmp=tmp*a%c;}return tmp; }2.快速冪
int ans=1; while(b) {if(b&1){ans=ans*a%c;}a=a*a%c;b/=2; }類似于這樣的操作
費馬小定理/歐拉定理
在模意義下有這個東西：
?C(n, m) = n! / ( (n-m)! * m! ) ????????????? = n! * ( (n-m)! * m! )^(p-2)顯然二者有推廣關系
篩法
前面講過，這里就不一一贅述
歐拉函數(shù)
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pr; const double pi=acos(-1); #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Rep(i,u) for(int i=head[u];i;i=Next[i]) #define clr(a) memset(a,0,sizeof a) #define pb push_back #define mp make_pair #define fi first #define sc second ld eps=1e-9; ll pp=1000000007; ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;} ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;} ll read(){ll ans=0;char last=' ',ch=getchar();while(ch<'0' || ch>'9')last=ch,ch=getchar();while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();if(last=='-')ans=-ans;return ans; } //head #define N 110000 bool p[N]; int prime[N],tot=0,rec[N],phi[N]; int main(){clr(p);rep(i,2,100000){if(!p[i]){prime[++tot]=i;rec[i]=i;}for(int j=1;j<=tot && prime[j]*i<=100000;j++){p[prime[j]*i]=1;rec[prime[j]*i]=prime[j];if(i%prime[j]==0)break;}}rep(i,2,100000)if(rec[i]==i)phi[i]=i-1;elseif(i%(rec[i]*rec[i])==0)phi[i]=phi[i/rec[i]]*rec[i];else phi[i]=phi[i/rec[i]]*(rec[i]-1);rep(i,2,20)printf("%d : %d\n",i,phi[i]); }李昊大佬的碼風有些清奇qwq
下午篇
?蒟矩陣
such as：
特殊矩陣：
1.上三角矩陣
2.分塊矩陣
3.對角矩陣
4.對稱矩陣
行列式
?
?需要學一下逆序對（皮一下很舒服）
可以學一下這本書@工程數(shù)學線性代數(shù)
矩陣逆元
說到逆元，以下是洛谷P3811求乘法逆元的正解
#include<bits/stdc++.h> using namespace std; int n,p,inv[25000528]; int main() {scanf("%d%d",&n,&p);inv[1]=1;for(int i=2;i<=n;i++){inv[i]=(long long)(p-p/i)*inv[p%i]%p; }for(int i=1;i<=n;i++){printf("%d\n",inv[i]);}return 0; }?還講了一堆十分神奇的東西：
矩陣樹定理
?一個圖的鄰接矩陣G：對于無向圖的邊(u,v)，G[u][v]++,G[v][u]++ ?一個圖的度數(shù)矩陣D：對于無向圖的邊(u,v)，D[u][u]++,D[v][v]++ ?而通過這兩個矩陣就可以構造出圖G的基爾霍夫矩陣：C=D-G. ?Matrix Tree定理：將圖G的基爾霍夫矩陣去掉第i行和第i列(i可以取任意值，可以證明所得到的結果相同)，得到(n-1)*(n-1)的矩陣，對這個矩陣進行行列式的值求解，abs(det(A))即為圖G的生成樹個數(shù)。讓人十分慌張。。。
有向圖 - 矩陣樹定理
?樹形圖：以i點為根節(jié)點的樹形圖有(n-1)條邊，從i節(jié)點出發(fā)可以到達其他所有(n-1)個節(jié)點. ?定義： 有向圖的鄰接矩陣G：對于有向圖的邊(u,v)，G[u][v]++. ?有向圖的度數(shù)矩陣D：對于有向圖的邊(u,v)，D[v][v]++. ?尤其需要注意的是：有向圖的度數(shù)矩陣指的是一個點的入度，而不是出度。 ?而有向圖的基爾霍夫矩陣的構造方式是一模一樣的：C=D-G. ?有向圖Matrix Tree定理： ?將有向圖G的基爾霍夫矩陣去掉第i行和第i列，得到(n-1)*(n-1)的矩陣，對這個矩陣進行行列式的值求解，abs(det(A))就是以i為根的樹形圖的個數(shù)。讓人更加慌張。。。
so：這一下午就在慌張中過去了QAQ
之后還會有題目的整理鴨！！！
?
轉載于:https://www.cnblogs.com/gongcheng456/p/10656667.html
總結
以上是生活随笔為你收集整理的清北学堂培训2019.4.4的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Google 修改 Chrome API
- 下一篇： 2019年春季学期第九周作业