CJer in SJTU

7011

$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$

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

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

blablabla


#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];

{
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);
}
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;
}


#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];

{
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;
dout[a]++;
}
memset(f,-1,sizeof f);
printf("%.2lf\n",dp(1));
return 0;
}


1 Nim游戏
2 $Sg$函数(有向无环图中定义)

$Sg(u) =$ 集合{$0,2$}中不存在的一个最小自然数
$Sg(start)=1$

1个棋子 先手必胜 <=> $Sg(start)≠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];

{
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);
}
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;
}


$f[i]:从i跳到N的期望长度$
$边界:f[N]=0$
$答案:f[1]$

\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];

{
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;
dout[a]++;
}
memset(f,-1,sizeof f);
printf("%.2lf\n",dp(1));
return 0;
}


#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 组中,问有多少种不同的分法？

$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}$

$$\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}

$$C_{M+N-1}^{N-1} = \frac{(M+N-1)(M+N-2)…(M-1)}{(N-1)!} \\ O(N)项$$

$$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;
}



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}

### 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个方程,有唯一解-高斯消元

$$\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]$$

### 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;
}



#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;
}