康托展开与康托展开逆运算
ll fac[20]; //阶乘
void getFac()
{
fac[0] = 1;
for(int i=1;i<20;i++)
fac[i] = 1LL * fac[i-1] * i;
}
ll cantor(int *a,int len) //康托展开求a是全排列第几项,a从1开始
{
ll ret = 0;
int vis[20] = {0};
for(int i=1;i<=len-1;i++)
{
ll tp = 0;
for(int j=1;j<a[i];j++)
if(!vis[j])
tp ++;
ret += 1LL * tp * fac[len - i];
vis[a[i]] = 1;
}
return ret + 1;
}
void _cantor(ll r,int len) //康托展开逆运算求第r个排列
{
r --;
int vis[20] = {0},a[20];
for(int i=1;i<=len;i++)
{
ll tp = r / fac[len - i];
r -= tp * fac[len - i];
int j;
for(j=1;j<=len;j++)
if(!vis[j])
{
if(tp == 0) break;
tp --;
}
vis[j] = 1;
a[i] = j;
}
for(int i=1;i<len;i++)
printf("%d ",a[i]);
printf("%d\n",a[len]);
}
Miller_Rabin大素数判断
ll prime[6] = {2, 3, 5, 233, 331};
ll qmul(ll x, ll y, ll mod) // 乘法防止溢出， 如果p * p不爆ll的话可以直接乘； O(1)乘法或者转化成二进制加法
{
return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}
ll qpow(ll a, ll n, ll mod)
{
ll ret = 1;
while(n) {
if(n & 1) ret = qmul(ret, a, mod);
a = qmul(a, a, mod);
n >>= 1;
}
return ret;
}
bool Miller_Rabin(ll p)
{
if(p < 2) return 0;
if(p != 2 && p % 2 == 0) return 0;
ll s = p - 1;
while(! (s & 1)) s >>= 1;
for(int i = 0; i < 5; ++i)
{
if(p == prime[i]) return 1;
ll t = s, m = qpow(prime[i], s, p);
while(t != p - 1 && m != 1 && m != p - 1) {
m = qmul(m, m, p);
t <<= 1;
}
if(m != p - 1 && !(t & 1)) return 0;
}
return 1;
}
扩展欧几里得解线性丢番图方程
解ax + by = c方程的x,y特解（a b无最大公约数的情况要特判）
当且仅当 c % gcd(a,b) == 0时方程有解
最小正整数解：r = b/d, x = ((x * c / d) % r + r) % r
ll extend_Euclid(ll a,ll b,ll &x,ll &y)
{
if(a == 0 && b == 0)return -1;
if(b == 0)
{
x = 1; y = 0; return a;
}
ll d = extend_Euclid(b, a % b, y, x);
y -= a / b * x;
return d;
}
Lucas定理求大组合数
求n,m很大的组合数对数p取模的值
1. p比较小的情况，预处理到p的阶乘，p必须是素数
int p;
ll fac[10010];
ll q_pow(ll a,ll b,ll mod)
{
ll r = 1, base = a % mod;
while(b)
{
if(b&1) r *= base;
base *= base;
b >>= 1;
}
return r;
}
void getFac()
{
fac[0] = 1;
for(int i=1; i<=p; i++)
{
fac[i] = (fac[i - 1] * i) % p;
}
}
ll Lucas(ll n,ll m)
{
ll ret = 1;
while(n && m)
{
ll a = n % p, b = m % p;
if(a < b) return 0;
ret = (ret * fac[a] * q_pow(fac[b] * fac[a-b] % p, p - 2)) % p;
n /= p;
m /= p;
}
return ret;
}
2. p较大的情况，p必须是素数
ll C(ll n, ll m, ll p)
{
if(m > n) return 0;
ll ans = 1;
for(int i=1; i<=m; i++)
{
ll a = (n + i - m) % p;
ll b = i % p;
ans = ans * (a * q_pow(b, p-2, p) % p) % p;
}
return ans;
}
ll Lucas(ll n, ll m, ll p)
{
if(m == 0) return 1;
return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
}
3. p可以是合数，且p < 1e5, n m < 1e6
const int N = 200005;// int范围内的mod都能处理
bool prime[N];
int p[N];
int cnt; // p数组储存素数
void getprime()
{
cnt = 0;
memset(prime,true,sizeof(prime));
for(int i=2; i<N; i++)
{
if(prime[i])
{
p[cnt++] = i;
for(int j=i+i; j<N; j+=i)
prime[j] = false;
}
}
}
ll Work(ll n,ll p)
{
ll ans = 0;
while(n)
{
ans += n / p;
n /= p;
}
return ans;
}
ll Solve(ll n,ll m,ll P)
{
ll ans = 1;
for(int i=0; i<cnt && p[i]<=n; i++)
{
ll x = Work(n, p[i]);
ll y = Work(n - m, p[i]);
ll z = Work(m, p[i]);
x -= (y + z);
ans *= q_pow(p[i],x,P);
ans %= P;
}
return ans;
}
矩阵快速幂
struct matrix{
ll a[3][3];
int h,w;
matrix(int _h,int _w):h(_h),w(_w){
a[0][0] = 1; a[0][1] = 0; a[0][2] = 1;
a[1][0] = 0; a[1][1] = 0; a[1][2] = 1;
a[2][0] = 0; a[2][1] = 1; a[2][2] = 1;
}
matrix operator * (const matrix &r) const{
matrix ret(h,r.w);
for(int i=0;i<h;i++)
for(int j=0;j<r.w;j++)
{
ret.a[i][j] = 0;
for(int k=0;k<w;k++)
ret.a[i][j] = (ret.a[i][j] + a[i][k] * r.a[k][j] % mod) % mod;
}
return ret;
}
matrix operator + (const matrix &r) const{
matrix ret(h,w);
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
ret.a[i][j] = (a[i][j] + r.a[i][j]) % mod;
return ret;
}
};
matrix matrix_pow(matrix p,int b)
{
matrix r(p.h,p.w);
memset(r.a, 0, sizeof r.a);
for(int i=0;i<3;i++) r.a[i][i] = 1;
/* 设置r为单位矩阵 */
matrix base = p;
while(b)
{
if(b&1) r = r * base;
base = base * base;
b >>= 1;
}
return r;
}
对整数n进行因数分解
1. 求n不同正因子个数
设n = p1^a1 * p2^a2 *...* pn^an; 即将n质分解
则count(n) = (a1 + 1)*(a2 + 1) *...*(an + 1)
int count(int n)
{
int ret = 1;
for(int i = 0; p[i] <= n; i++)// p数组储存素数
if(n % p[i] == 0)
{
int tmp = 0;
while(n % p[i] == 0)
{
n /= p[i];
tmp ++;
}
ret *= tmp + 1;
}
if(n > 1) ret *= 2;
return ret;
}
2. 求n所有正因子和
int sum(int n)
{
int ret = 1;
for(int i = 0; p[i] <= n; i++)// p数组储存素数
if(n % p[i] == 0)
{
int tmp = 1;
while(n % p[i] == 0)
{
n /= p[i];
tmp *= p[i];
}
ret *= (tmp * p[i] - 1) / (p[i] - 1);
}
if(n > 1) ret *= (1 + n);
return ret;
}
3. nlogn预处理正整数i所有正因子和dp[i]
ll dp[maxn];
int isp[maxn];
void init()
{
memset(isp, -1, sizeof(isp));
for(int i = 2; i < maxn; i ++)
if(isp[i] == -1)
{
isp[i] = i;
if(i < 11111) for(int j = i * i; j < maxn; j += i)
{
isp[j] = i;
}
}
dp[1] = 1;
for(int i = 2; i < maxn; i ++)
{
ll cnt = isp[i];
int a = i;
while(a % isp[i] == 0)
{
cnt *= isp[i];
a /= isp[i];
}
dp[i] = dp[a] * (cnt - 1) / (isp[i] - 1);
}
}
4. pollard_rho算法O(sqrt(p)) 求n质因子
ll ct; // 记录质因子个数
ll fac[N]; // fac数组储存质因子
ll pollard_rho(ll n, ll c)
{
ll i = 1, k = 2;
ll x = rand() % (n - 1) + 1;
ll y = x;
while(true)
{
i++;
x = (q_pow(x, x, n) + c) % n;
ll d = gcd((y - x + n) % n, n);
if(1 < d && d < n) return d;
if(y == x) return n;
if(i == k)
{
y = x;
k <<= 1;
}
}
}
void find(ll n, ll c) // 传入参数c设置为120
{
if(n == 1) return;
if(Miller_Rabin(n))
{
fac[ct++] = n;
return ;
}
ll p = n;
ll k = c;
while(p >= n) p = pollard_rho(p, c--);
find(p, k);
find(n / p, k);
}
费马小定理： 当m是质数时，a^(m - 1) = 1(mod m)
欧拉定理： 对任何两个互质的正整数a,m(m > 1)有 a^(Euler(m)) = 1 (mod m)
树状数组
起点从1开始
* 区间更新，单点查询: update(l,val); update(r+1,-val); query(pos);
* 单点更新，区间查询: update(pos,val); query(r) - query(l);
const int maxn = 1e5+7;
int c[maxn];
void update(int pos,int val)
{
while(pos <= maxn)
{
c[pos] += val;
pos += lowbit(pos);
}
}
int query(int pos)
{
int ret = 0;
while(pos > 0)
{
ret += c[pos];
pos -= lowbit(pos);
}
return ret;
}
线段树
1. 单点更新，区间求最值
int t[maxn << 2];
void update(int i,int b,int e,int pos,int val)
{
if(b == e)
{
t[i] = val;
return ;
}
int mid = (b + e) / 2;
if(pos <= mid) update(i << 1, b, mid, pos, val);
else update(i << 1 | 1, mid + 1, e, pos, val);
t[i] = max(t[i << 1], t[i << 1 | 1]);
}
int query(int i,int b,int e,int l,int r)
{
if(b >= l && e <= r) return t[i];
int mid = (b + e) / 2;
if(r <= mid) return query(i << 1, b, mid, l, r);
else if(l > mid) return query(i << 1 | 1, mid + 1, e, l, r);
else return max(query(i << 1, b, mid, l, r), query(i << 1 | 1, mid + 1, e, l, r));
}
2. 区间更新，区间求和
ll t[maxn << 2], lazy[maxn << 2];
void pushdown(int i,int b,int e)
{
if(lazy[i])
{
int mid = (b + e) / 2;
t[i << 1] += lazy[i] * (mid - b + 1);
t[i << 1 | 1] += lazy[i] * (e - mid);
lazy[i << 1] += lazy[i];
lazy[i << 1 | 1] += lazy[i];
lazy[i] = 0;
}
}
void update(int i,int b,int e,int l,int r,int val)
{
if(b >= l && e <= r)
{
t[i] += 1LL * val * (e - b + 1);
lazy[i] += val;
return;
}
pushdown(i, b, e);
int mid = (b + e) / 2;
if(r <= mid) update(i << 1, b, mid, l, r, val);
else if(l > mid) update(i << 1 | 1, mid + 1, e, l, r, val);
else
{
update(i << 1, b, mid, l, r, val);
update(i << 1 | 1, mid + 1, e, l, r, val);
}
t[i] = t[i << 1] + t[i << 1 | 1];
}
ll query(int i,int b,int e,int l,int r)
{
if(b >= l && e <= r) return t[i];
pushdown(i, b, e);
int mid = (b + e) / 2;
if(r <= mid) return query(i << 1, b, mid, l, r);
else if(l > mid) return query(i << 1 | 1, mid + 1, e, l, r);
else return query(i << 1, b, mid, l, r) + query(i << 1 | 1, mid + 1, e, l, r);
}
nlog最大上升子序列
int arr[maxn],ans[maxn],len;
// 二分查找求下界,返回 >= 所查找对象的第一个位置
int binary_search(int i)
{
int l = 0, r = len, mid;
while(l < r)
{
mid = l + (r - l) / 2;
if(ans[mid] >= arr[i]) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
// arr存数据，从0开始
ans[0] = arr[0];
len = 1;
for(int i=1; i<n; i++)
{
if(arr[i] > ans[len]) ans[++len] = arr[i];
else
{
int pos = binary_search(i);
ans[pos] = arr[i];
}
}
}
Java BigInteger
BigInteger abs() 返回大整数的绝对值
boolean equals(BigInteger val) 返回两个大整数是否相等
int comareTo(BigInteger val) 返回a - b
BigInteger add(BigInteger val) 返回两个大整数的和
BigInteger subtract(BigInteger val)返回两个大整数相减的结果
BigInteger multiply(BigInteger val) 返回两个大整数的积
BigInteger divide(BigInteger val) 返回两个大整数的商
BigInteger mod(BigInteger val) 用当前大整数对val求模
BigInteger remainder(BigInteger val) 返回当前大整数除以val的余数
BigInteger pow(int exponent) 返回当前大整数的exponent次方
BigInteger negate() 返回当前大整数的相反数
BigInteger gcd(BigInteger val) 返回大整数的最大公约数
BigInteger max(BigInteger val) 返回两个大整数的最大者
BigInteger min(BigInteger val) 返回两个大整数的最小者
BigInteger leftShift(int n) 将当前大整数左移n位后返回
BigInteger rightShift(int n) 将当前大整数右移n位后返回
BigInteger not() 返回当前大整数的非
BigInteger xor(BigInteger val) 返回两个大整数的异或
BigInteger and(BigInteger val) 返回两个大整数的按位与的结果
BigInteger or(BigInteger val) 返回两个大整数的按位或
BigInteger andNot(BigInteger val) 返回两个大整数与非的结果
double doubleValue() 返回大整数的double类型的值
float floatValue() 返回大整数的float类型的值
int intValue() 返回大整数的整型值
long longValue() 返回大整数的long型值
byte[] toByteArray(BigInteger val)将大整数转换成二进制反码保存在byte数组中
String toString() 将当前大整数转换成十进制的字符串形式
博弈
1. 巴什博奕模型：只有一堆n个物品，两个人轮流从中取物，规定每次最少取一个，最多取m个，最后取光者为胜
int n,m;
cin >> n >> m;
if(n % (m + 1) == 0) cout << "后手必胜" << endl;
else cout << "先手必胜" << endl;
2. 威佐夫博弈模型：有两堆各若干的物品，两人轮流从其中一堆取至少一件物品，至多不限，或从两堆中同时取相同件物品，规定最后取完者胜利
若两堆物品的初始值为（x，y），且x<y，则另z=y-x；
记w=（int）[（（sqrt（5）+1）/2）*z ]；
若w=x，则先手必败，否则先手必胜
int n,m,temp;
cin >> n >> m;
if(n > m) swap(n, m);
temp = (int)((m - n) * (1 + sqrt(5.0)) / 2.0);
if(temp == n) cout<<"后手必胜"<<endl;
else cout<<"先手必胜"<<endl;
3.尼姆博弈模型
有任意堆物品，每堆物品的个数是任意的，双方轮流从中取物品，每一次只能从一堆物品中取部分或全部物品，最少取一件，取到最后一件物品的人获胜
把每堆物品数全部异或起来，如果得到的值为0，那么先手必败，否则先手必胜
int n,ans,temp;
cin >> n;
temp = 0;
for(int i=0;i<n;i++)
{
cin >> ans;
temp ^= ans;
}
if(temp == 0) cout << "后手必胜" << endl;
else cout << "先手必胜" << endl;
4.斐波那契博弈模型
有一堆物品，两人轮流取物品，先手最少取一个，至多无上限，但不能把物品取完，之后每次取的物品数不能超过上一次取的物品数的二倍且至少为一件，取走最后一件物品的人获胜
先手胜当且仅当n不是斐波那契数（n为物品总数）
int f[N];
void init()
{
f[0] = f[1] = 1;
for(int i=2;i<N;i++)
f[i] = f[i-1] + f[i-2];
}
int main()
{
init();
int n;
while(cin>>n)
{
if(n == 0) break;
bool flag = 0;
for(int i=0;i<N;i++)
{
if(f[i] == n)
{
flag = 1;
break;
}
}
if(flag) puts("Second win");
else puts("First win");
}
}