头像

仅存老实人

CJer in SJTU




离线:30分钟前



891Nim游戏0.PNG
从$a_{i}$中拿走$a_{i}-(a_{i}$^$x)$堆石子
剩下$a_{i}-(a_{i}-(a_{i}$^$x))$ = $a_{i}$^$x$

$a_{i}$剩下的部分和其他的异或
=$a_{1}$^$a_{2}$^…^$a_{i}$^$x$^$a_{i+1}$…^$a_{n+1}$
=$x$^$x$
=$0$

2 则证明了当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n+1}$非零时,总可以找到一个拿石子的方案使得拿完后异或$=0$

891Nim游戏1.PNG

891Nim游戏2.PNG

当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n}$为零时,假设

$a_{i}$拿完后变成$a’_{i}$,拿完后的异或和==0

所有数异或变成$a_{1}$^$a_{2}$^…^$a_{i}’$ ^ $a_{i+1}$…^$a_{n+1}$

此时我们让拿之前的异或$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n}$和拿之后的异或$a_{1}$^$a_{2}$^…^$a_{i}’$ ^ $a_{i+1}$…^$a_{n}$做异或,除$a_{i}’$外其他项两两消掉只剩下$a_{i}$^$a_{i}’$==0则需要$a_{i}$==$a_{i}’$,与$a_{i}’$是$a_{i}$拿走一部分后的数($a_{i}’$<$a_{i}$矛盾)

3 当$a_{1}$^$a_{2}$^…^$a_{i}$^$a_{i+1}$…^$a_{n+1}$为零时,不管怎么拿,剩下的所有数的异或一定不是0

blablabla


活动打卡代码 AcWing 1319. 移棋子游戏

#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

const int N = 2010, M = 6010;

int n, m, k;
int h[N], e[M], ne[M], idx;
int f[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int sg(int u)
{
    if (f[u] != -1) return f[u];
    // 找u能到的邻点
    set<int> S;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        S.insert(sg(j));
    }
    // 找最小的不能到的点
    for (int i = 0; ; i ++ )
        if (S.count(i) == 0)
        {
            f[u] = i;
            break;
        }

    return f[u];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 0; i < k; i ++ )
    {
        int u;
        scanf("%d", &u);
        res ^= sg(u);
    }
    if (res) puts("win");
    else puts("lose");

    return 0;
}


活动打卡代码 AcWing 217. 绿豆蛙的归宿

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dout[N];
double f[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx]=c,h[a]=idx++;
}

double dp(int u)
{
    if(f[u]>=0)return f[u];
    f[u]=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        f[u]+=(w[i]+dp(j))/dout[u];
    }
    return f[u];
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        dout[a]++;
    }
    memset(f,-1,sizeof f);
    printf("%.2lf\n",dp(1));
    return 0;
}



1 Nim游戏
2 $Sg$函数(有向无环图中定义)
1319移棋子游戏.PNG
对于每个点求Sg值
$Sg(u) = $ 集合{$ 0,2 $}中不存在的一个最小自然数
$Sg(start)=1$

1个棋子 先手必胜 <=> $Sg(start)≠0$
多个棋子 先手必胜 <=> $Sg(S_{1})$^$Sg(S_{2})$^…^$Sg(S_{k})≠0$

#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

const int N = 2010, M = 6010;

int n, m, k;
int h[N], e[M], ne[M], idx;
int f[N];

void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int sg(int u)
{
    if (f[u] != -1) return f[u];
    // 找u能到的邻点
    set<int> S;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        S.insert(sg(j));
    }
    // 找最小的集合中没有的自然数
    for (int i = 0; ; i ++ )
        if (S.count(i) == 0)
        {
            f[u] = i;
            break;
        }

    return f[u];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 0; i < k; i ++ )
    {
        int u;
        scanf("%d", &u);
        res ^= sg(u);
    }
    if (res) puts("win");
    else puts("lose");

    return 0;
}



有向无环图
217概率dp.PNG
事件发生的期望的线性性$E(aX+bY) = aE(X)+bE(Y)$
$f[i]:从i跳到N的期望长度$
$边界:f[N]=0$
$答案:f[1]$
217概率dp1.PNG

$$
\begin{align}
E(i)&=E(\frac{1}{k}(w_{1}+x_{1}) + \frac{1}{k}(w_{2}+x_{2}) +…+\frac{1}{k}(w_{k}+x_{k}) )\\
&=\frac{1}{k}(w_{1}+E(x_{1})) +\frac{1}{k}(w_{2}+E(x_{2}))…+\frac{1}{k}(w_{k}+E(x_{k}))\\
&=\frac{1}{k}(w_{1}+w_{2}+…+w_{k})+\frac{1}{k}(E(x_{1})+E(x_{2})+…+E(x_{k}))\\
f(i)&=\frac{1}{k}(w_{1}+w_{2}+…+w_{k})+\frac{1}{k}(f(s_{1})+f(s_{2})+…+f(s_{k}))\\
&=\sum_{i=1}^{k}\frac{1}{k}(w_{i}+f(s_{i}))
\end{align}
$$

问题转化为按拓扑序从后往前推一遍

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dout[N];
double f[N];

void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a],w[idx]=c,h[a]=idx++;
}

double dp(int u)
{
    if(f[u]>=0)return f[u];
    f[u]=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        f[u]+=(w[i]+dp(j))/dout[u];
    }
    return f[u];
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        dout[a]++;
    }
    memset(f,-1,sizeof f);
    printf("%.2lf\n",dp(1));
    return 0;
}


活动打卡代码 AcWing 214. Devu和鲜花

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;//忘了定义

const int N = 20, mod = 1e9 + 7;

LL A[N];// 没有定义LL 
int down = 1;

int qmi(int a,int k,int p)
{
    int res = 1;
    while(k)
    {
        if(k&1) res = (LL)res*a%mod;
        a = (LL)a*a%p;
        k>>=1;
    }
    return res;
}

int C(LL a,LL b)
{
    if(a<b) return 0;
    int up=1;
    for(LL i=a;i>a-b;i--) up = i%mod*up%mod;//分子累乘
    return (LL)up*down %mod;
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> A[i];

    for (int j = 1; j <= n - 1; j ++ ) down = (LL)j * down % mod;// <=n-1而不是n 分母
    down = qmi(down, mod - 2, mod);//分子1/(n-1)! 通过快速幂逆元 

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        // C_{a}^{b}
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)//二进制数多一个1 变号
            {
                sign *= -1;
                a -= A[j] + 1;// "分母"减去条件j数A[j]+1 - A[j]-1
            }
        res = (res + C(a, b) * sign) % mod;
    }

    cout << (res + mod) % mod << endl;

    return 0;
}





n 个相同的元素,要求分到 m 组中,每组至少元素数为1,问有多少种不同的分法?
$C_{N-1}^{M-1}$
n 个相同的元素,要求分到 m 组中,问有多少种不同的分法?
第二个问题是允许有些组中分到的元素数为0,也就是组中可以为空的。对于这样的题,我们就首先将每组都填上1个,这样所要元素总数就 n+m个,问题也就是转变成将(n+m)个元素分到m组,并且每组至少分到一个的问题,也就可以用插板法来解决。
$C_{M+N-1}^{M-1}$


本题从M个元素分N

1. 假设每个盒子中花有无限个

$x_{1}+…+x_{N}=M \\ x_{i}\in [0,+∞):从第i个盒子里选的花的个数 $
$y_{1}+…+y_{N}=M+N \\ y_{i}\in [1,+∞) $
o o | o o | o o
隔板法:
M+N-1个空隙中插N-1个板子 <=> 方案数$C_{M+N-1}^{N-1}$


现在我们想求满足$x_{1}≤A_{1}…x_{N}≤A_{N}$的方案数,根据容斥原理,问题转化为补集:所有方案数-不满足至少一种条件的方案数
$$
\begin{matrix}
x_{1}>A_{1} & … & x_{N}>A_{N}\\
集合S_{1} & … & 集合S_{N}
\end{matrix}
$$
$$
\begin{align}
答案 &= C_{M+N-1}^{N-1}-cnt(S_{1} \cup S_{2}…\cup S_{N})\\
&= C_{M+N-1}^{N-1}-cnt(S_{1})-cnt(S_{2})-…-cnt(S_{N}) \\
&+ cnt(S_{1} \cap S_{2})…\\
&- cnt(S_{1} \cap S_{2} \cap S_{3})…\\
&+…\\
&= C_{M+N-1}^{N-1}-\sum_{i}^{N}C_{M+N-1-(A_{i}+1)}^{N-1}+\sum_{i<j}^{N}C_{M+N-1-(A_{i}+1)-(A{j}+1)}^{N-1}-…
\end{align}
$$
求$cnt(S_{1})$:$x_{1}≥A_{1}+1$的所有方案
先把$x_{1}$取为$A_{1}+1$只花,则问题转化为选$M-A_{1}-1$只花分$N$组

实现时从$0$枚举到$2^{N-1}$,把每个条件数当成一个二进制数,第$i$位为$1$代表符合条件,正负号取决于条件个数(二进制中$1$的个数)奇偶性,条件数为奇数,符号为-,条件数为偶数,符号为+

$$
C_{M+N-1}^{N-1} = \frac{(M+N-1)(M+N-2)…(M-1)}{(N-1)!}
\\ O(N)项
$$
费马小定理(如果p是一个质数,而整数a不是p的倍数,则有$a^{p-1}≡1(mod p))$求$\frac{1}{(n-1)!}$
$$
a = (n-1)!\\
a^{p-1}=1(mod p)\\
那么a^{p-2}=a^{-1}(mod p)\\
也就是说a的逆元为a^{p-2}
$$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20, mod = 1e9 + 7;

LL A[N];
int down = 1;

int qmi(int a,int k,int p)
{
    int res = 1;
    while(k)
    {
        if(k&1) res = (LL)res*a%mod;
        a = (LL)a*a%p;
        k>>=1;
    }
    return res;
}

int C(LL a,LL b)
{
    if(a<b) return 0;
    int up=1;
    for(LL i=a;i>a-b;i--) up = i%mod*up%mod;//分子累乘
    return (LL)up*down %mod;
}

int main()
{
    LL n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> A[i];

    for (int j = 1; j <= n - 1; j ++ ) down = (LL)j * down % mod;
    down = qmi(down, mod - 2, mod);//分子1/(n-1)! 通过快速幂逆元 

    int res = 0;
    for (int i = 0; i < 1 << n; i ++ )
    {
        // C_{a}^{b}
        LL a = m + n - 1, b = n - 1;
        int sign = 1;
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)//二进制数多一个1 变号
            {
                sign *= -1;
                a -= A[j] + 1;// "分母"减去条件j数A[j]+1 - A[j]-1
            }
        res = (res + C(a, b) * sign) % mod;
    }

    cout << (res + mod) % mod << endl;

    return 0;
}




#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 15;

int n;
double a[N][N], b[N][N];

void gauss()
{
    // 转化成上三角矩阵
    for (int r = 1, c = 1; c <= n; c ++, r ++ )
    {
        // 找主元(从最高行r往下找当前列绝对值最大的值所在的行t)
        int t = r;
        for (int i = r + 1; i <= n; i ++ )
            if (fabs(b[i][c]) > fabs(b[t][c]))
                t = i;

        // 交换(t行交换到当前最高行r)
        for (int i = c; i <= n + 1; i ++ ) swap(b[t][i], b[r][i]);
        // 归一化第r行(做完后对角线上b[r][r]=1,对角线右边的都除了一个b[r][r])
        for (int i = n + 1; i >= c; i -- ) b[r][i] /= b[r][r];
        // 消(做完后对角线b[r][r]同列下方全-1*b[i][r]后变0,
        //    右边都减第r行对应第j列元素b[r][j]的b[i][r]倍)
        for (int i = r + 1; i <= n; i ++ )
            for (int j = n + 1; j >= c; j -- )
                b[i][j] -= b[i][r] * b[r][j];
    }

    // 转化成对角矩阵
    for (int i = n; i > 1; i -- )
        for (int j = i - 1; j; j -- )
        {
            b[j][n + 1] -= b[i][n + 1] * b[j][i];
            b[j][i] = 0;
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n + 1; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%lf", &a[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            b[i][j] += 2 * (a[i][j] - a[0][j]);
            b[i][n + 1] += a[i][j] * a[i][j] - a[0][j] * a[0][j];
        }

    gauss();
    // 此时B矩阵为单位阵,则右边的b[i][n+1]就是x[i]
    for (int i = 1; i <= n; i ++ ) printf("%.3lf ", b[i][n + 1]);

    return 0;
}




球心$[x_{1},x_{2}…x_{n}]$
i个点坐标$[a_{i1},a_{i2},…,a_{in}]$
$$
\begin{align}
(a_{11}-x_{1})^{2}+(a_{12}-x_{2})^{2}+…(a_{1n}-x_{n})^{2}&=R^{2} - -等式1\\
…&=…\\
(a_{n+1,1}-x_{1})^{2}+(a_{n+1,2}-x_{2})^{2}+…(a_{n+1,n}-x_{n})^{2}&=R^{2} - - 等式N+1
\end{align}
$$
把二维转一维

等式2-等式1

1.先看头一项

$$
\begin{align}
a_{21}^{2}+x_{1}^{2}-2a_{21}x_{1}-(a_{11}^{2}+x_{1}^{2}-2a_{11}x_{1}) &= R^{2}-R^{2} \\
a_{21}^{2}-a_{11}^{2} &= 2(a_{21}-a_{11})x_{1}\\
a_{21}+a_{11} &= 2x_{1}
\end{align}
$$

2.把每一项都加进来

$$
\begin{align}
2(a_{21}-a_{11})x_{1}+…+2(a_{2n}-a_{1n})x_{n} &=a_{21}^{2}+…+a_{2n}^{2}-(a_{11}^{2}+…+a_{1n}^{2}) \\
b_{11}x_{1}+…+b_{1n}x_{n} &=b_{1,n+1} \\
\end{align}
$$
其中$b_{ij}$为常数

3.进一步推广到每个等式3-等式2等式n+1-等式n

$$
\begin{align}
b_{11}x_{1}+…+b_{1n}x_{n} &=b_{1,n+1} \\
… &= … \\
b_{n,1}x_{1}+…+b_{nn}x_{n} &=b_{n,n+1} \\
\end{align}
$$
一共n个未知数x_{i} for i in [1,n]
n个方程,有唯一解-高斯消元
矩阵B消元
$$
\left[ \begin{matrix}
a & b & c\\
d & e & f\\
g & h & i
\end{matrix} \right]
\stackrel{找主元+归一化+消左下角}{\rightarrow}
\left[ \begin{matrix}
1 & x & y\\
0 & 1 & z\\
0 & 0 & 1
\end{matrix} \right]
\stackrel{逐列/行消右上角}{\rightarrow}
\left[ \begin{matrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{matrix} \right]
$$

答案

此时B矩阵为单位阵,则右边的b[i][n+1]就是x[i]

Gauss 步骤

1.枚举列

1. 找主元(绝对值最大的数)
2. 交换
3. 归一
4. 消(按列或行消)

2.按行消元

从倒数第二行开始 对角线右边的都用对角线上的消掉
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 15;

int n;
double a[N][N], b[N][N];

void gauss()
{
    // 转化成上三角矩阵
    for (int r = 1, c = 1; c <= n; c ++, r ++ )
    {
        // 找主元(从最高行r往下找当前列绝对值最大的值所在的行t)
        int t = r;
        for (int i = r + 1; i <= n; i ++ )
            if (fabs(b[i][c]) > fabs(b[t][c]))
                t = i;

        // 交换(t行交换到当前最高行r)
        for (int i = c; i <= n + 1; i ++ ) swap(b[t][i], b[r][i]);
        // 归一化第r行(做完后对角线上b[r][r]=1,对角线右边的都除了一个b[r][r])
        for (int i = n + 1; i >= c; i -- ) b[r][i] /= b[r][r];
        // 消(做完后对角线b[r][r]同列下方全-1*b[i][r]后变0,
        //    右边都减第r行对应第j列元素b[r][j]的b[i][r]倍)
        for (int i = r + 1; i <= n; i ++ )
            for (int j = n + 1; j >= c; j -- )
                b[i][j] -= b[i][r] * b[r][j];
    }

    // 转化成对角矩阵
    for (int i = n; i > 1; i -- )
        for (int j = i - 1; j; j -- )
        {
            b[j][n + 1] -= b[i][n + 1] * b[j][i];
            b[j][i] = 0;
        }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n + 1; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%lf", &a[i][j]);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            b[i][j] += 2 * (a[i][j] - a[0][j]);
            b[i][n + 1] += a[i][j] * a[i][j] - a[0][j] * a[0][j];
        }

    gauss();
    // 此时B矩阵为单位阵,则右边的b[i][n+1]就是x[i]
    for (int i = 1; i <= n; i ++ ) printf("%.3lf ", b[i][n + 1]);

    return 0;
}



活动打卡代码 AcWing 1307. 牡牛和牝牛

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1000010,mod=5000011;
int n,k;
int f[N],s[N];
int main()
{
    cin >> n >> k;
    f[0] = s[0] = 1;
    for(int i=1;i<=n;i++)
    {
        if(i>k)
            f[i]=s[i-k-1];
        else
            f[i]=1;
        s[i] = (s[i-1]+f[i])%mod;
    }
    cout << s[n];
    return 0;
}