497D1B

输入

t个询问(1<=t<=100'000)

每个询问A,B,C (1<=A,B,C<=100'000)

要求

若a是A的因子,b是B的因子,c是C的因子,则(a,b,c)记为1种方案

(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)视作同一种方案

输出

求总方案数

解法

看了别人超级宽的代码后 才看懂解法,虽然我第一眼也知道是个容斥

首先众所周知,预处理每个数的因子个数。

然后把A的因子个数 分为{A独有的因子的个数,仅AB共有的因子的个数,仅CA共有的因子的个数,ABC共有的因子的个数}

对B和C同样的处理,然后 就会发现,不过是个4*4*4的排列组合(因为不同的分化之间相互不重叠),注意去重,就随便写都过了,毕竟O(4*4*4*100'000)

497D1B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

int yzcnt[100010];

void init(){
rep(i,1,100001)
yzcnt[i]++;
rep(i,2,100001){
rep(j,1,100000/i+1){
if(i*j<100001){
yzcnt[i*j]++;
}
}
}
}

int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}

ll calc(ll *v1,ll *v2,ll *v3){
if(v1 == v2 && v2 == v3){
return (*v1)*(*v1+1)*(*v1+2)/6;
}
if(v1 == v2){
return (*v3)*((*v1+1)*(*v1)/2);
}
if(v2 == v3){
return (*v1)*((*v2+1)*(*v2)/2);
}
if(v3 == v1){
return (*v2)*((*v3+1)*(*v3)/2);
}
return (*v1)*(*v2)*(*v3);
}

int ec(int a,int b,int c){
return c+7*(b+7*a);
}

int main(){
init();
int t;
cin>>t;
while(t-->0){
int v[3];
scanf("%d %d %d",v,v+1,v+2);
int gab= gcd(v[0],v[1]);
int gbc= gcd(v[1],v[2]);
int gca= gcd(v[2],v[0]);
int gabc= gcd(gab,v[2]);

// 计算每一个的仅有的部分
/*0*/ll a = yzcnt[v[0]] - yzcnt[gab] - yzcnt[gca] + yzcnt[gabc];
/*1*/ll b = yzcnt[v[1]] - yzcnt[gbc] - yzcnt[gab] + yzcnt[gabc];
/*2*/ll c = yzcnt[v[2]] - yzcnt[gca] - yzcnt[gbc] + yzcnt[gabc];
/*3*/ll ab = yzcnt[gab] - yzcnt[gabc];
/*4*/ll bc = yzcnt[gbc] - yzcnt[gabc];
/*5*/ll ca = yzcnt[gca] - yzcnt[gabc];
/*6*/ll abc = yzcnt[gabc];

// 用于4*4*4的枚举
ll *slotA[] = {&a,&ab,&ca,&abc};
ll *slotB[] = {&b,&bc,&ab,&abc};
ll *slotC[] = {&c,&ca,&bc,&abc};

// 用于上面枚举的去重
int slotMaskA[] = {0,3,5,6};
int slotMaskB[] = {1,4,3,6};
int slotMaskC[] = {2,5,4,6};
bool masks[7*7*7];
rep(i,0,7*7*7){
masks[i] = false;
}

// 枚举
ll ans = 0;
rep(i,0,4){
rep(j,0,4){
rep(k,0,4){
int maskarr[] = {slotMaskA[i],slotMaskB[j],slotMaskC[k]};
sort(maskarr,maskarr+3);
int code = ec(maskarr[0],maskarr[1],maskarr[2]);
if(!masks[code]){// 去重
masks[code] = true;
ans +=calc(slotA[i],slotB[j],slotC[k]);
}
}
}
}
printf("%lld\n",ans);
}

return 0;
}

代码

497D1B

参考

493D1C 官方题解

493D1C Petr的代码

497D1B wavator超级宽的代码

493D1C

输入

给你n*n(1<=n<=1'000'000)的格子

要求

每个格子 图上 有3种颜色可以选择,

如果所有格子都上完色后, 存在一列或一行的颜色全部相同,则称作lucky

输出

求 所有lucky的方案数 modulo 998244353

解法

翻译自官方

A{i}表示 有i 行 颜色相同
B{i}表示 有i 列 颜色相同

然后直接 容斥原理公式(搜索一下就能找到的公式) 计算 $A_1 \cup A_2 \ldots A_n \cup B_1 \cup B_2 \ldots B_n$

然后因为 这些行列在哪里和我们的计算无关,所以对于A{i}可以看成选i行,让这i行每行内颜色相同,也就是C(n,i)倍的 方案数

所以有那个公式$ans = \sum_{i=0 \ldots n, j=0 \ldots n, i + j > 0} C_n^i C_n^j (-1)^{i + j + 1} f(i, j)]$

f(i,j)表示前i行j列 lucky的方案数

然后 具体表示f(i,j)

i,j其中一个有0的情况,这种情况,以行举例来说,同色的行 之间是可以不同色的,所以是$3^k$

$f(k, 0) = f(0, k) = 3^k \cdot 3^{n (n - k)}$

其它情况,这样的话 因为 如果至少有1行+1列是同色的,那么所有的同色的行列 都是同色的,这样就是3

$f(i, j) = 3 \cdot 3^{(n - i)(n - j)}$

很明显 这个n,肯定不是能做出来的

那么 分两块,ij带0O(n)时间内算出

其它部分 看数学操作了,首先 带入f(i,j)

$ans=\sum_{i=1}^{n}\sum_{j=1}^{n}C_n^iC_n^j(-1)^{i+j+1}3\cdot3^{(n-i)(n-j)}$

换元 $i \to n-i, j \to n - j$

$ans = 3 \sum_{i=0}^{n - 1}\sum_{j = 0}^{n - 1} C_n^{n - i} C_n^{n - j} (-1)^{n - i + n - j + 1} \cdot 3^{ij}$

等价化简

$ans = 3 \sum_{i=0}^{n - 1} \sum_{j = 0}^{n - 1} C_n^i C_n^j (-1)^{i + j + 1} \cdot 3^{ij}$

分离

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (-1)^{j} \cdot (3^i)^j$

乘法分配率

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} \sum_{j = 0}^{n - 1} C_n^j (- 3^i)^j$

考虑对后面的求和简化,考虑下面式子

$(a + b)^n = \sum_{i = 0}^{n} C_n^i a^i b^{n - i}$

这里 我们把a取1,b取$-3^i$,再注意到求和到n不是n-1,进行一个加减消除,最后可以把ans化简为

$ans = 3 \sum_{i=0}^{n - 1} C_n^i (-1)^{i+1} [(1 + (-3^i))^n - (-3^i)^n]$

这个式子,可以累加求和在O(n)时间内做出了

众所周知的 模逆元 快速幂 取模什么的就不说了


感觉这里分类是我的问题,我自己想 始终把三个颜色分开想怎么计算,这里合在一起了。

497D1B

输入

t个询问(1<=t<=100'000)

每个询问A,B,C (1<=A,B,C<=100'000)

要求

若a是A的因子,b是B的因子,c是C的因子,则(a,b,c)记为1种方案

(a,b,c),(a,c,b),(b,a,c),(b,c,a),(c,a,b),(c,b,a)视作同一种方案

输出

求总方案数

解法

看了别人超级宽的代码后 才看懂解法,虽然我第一眼也知道是个容斥

首先众所周知,预处理每个数的因子个数。

然后把A的因子个数 分为{A独有的因子的个数,仅AB共有的因子的个数,仅CA共有的因子的个数,ABC共有的因子的个数}

对B和C同样的处理,然后 就会发现,不过是个4*4*4的排列组合(因为不同的分化之间相互不重叠),注意去重,就随便写都过了,毕竟O(4*4*4*100'000)

497D1B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

int yzcnt[100010];

void init(){
rep(i,1,100001)
yzcnt[i]++;
rep(i,2,100001){
rep(j,1,100000/i+1){
if(i*j<100001){
yzcnt[i*j]++;
}
}
}
}

int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}

ll calc(ll *v1,ll *v2,ll *v3){
if(v1 == v2 && v2 == v3){
return (*v1)*(*v1+1)*(*v1+2)/6;
}
if(v1 == v2){
return (*v3)*((*v1+1)*(*v1)/2);
}
if(v2 == v3){
return (*v1)*((*v2+1)*(*v2)/2);
}
if(v3 == v1){
return (*v2)*((*v3+1)*(*v3)/2);
}
return (*v1)*(*v2)*(*v3);
}

int ec(int a,int b,int c){
return c+7*(b+7*a);
}

int main(){
init();
int t;
cin>>t;
while(t-->0){
int v[3];
scanf("%d %d %d",v,v+1,v+2);
int gab= gcd(v[0],v[1]);
int gbc= gcd(v[1],v[2]);
int gca= gcd(v[2],v[0]);
int gabc= gcd(gab,v[2]);

// 计算每一个的仅有的部分
/*0*/ll a = yzcnt[v[0]] - yzcnt[gab] - yzcnt[gca] + yzcnt[gabc];
/*1*/ll b = yzcnt[v[1]] - yzcnt[gbc] - yzcnt[gab] + yzcnt[gabc];
/*2*/ll c = yzcnt[v[2]] - yzcnt[gca] - yzcnt[gbc] + yzcnt[gabc];
/*3*/ll ab = yzcnt[gab] - yzcnt[gabc];
/*4*/ll bc = yzcnt[gbc] - yzcnt[gabc];
/*5*/ll ca = yzcnt[gca] - yzcnt[gabc];
/*6*/ll abc = yzcnt[gabc];

// 用于4*4*4的枚举
ll *slotA[] = {&a,&ab,&ca,&abc};
ll *slotB[] = {&b,&bc,&ab,&abc};
ll *slotC[] = {&c,&ca,&bc,&abc};

// 用于上面枚举的去重
int slotMaskA[] = {0,3,5,6};
int slotMaskB[] = {1,4,3,6};
int slotMaskC[] = {2,5,4,6};
bool masks[7*7*7];
rep(i,0,7*7*7){
masks[i] = false;
}

// 枚举
ll ans = 0;
rep(i,0,4){
rep(j,0,4){
rep(k,0,4){
int maskarr[] = {slotMaskA[i],slotMaskB[j],slotMaskC[k]};
sort(maskarr,maskarr+3);
int code = ec(maskarr[0],maskarr[1],maskarr[2]);
if(!masks[code]){// 去重
masks[code] = true;
ans +=calc(slotA[i],slotB[j],slotC[k]);
}
}
}
}
printf("%lld\n",ans);
}

return 0;
}

代码

497D1B

参考

493D1C 官方题解

493D1C Petr的代码

497D1B wavator超级宽的代码

关于 强连通分量 缩点 tarjan是什么 自行搜索,这里只是封了一个板子

Codeforces Round #490 (Div. 3) E题

题目一眼可得tarjan 也不是一次两次了 封了板子,最开始还想做个模板类,但仔细一想,时间复杂度导致点个数不会超int,所以如果点序号大于int先离散化再做

E题 AC CODE

板子如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* construct: vertexsize
* auto tarjan = new Tarjan(vertex_size)
*
* addpath // 1<=from_vertex,to_vertex<= vertex_size
* tarjan.addpath(from_vertex,to_vertex)
*
* prepare an result array,and work
* int res[vertex_size+1];
* tarjan.work(res);
*
* return:
* res[vertex_id] ===== after_tarjan_vertex_group_id
*/
class Tarjan{
int *low;// lowest node
int *dfn;// deep first node
int *stk;// stack
bool *instk;
bool *visited;

vector<int> * p; // one-way road
int stki;
int id;
int n;
// strongly connected components强联通分量
void scc(int v) {
low[v] = dfn[v] = ++id;
stk[stki++] = v;
instk[v] = true;
visited[v] = true;
for(auto w:p[v]){
if(!visited[w]){
scc(w);
low[v] = min(low[v],low[w]); //v或v的子树能够追溯到的最早的栈中节点的次序编号
} else if(instk[w]){ //v->w后向边
low[v] = min(low[v],dfn[w]);
}
}
int u;
if(low[v] == dfn[v]) {
do{
u = stk[--stki];
dfn[u] = v; //缩点
instk[u] = false; //出栈解除标记
}while(u != v);
}
}
public:
Tarjan(int SZ){
n = SZ;
low = new int[n+1];
stk = new int[n+1];
dfn = new int[n+1];
instk = new bool[n+1];
visited = new bool[n+1];
p = new vector<int>[n+1];
rep(i,0,n+1){
visited[i] = false;
}
id = 0;
stki = 0;
}
~Tarjan(){
delete [] low;
delete [] stk;
delete [] dfn;
delete [] instk;
delete [] visited;
delete [] p;
}
void work(int *ret){
rep(i,1,n+1){
if(!visited[i]){
scc(i);
}
}
rep(i,1,n+1)
ret[i]=dfn[i];
}
void addpath(int i,int j){
p[i].pb(j);
}
};

基本上 使用分3个步骤就好

  1. 根据size初始化

  2. 给它加单向边.addpath(from,to)

  3. 准备一个结果数组a,调用.work(a)

  4. 得到的结果数组a[原来的点序号]=缩点后的点序号

  5. emmm 需要加两个宏使用 #define rep(i,a,n) for (int i=a;i<n;i++)#define pb push_back

增强复用+简化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define pb push_back

class Tarjan{
vector<int> low;
vector<int> dfn;
stack<int> stk;
vector<int> res;
vector<vector<int> > p;
int n;
void scc(int v) {
static int id = 0;
low[v] = dfn[v] = ++id;
stk.push(v);
for(auto w:p[v]){
if(!dfn[w]){ // 未访问过
scc(w);
low[v] = min(low[v],low[w]);
} else if(!res[w]){ // 访问过但没有结果(在栈中)
low[v] = min(low[v],dfn[w]);
}
}
int u;
if(low[v] == dfn[v]) {
do{
res[u = stk.top()] = v;
stk.pop();
}while(u != v);
}
}
public:
Tarjan(int SZ):n(SZ){
low = vector<int>(n+1);
stk = {};
vector<int>(n+1);
dfn = vector<int>(n+1);
res = vector<int> (n+1);
p = vector<vector<int> >(n+1);
}
vector<int> calc(){
rep(i,1,n+1){
if(!res[i]){
scc(i);
}
}
return res;
}
void p2(int i,int j){
p[i].pb(j);
}
};

int main(){
int n,m;
// 点,有向边,
cin>>n>>m;
Tarjan tarjan(n);
rep(i,0,m){
int u,v;
scanf("%d %d",&u,&v);
tarjan.p2(u,v);
}
vector<int> num = tarjan.calc(); // scc 联通分量 标识
rep(i,1,n+1){
printf("%lld: %d\n",i,num[i]);
}
return 0;
}

/**
1->2->3->1
3->4->5

5 5
1 2
2 3
3 1
3 4
4 5
*/

简述操作

tarjan(u)

  1. 深搜: 标记序号, 到达最小, u进栈
  2. 子点v未访问(dfn[v] == 0), 递归tarjan(v), low[u] = min(low[u],low[v])
  3. 子点v在栈中(result[v] == 0), low[u] = min(low[u],深搜序号[v])
  4. 当low[u] == dfn[u]时, 逐个出栈直到遇到u, 这些出栈的都是属于u这个联通分量 result[i] = u

D

难过的是 D 题的 算法细节已经对了,然而还是超时

通过 学习红名大佬的代码,发现是我们共同的n平方的算法的常数不同,我的常数是map查找 hash的速度+stl的效率,而它通过离散化,真的就只有个位数常数,,,,然而仔细想想,离散化的化我也不是遇到一次两次了,感觉不该再栽倒在同一个地方。

拷贝 提取 并修改了 红名大佬代码中做离散化的部分。

1
2
3
4
sort(li.begin(), li.end());
li.resize(unique(li.begin(), li.end())-li.begin());
for(int i=0; i<n; i++)
newv[i]=lower_bound(li.begin(), li.end(), sourcev[i])-li.begin();

解释一下内容,sourcev中存的原始数据

li是 vector,把原始数据放进去

然后 通过排序 和 去重

再对每一个 原始数据找到所离散化出的新结果

参考

大佬的代码

表格整理

图片主要来源于官方的讲义PDF以及Wikipedia

监督学习

线性回归

将输入数据,如图中的红点,求得一条直线表示数据中的线性关系,并且这条直线在概率期望上达到最佳(后面算法省略这句)。

线性回归

梯度下降

找函数极值小值点,图中相同颜色线为等高线,越靠近中心高度越低,运用高数的梯度运算和梯度下降能够得到如图中蓝色x标记的逐步逼近的极值点。

梯度下降

Normal Equation

同样是解决线性回归问题,和梯度下降不同的是,运用矩阵运算,直接得到参数的表达式

Normal Equations

Logistics 回归

分类算法,对一侧数据0,另一侧数据1的训练数据建立分类器,图中的点是 训练输入,线是得到的logistics函数

logistics

高斯切线法

高数知识,二次收敛,加速点的收敛,如图 通过计算切线与坐标轴的交点作为下一次的迭代起始值。

gao si qie xian

广义线性模型GLM

按照所提出的假设模型,能够直接得到所需要的 拟合函数,可以用来证明上面 的线性回归中最小二乘法是最优,以及Logistics 回归中的函数选取。

GLM

softmax 回归

分类到对互斥的k个类别,公式推导采用带入GLM

softmax

高斯判别分析GDA

对0分布满足高斯分布,1分布也满足高斯分布的分布进行线性分类。

GDA

朴素贝叶斯

整体与特征来判断整体的分类,如垃圾邮件根据出现的词汇进行分类,很暴力直接计算概率

bayes

拉普拉斯平滑

解决朴素贝叶斯中可能出现的0除以0的情况,分子+1,分母+可分的种类数k

laplace

最优线性分类器

如图能够找到将 数据分开,并且离分割线最近的点的距离值最大的分类器。

jihejuli

拉格朗日对偶、KKT

用于具体解决 最优线性分类器的支撑方法

KKT

核函数

将变量非线性变化映射到高维空间,减小计算量,表示量,配合其它算法使用能获得高维空间性质。

Kernel

支持向量机SVM

将低维不可线性分割的 通过核函数映射到高维度,再在高维中进行最优线性分割

SVM

L1 Regularization

在有部分异常点时的分割,通过添加惩罚项解决如下图异常点导致变化过大的问题。

L1regularization

SMO

对于多个参数 每次选一个参数进行取极值点,SMO能在带等式与不等式的约束限定情况下,每次两个参数逐步逼近。

SMO

均方误差MSE

能够用于分析 过拟合 还是 欠拟合

mse

错误分析

按步骤替代/隔离分析,逐个增加或逐个减少。按训练误差 方差,实验 误差方差分析。

error

VC维、hoeffding不定式

用于证明概率下训练集和误差的上下界存在性。

验证方式、模型选择

将部分的训练数据不用于训练而用于检验模型

感知器

感知器:转换后的值小于0输出-1,大于等于0输出

无监督学习

k-means

对无标记的点进行分类(寻找分类的中心)

kmeans

高斯混合模型GMM

可以看作类似前面的高斯判别模型GDA,但是现在的输入数据是无标记的

GMM

EM算法

用于GMM等无标记的混合模型的分离,先假设隐含变量Z以及它的分布Q,和k-means的思想类似,E-step优化Q,M-step优化参数,重复直到收敛 [使用Jensen不等式],分离效果见上图

EM

因子分析

对训练集量少,维数大,分类的类别少的分布进行分类,思想是建立隐含低维度变量z,通过矩阵转化投影到高维,再加上高斯扰动误差

Factor

主成分分析PCA

对于高维空间的数据,找到其前k个相互正交的关键维度的向量,可用线性代数奇异值分解SVD进行快速计算。可以用于降维度,作为其它算法的预处理步骤,或找到关系的主要方面。

PCA

独立成分分析ICA

对于多维度,相互独立的非高斯分布成分,找到每个成分的轴,并将所有轴转换为正交轴。可用于特征提取,特征分离,如音频分离,计算人脸识别面部特征向量,对脑电波数据分离预处理去除眨眼和心跳信号。

ICA

马尔科夫模型

马尔科夫决策过程 MDP

能够学习带有状态,和基于状态动作的一类事情,学出一个策略集,如自动驾驶,需要设置奖励函数,概率函数等参数函数。策略迭代和值迭代

MDP

离散化连续状态的MDP

也就是字面意思离散化,在2维下工作一般不错,高维度后无论是维数灾难还是离散化难度,以及模型最终产物都难以普遍满意

MDPlsh

MDP中的模型模拟器

用于概率状态未知时,用实验+拟合得到模型,从而代替概率函数的位置

simulator

线性二次型调节控制LQR

解决状态依赖于前一个状态前一个动作以及时间的策略选择,在有限时间内用动规(倒着递推),多次实验线性拟合基于时间的。对于非线性函数仅能取较近的输入值,用近似的切线做近似的线性处理。通过加强奖励函数,初始值(时间T)矩阵,等限定。得出结论,动作与状态的线性相关,且计算过程中可以省去无关迭代

LQR

kalman滤波

观测值转化为概率上的真实值

kalman

LQG

LQG=LQR+kalman滤波

微分动规DDP

根据当前决策选定轨迹,做LQR,更新决策,重复。从函数上理解是函数逐步靠近,即使是一个不那么好的模拟器

DDP

pegasus策略搜索

处理非线性模型函数的情况。选取随机序列并重复使用于模型训练,在模型选择时选取非线性的模型(如logistics 函数),用极大似然去找该模型下的最优策略。

policy

0%