# 位元運算與快速冪
## 感受一下
[MDJudge T042《C++：從入門到放棄》](http://mdcpp.mingdao.edu.tw/problem/T042)
[TOI初選 原始人排序](http://mdcpp.mingdao.edu.tw/problem/T052)

## 進位法
### 十進位
就是平常我們熟悉的數字寫法
每個位數可能是0 1 2 3 4 5 6 7 8 9其中一個
當一個位數超過9就得進位
ex) $9+1=10$
個位塞不下了
所以進位到十位

### 二進位
==電腦的世界==
每個數僅由0 1組成
$(1)_{10}=(1)_2$
$(2)_{10}=(10)_2$

### 十六進位(補充)
==計算機領域的世界==
二進位的進化版
但比起二進位更不直觀
認識就好
數字由0 1 2 3 4 5 6 7 8 9 A B C D E F所組成
\
補充python code

## 進位法換算
### 個位與十位的意義
個位 顧名思義就是那個位數數字代表的值要乘1(也就是$10^0$)
十位的數字代表的值要乘10(也就是$10^1$)
以此類推

### 二進位轉十進位
:::spoiler {state="open"}舉個栗子
$(11001)_2=(?)_{10}$
$1*2^0+0*2^1+0*2^2+1*2^3+1*2^4=25$
:::

### 十進位轉二進位
:::spoiler {state="open"}舉個栗子
$(?)_2=(25)_{10}$
$25=1*2^0+0*2^1+0*2^2+1*2^3+1*2^4$
$?=11001$
:::

## 位元運算
:::success
C++裡 int是以二進位儲存的
因此宣告int a=25;
在內部記憶體會以11001來存
這就能解釋
為什麼位元運算比其他運算快很多
以及int的範圍是2^32
:::
假設$a=(25)_{10}=(011001)_2$
以及$b=(42)_{10}=(101010)_2$
方便後面解說

### & (and)
==25 & 42 = 8==
以二進制數來比較$a,b$
若該位數皆為$1$則結果也為$1$
否則為$0$

### | (or)
==25 | 42 = 59==
以二進制數來比較$a,b$
若該位數皆為$0$則結果也為$0$
否則為$1$

### ^ (xor)
==25 ^ 42 = 51==
以二進制數來比較$a,b$
若該位數數碼相同則結果為$0$
否則為$1$

### ! (not)
$!1=0$
$!0=1$

### >> 和 << (位移運算子 不是輸出輸入)
$a$>>$n$代表$a$右移$n$個bits
即$a=[a/2^n]$
$a$<<$n$代表$a$左移$n$個bits
即$a=a*2^n$

## 快速冪
**求$123^{25}=?$**
慢慢乘?
也是可以

再快一點?
> $a^{25}=a^1*a^8*a^{16}$-------<１>

把25轉成二進制分解
數值是1就乘進去

不太明白?
把$(11001)_2$跟<１>比較一下

### code

int fpow(int a, int k){
    int base = a, ans = 1;
    while(k){
        if(k&1)ans*=base;
        base*=base;
        k>>1;
    }
    return ans;
}

### 大數...?
大家都知道指數成長爆炸快
該不會求這東西都要用大數運算?

### 取模
通常這一類題目都會要你求除以某數後的餘數
所以...

[請接著服用:同餘](https://hackmd.io/O6Qm7k06TU22sajD5PN25A?both)

###### tags: `MDCPP` `Cosmos`

note:矩陣快速冪模板

#include<bits/stdc++.h>
#define loli ios::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define int long long
#define mod 1000000007
using namespace std;
struct mat{
	int m[101][101];
};
mat init(int n);
mat mul(mat a,mat b,int n);
mat fpow(mat a,int b,int n);
mat a,e;//a:輸入 e:單位矩陣
int n;//矩陣長度 (每行n個數 )
using namespace std;
signed main(){
    loli

	mat a;
	int k;
	cin>>k;
	if(k<2)cout<<k;
	else{
		n=2;
		a.m[0][0]=1;a.m[0][1]=1;a.m[1][0]=1;a.m[1][1]=0;
		for(int i=0;i<n;i++)e.m[i][i]=1;
		mat out=fpow(a,k,n);
		
		cout<<out.m[0][1]%mod;	
	}
    return 0;
}

mat init(int n){
	mat z;
	for(int i=0;i<n;i++)for(int j=0;j<n;j++)z.m[i][j]=0;
	return z;
}

mat mul(mat a, mat b, int n){
	mat Multi=init(n);
	for(int i=0;i<n;i++){//from A第一橫排 
		for(int j=0;j<n;j++){//from B第一直排 
			for(int k=0;k<n;k++){//第k元素 
				Multi.m[i][j]+=a.m[i][k]*b.m[k][j];
				Multi.m[i][j]%=mod;
			}
		}
	}
	return Multi;
}

mat fpow(mat a, int b, int n){
	mat power=a,ans=e;
	while(b){
		if(b&1)ans=mul(ans,a,n);
		a=mul(a,a,n);
		b/=2;
	}
	return ans;
}