学步园

#define LL long long  
#define FF(i,n) for(i=0;i<n;i++)  
LL f[N];  
LL ans[N];  
LL init[N];  
LL buf[N];  
void matrixMul(LL a[N],LL b[N],LL n,LL mod)  
{  
    int i,j;  
    FF(i, n) buf[i]=0;  
    FF(i, n) FF(j,n) if(a[(i - j + n) % n] && b[j])  
            buf[i] = (buf[i] + a[(i - j + n) % n] * b[j]);  
    FF(i, n) a[i] = buf[i] % mod; // 算完后再取模，节省时间  
}  
  
void matrixMul(int n,int m,int mod)  
{  
    int i,j;  
    FF(i,n) ans[i] = (i==0);  
    while(m > 1)  
    {  
        if(m&1) matrixMul(ans, init, n, mod);  
        matrixMul(init, init, n, mod);  
        m >>= 1;  
    }  
    matrixMul(init, ans, n, mod);  
}  

UVALive
4727 Jump  约瑟夫变形问题

LL gcd(LL a, LL b)  
{  
    return b == 0 ? a : gcd(b, a % b);  
}  
  
void E_gcd(LL a, LL b, LL &d, LL& x, LL& y)  
{  
    if(!b)  
    {  
        d = a;  
        x = 1, y = 0;  
    }  
    else  
    {  
        E_gcd(b, a % b, d, y, x);  
        y -= x*(a / b);  
    }  
}  

hdu 4497 GCD and LCM   质分解

模板部分：

const int N = 111111;  
  
vector<int> hav;  
bool isp[N];  
int p[N], cnt;  
  
void getp()  
{  
    int i, j;cnt = 0;  
    isp[0] = isp[1] = 1;  
    for(i = 2; i < N; i ++)  
    {  
        if(!isp[i])  
        {  
            p[cnt ++] = i;  
            if(i <= 1111)for(j = i * i; j < N; j += i) isp[j] = 1;  
        }  
    }  
}  
  
void get_hav(int h)  //求h的所有质因数（算重复）
{  
    int i;  
    for(i = 0; i < cnt && h > 1; i ++)  
    {  
        if(h % p[i] == 0)  
        {  
            h /= p[i];  
            hav.push_back(p[i]);  
            i --;  
        }  
    }  
    if(h != 1) hav.push_back(h);  
}  

hdu 4418 Time travel   高斯消元

模板部分：

inline int sgn(double d) {  
    if (fabs(d) < eps) return 0;  
    return d > 0 ? 1 : -1;  
}  
  
int gauss(int N, int M){  
    int i, j, r, c, pvt;  
    double maxp;  
    for (r = 0, c = 0; r < N && c < M; ++ r, ++ c) {  
        for (maxp = 0, i = r; i < N; ++ i)  
            if (fabs(a[i][c])>fabs(maxp)) maxp = a[pvt=i][c];  
        if (sgn(maxp) == 0) {  
            r--;  
            continue;  
        }  
        if (pvt != r)  
            for (j = r; j <= M; ++j) swap(a[r][j], a[pvt][j]);  
        for (j = c+1; j <= M; ++j) {  
            a[r][j] /= maxp;  
            for (i = r+1; i < N; ++i)  
                a[i][j] -= a[i][c]*a[r][j];  
        }  
    }  
    for (i = r; i < N; ++i)  
        if (sgn(a[i][M])) return -1;  
    if (r < M) return M-r;  
    for (i = M-1; i >= 0; --i)  
        for (j = i+1; j < M; ++j)  
            a[i][M] -= a[j][M]*a[i][j];  
    return 0;  
}  

ZOJ
2320 Cracking' RSA  其次布尔线性方程组，高斯消元。

int gauss(int N, int M)  
{    
    int r, c, pvt;    
    bool flag;  
    for (r = 0, c = 0; r < N && c < M; ++ r, ++ c) {  
        flag = false;  
        for (int i = r; i < N; ++ i)    
            if (a[i][c]) {  
                flag = a[pvt=i][c];  
                break;  
            }  
        if (!flag) {    
            r--; continue;    
        }    
        if (pvt != r)    
            for (int j = r; j <= M; ++j) swap(a[r][j], a[pvt][j]);    
        for (int i = r+1; i < N; ++i)    
            if(a[i][c])  
            {  
                a[i][c] = false;   
                for (int j = c+1; j <= M; ++j) {    
                    if(a[r][j]) a[i][j] = !a[i][j];  
            }  
        }  
    }   
    return r;  //return的是系数矩阵的秩
}  

 

hdu 4746 Mophues  莫比乌斯反演

模板部分：

void Mobius()
{
    CLR(isp, 0);CLR(cnt, 0);
    int tot = 0;mob[1] = 1;
    for(int i = 2; i < N; i ++)
    {
        if(!isp[i])
        {
            p[tot ++] = i;
            mob[i] = -1;cnt[i] = 1;
        }
        for(int j = 0; j < tot && p[j] * i < N; j ++)
        {
            isp[p[j] * i] = true;
            cnt[i * p[j]] = cnt[i] + 1;
            if(i % p[j] == 0)
            {
                mob[p[j] * i] = 0;
                break;
            }
            else
            {
                mob[p[j] * i] = -mob[i];
            }
        }
    }
}

分块处理：

for(int i = 1, j = 1; i < n; i = j + 1)  
{  
      j = min(n / (n / i), m / (m / i));  
      ans += (LL)(mbs[j][p] - mbs[i - 1][p]) * (n / i) * (m / i);  
}  

容斥原理：

void dfs(int st, LL now)  ///num表示元素个数。
{  
    ans.insert(now);  
    if(st >= tot) return;  
    LL tmp = 1;  
    for(int i = 0; i <= num[st]; i ++)  
    {  
        dfs(st + 1, now * tmp);  
        tmp *= bef[st];  
    }  
    return ;  
}  

错排公式。（摘自百科）

当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用M(n）表示，那么M(n-1）就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.

第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

第二步，放编号为k的元素，这时有两种情况⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有M(n-2）种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有M(n-1）种方法；

综上得到

M(n)=(n-1）[M(n-2）+M(n-1）]

特殊地，M⑴=0,M⑵=1

下面通过这个递推关系推导通项公式：

为方便起见，设M(k)=k!N(k),(k=1,2，…，n)

则N⑴=0,N⑵=1/2

n>=3时，n!N(n)=(n-1）（n-1）！N(n-1）+(n-1）！N(n-2）

即 nN(n)=(n-1）N(n-1）+N(n-2）

于是有N(n)-N(n-1）=-[N(n-1）-N(n-2）]/n=(-1/n)[-1/(n-1）][-1/(n-2）]…（-1/3）[N⑵-N⑴]=(-1）^n/n!

因此

N(n-1）-N(n-2）=(-1）^(n-1）/(n-1）！

N⑵-N⑴=(-1）^2/2!

相加，可得

N(n)=(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!

因此

M(n)=n![(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!]

可以得到

错排公式为M(n)=n！（1/2!-1/3!+…..+(-1）^n/n!)

梅森素数   from  百科