zcmimi's blog

arrow_back二进制共7篇文章

avatar
zcmimi
2020-06-01 13:28:00
avatar
zcmimi
2020-03-02

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p} \cdot C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大

avatar
zc
2020-10-21 18:55:41

查看原题

点击跳转

95分(未特判2^64)

#include<iostream>
int n;unsigned long long k;
int main(){
    std::cin>>n>>k;
    k^=k>>1;
    while(~--n)std::cout<<(k>>n&1);
}

100分简洁代码:

avatar
zc
2020-06-01 19:50:00
查看原题

点击跳转

先按魔法值排序,然后按顺序插入,如果不能被当前集合异或出来,那么插入并加上其贡献

avatar
zc
2020-05-29 17:09:00
查看原题

点击跳转

矩阵乘法

这题倍增加速比快速幂快,可以节省很多多余的计算

二进制拆位后才能矩阵运算

avatar
zc
2020-03-08 10:54:00
查看原题

点击跳转

K^x \equiv 1 \pmod M

求最小的非负整数x

最近刚学了bsgs,一眼看成exbsgs

exbsgs可以,但是比较麻烦

看到最后是1,我们可以想到欧拉定理:

K^{\varphi(M)} \equiv 1 \pmod M(\gcd(K,M)=1)

可以发现,答案是\varphi(M)的约数,那么枚举\varphi(M)的约数即可(可以一直尝试枚举删掉约数)

\gcd(K,M)!=1时无解

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

题意

一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。

1/1
Search
search