MinamiMelon
0%

发表于 更新于 分类于

向量空间:给定域\(F\)，\(F\)上的向量空间\(V\)是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。

线性无关:对于向量空间中\(V\)上\(n\)个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\),若存在不全为\(0\)的数\(a_i \in F\)满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]

则称这\(n\)个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。

线性组合:对于向量空间中 V 上 nn 个元素的向量组\((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其线性组合（linear combination）是如下形式的向量

\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] ​​ 其中\(a_1, \ldots, a_n \in F\)

一组向量线性无关 \(\Leftrightarrow\)没有向量可用有限个其他向量的线性组合所表示

张成:对于向量空间中 \(V\) 上 \(n\) 个元素的向量组 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其所有线性组合所构成的集合称为 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)的张成（span），记为 \(\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)\)

基:若向量空间 \(V\) 中向量组 \(\mathfrak{B}\) 既是线性无关的又可以张成 \(V\)，则称其为\(V\) 的基（basis）。

\(\mathfrak{B}\)中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

设 \(\mathfrak {B}\) 是向量空间 \(V\) 的基。则\(\mathfrak {B}\)具有以下性质：

1.\(V\) 是 \(\mathfrak {B}\)的极小生成集，就是说只有\(\mathfrak {B}\)能张成\(V\)，而它的任何真子集都不张成全部的向量空间。

2.\(\mathfrak {B}\) 是 \(V\) 中线性无关向量的极大集合，就是说 \(\mathfrak {B}\) 在\(V\) 中是线性无关集合，而且\(V\) 中没有其他线性无关集合包含它作为真子集。

3.\(V\) 中所有的向量都可以按唯一的方式表达为\(\mathfrak {B}\) 中向量的线性组合。

异或运算下的基} $

对于数 \(a_0, a_1, \ldots, a_n\)，将 \(a_i\)的二进制表示$ (b_{m}b_0)_2$​ 看作一个向量。向量组 \(\mathbf{a}_1, \ldots, \mathbf{a}_n\)可以张成一个向量集合 \(\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)\)，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 \(V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)\)

设集合\(S\)中最大的数在二进制意义下有\(L\)位，我们使用一个 \([0\dots L]\)的数组\(a\)来储存线性基。

这种线性基的构造方法保证了一个特殊性质，对于每一个\(i\),\(a_i\)有以下两种可能：

  • \(a_i=0\)，并且 只有} \(满足\)j<i\(的\)a_j\(（即\)a_i\(前面所有数）的第\)i$个二进制位一定为\(0\)。

  • \(a_i\neq0\),并且

  1. 整个\(a\)数组只有\(a_i\)的第\(i\)个二进制位为\(1\)；
  2. \(a_i\)更高的二进制位一定为1

（如果排成矩阵，形成一个下三角矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
const int MAXL=60;
ll a[MAXL+1];int lbsiz;
void insert(ll t){//高斯消元解出的对角矩阵的非零行构成的向量组 
    for(int j=MAXL;j>=0;--j){// 逆序枚举二进制位
        if(!((t>>j)&1)) continue;// 如果 t 的第 j 位为 0，则跳过
        if(a[j]) t^=a[j];
        else{// 找到可以插入 a[j] 的位置
            // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
// 如果某一个a[k]=0也无须担心，因为这时候第k位不存在于线性基中，不需要保证t的第k位为 0	
            for(int k=0;k<j;++k) if((t>>k)&1) t^=a[k];
            // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
            for(int k=j+1;k<=MAXL;++k) if((a[k]>>j)&1) a[k]^=t;
                // 插入到 a[j] 的位置上
            a[j]=t;++lbsiz;
            return;// 不要忘记，结束插入过程
        }
    }
}

最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。

1
2
3
4
5
ll querymax(){
    ll res=0;
    for(int i=0;i<=MAXL;++i) res^=a[i];
    return res;
}

集合任选大于1个元素异或出的第k大数

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
vector<ll> v;
bool zero;int n;//zero: 是否能异或出0
void init(){
    lbsiz=0;
    v.clear();
    memset(a,0,sizeof a);
}
void prepare(){
    zero=(lbsiz!=n);
    for(int i=0;i<=MAXL;++i){
        if(a[i]) v.push_back(a[i]);
    }
}
ll query(ll k){
    if(zero) --k;
    if(k>=(1ll<<v.size())) return -1;
    ll res=0;
    for(int i=MAXL;i>=0;--i) if((k>>i)&1) res^=v[i];
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ttt=1;ttt<=T;++ttt){
        init();
        scanf("%d",&n);ll t;
        for(int i=1;i<=n;++i){
            scanf("%lld",&t);
            insert(t);
        }
        prepare();
        printf("Case #%d:\n",ttt);
        int q;scanf("%d",&q);
        while(q--){
            scanf("%lld",&t);
            printf("%lld\n",query(t));
        }
    }
    return 0;
}

P4151 [WC2011]最大XOR和路径

异或路径问题：转化成任意一条路径，和任意个圈的异或。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M=200000+5,N=50000+5,MAXL=60;
struct Edge{
	int t,n;
	ll v;
}e[M];
int hd[N],cnt;
inline void build(int f,int t,ll v){
	e[++cnt]=(Edge){t,hd[f],v};
	hd[f]=cnt;
}
ll a[MAXL+3],dis[N];
bool vis[N];
void insert(ll t){
	for(int j=MAXL;j>=0;--j){
		if(!((t>>j)&1)) continue;
		if(a[j]) t^=a[j];
		else{
			for(int k=0;k<j;++k){
				if((t>>k)&1) t^=a[k];
			}
			for(int k=j+1;k<=MAXL;++k){
				if((a[k]>>j)&1){
					a[k]^=t;
				}
			}
			a[j]=t;
			return;
		}
	}
}
int n,m;
void dfs(int u,ll now){
	dis[u]=now;vis[u]=1;
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(!vis[v]){
			dfs(v,now^e[i].v);
		}else{
			insert(now^e[i].v^dis[v]);
		}
	}
}
ll query(ll x){
	for(int i=MAXL;i>=0;--i){
		if((x^a[i])>x){
			x^=a[i];
		}
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;ll d;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&d);
		build(a,b,d);
		build(b,a,d);
	}
	dfs(1,0);
	printf("%lld",query(dis[n]));
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

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
#include<bits/stdc++.h>
using namespace std;

const int N=105;
int a[40],d[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
	}
	sort(d+1,d+n+1,greater<int>());
	long long ans=0;
	for(int i=1;i<=n;++i){
		int t=d[i];
		for(int j=31;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				a[j]=t;
				break;
			}
		}
		if(!t) ans+=d[i];
	}
	printf("%lld",ans);
	return 0;
}

P3292 [SCOI2016]幸运数字

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
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=20000+5,MAXL=61;
struct Edge{
	int t,n;
}e[N<<1];
int hd[N],cnt;
inline void build(int f,int t){
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}
struct Lbasis{//Linear Basis 
	ll a[MAXL+1];
	Lbasis(){memset(a,0,sizeof a);}
	Lbasis(const Lbasis& b){memcpy(a,b.a,sizeof a);} 
	void insert(ll t){
		for(int j=MAXL;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				for(int k=0;k<j;++k){
					if((t>>k)&1) t^=a[k];
				}
				for(int k=j+1;k<=MAXL;++k){
					if((a[k]>>j)&1){
						a[k]^=t;
					}
				}
				a[j]=t;
				return;
			}
		}
	}
	void merge(const Lbasis &b){
		for(int i=MAXL;i>=0;--i){
			if(b.a[i]){
				insert(b.a[i]);
			}
		}
	}
	ll max(){
		ll res=0;
		for(int i=0;i<=MAXL;++i){
			res^=a[i];
		}
		return res;
	}
}b[20][N];
int dep[N],anc[20][N];
ll val[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	anc[0][u]=f;
	b[0][u].insert(val[u]);
	for(int i=1;anc[i-1][u];++i){
		anc[i][u]=anc[i-1][anc[i-1][u]];
		b[i][u]=b[i-1][u];
		b[i][u].merge(b[i-1][anc[i-1][u]]);
	}
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(v==f) continue;
		dfs(v,u);
	}
}
ll ask(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dd=dep[x]-dep[y];
	Lbasis res;
	for(int i=19;i>=0;--i){
		if(dd&(1<<i)){
			res.merge(b[i][x]);
			x=anc[i][x];
		}
	}
	if(x==y){
		res.insert(val[x]);
		return res.max();
	}
	for(int i=19;i>=0;--i){
		if(anc[i][x]!=anc[i][y]){
			res.merge(b[i][x]);res.merge(b[i][y]);
			x=anc[i][x];y=anc[i][y];
		}
	}
	res.insert(val[x]);res.insert(val[y]);res.insert(val[anc[0][x]]);
	return res.max();
}
int n;
int main(){
	int q;
	scanf("%d%d",&n,&q);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		build(a,b);build(b,a);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",ask(x,y));
	}
	return 0;
}

发表于 更新于 分类于

10.3

Codeforces Round #746 (Div. 2)

A

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[10000];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,h;
		scanf("%lld%lld",&n,&h);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		sort(a+1,a+n+1,greater<int>());
		ll t=floor(1.0*h/(a[1]+a[2]));
		if(t*(a[1]+a[2])==h){
			printf("%lld\n",t<<1);
		}else if(t*(a[1]+a[2])+a[1]>=h){
			printf("%lld\n",(t<<1)+1);
		}else{
			printf("%lld\n",(t<<1)+2);
		}
	}
	return 0;
}

B

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N],b[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,x;
		scanf("%d%d",&n,&x);
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			b[i]=a[i];
		}
		sort(b+1,b+n+1);
		bool f=1;
		for(int i=1;i<=n;++i){
			if(i+x>n&&i-x<1){
				if(a[i]!=b[i]){
					f=0;
					break;
				}
			}
		}
		puts(f?"YES":"NO");
	}
	return 0;
}

C

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
vector<int> G[N];
int t[N],sm,a[N];

int dfs(int u,int fa){
	t[u]=a[u];
	for(int v:G[u]){
		if(v==fa) continue;
		t[u]^=dfs(v,u);
	}
	return t[u];
}
bool flag;
void find(int u,int fa){
	for(int v:G[u]){
		if(v==fa) continue;
		find(v,u);
		if(t[v]==sm&&!flag){
			flag=1;
			G[u].erase(find(G[u].begin(),G[u].end(),v));
			return;
		}
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,kk;
		scanf("%d%d",&n,&kk);
		sm=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			sm^=a[i];
		}
		for(int i=1;i<n;++i){
			int x,y;
			scanf("%d%d",&x,&y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		if(sm==0){
			puts("YES");
		}
		else if(kk==2){
			puts("NO");
		}
		else{
			dfs(1,0);
			find(1,0);
			if(flag){
				flag=0;
				dfs(1,0);
				find(1,0);
				if(flag){
					puts("YES");
				}else{
					puts("NO");
				}
			}else{
				puts("NO");
			}
			
		}
		for(int i=1;i<=n;++i){
			G[i].clear();
		}
	}
	return 0;
}

10.4

Lindström–Gessel–Viennot lemma，可以用来处理$ $上不相交路径计数等问题。

\(\omega(P)\) 表示 \(P\) 这条路径上所有边的边权之积。（路径计数时，可以将边权都设为 \(1\)）（事实上，边权可以为生成函数）

\(e(u, v)\) 表示 \(u\) 到 \(v\) 的$ $ \(P\) 的 \(\omega(P)\) 之和，即 \(e(u, v)=\sum\limits_{P:u\rightarrow v}\omega(P)\)。

起点集合 \(A\)，是有向无环图点集的一个子集，大小为 \(n\)。

终点集合 \(B\)，也是有向无环图点集的一个子集，大小也为 \(n\)。

一组 \(A\rightarrow B\) 的不相交路径 \(S\)：\(S_i\) 是一条从 \(A_i\) 到 \(B_{\sigma(S)_i}\) 的路径（\(\sigma(S)\) 是一个排列），对于任何 \(i\ne j\)，\(S_i\) 和 \(S_j\) 没有公共顶点。

\(N(\sigma)\) 表示排列 \(\sigma\) 的逆序对个数。

\[ M = \begin{bmatrix}e(A_1,B_1)&e(A_1,B_2)&\cdots&e(A_1,B_n)\\ e(A_2,B_1)&e(A_2,B_2)&\cdots&e(A_2,B_n)\\ \vdots&\vdots&\ddots&\vdots\\ e(A_n,B_1)&e(A_n,B_2)&\cdots&e(A_n,B_n)\end{bmatrix} \]

\[ \det(M)=\sum\limits_{S:A\rightarrow B}(-1)^{N(\sigma(S))}\prod\limits_{i=1}^n \omega(S_i) \]

其中 \(\sum\limits_{S:A\rightarrow B}\) 表示满足上文要求的 \(A\rightarrow B\) 的每一组不相交路径 \(S\)。

路径计数时，\(\omega(S_i)=1\),故\(\prod\limits_{i=1}^n \omega(S_i)=1\)。

例题题意：有一个 \(n\times n\) 的棋盘，棋子只能向下向右走，有 \(m\) 个棋子，一开始第 \(i\) 个棋子放在 \((1, a_i)\)，最终要到 \((n, b_i)\)，路径要两两不相交，求方案数。

观察到如果路径不相交就一定是 \(a_i\) 到 \(b_i\)，因此 LGV 引理中一定有 \(\sigma(S)_i=i\)，不需要考虑符号问题。边权设为 \(1\)，直接套用引理即可。

从 \((1, a_i)\) 到 \((n, b_j)\) 的路径条数相当于从 \(n-1+b_j-a_i\) 步中选 \(n-1\) 步向下走，所以 \(e(A_i, B_j)=\binom{n-1+b_j-a_i}{n-1}\)。

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
const int M=105,N=2e6+6;
ll fact[N],mt[M][M],a[M],b[M];
const ll mod=998244353;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;return;
    }
    exgcd(b,a%b,x,y);
    ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a){
    ll x,y;
    exgcd(a,mod,x,y);
    return (x+mod)%mod;
}
ll C(ll n,ll m){
    return fact[n]*inv(fact[m])%mod*inv(fact[n-m])%mod;
}
int main(){
    int T;scanf("%d",&T);
    fact[0]=1;
    for(int i=1;i<N;++i){
        fact[i]=(fact[i-1]*i)%mod;
    }
    while(T--){
        ll n,m;
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%lld%lld",&a[i],&b[i]);//(ai,1)->(bi,n)
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=m;++j){
                if(a[i]<=b[j]){
                    mt[i][j]=C(n-1+b[j]-a[i],n-1);
                }else{
                    mt[i][j]=0;
                }
            }
        }
        ll ans=1;
        for(int i=1;i<=m;++i){
            for(int j=i+1;j<=m;++j){
                while(mt[j][i]){
                    ll t=mt[i][i]/mt[j][i];
                    for(int k=i;k<=m;++k){
                        mt[i][k]=(mt[i][k]-t*mt[j][k]%mod+mod)%mod;
                        swap(mt[i][k],mt[j][k]);
                    }
                    ans=mod-ans;
                }
            }
            ans=ans*mt[i][i]%mod;
        }
        printf("%lld\n",(ans+mod)%mod);
    }
    return 0;
}

10.5

P5905【模板】Johnson 全源最短路

用于处理$ \(的多源最短路问题。套用斐波那契堆优化的Dijkstra时间复杂度为\)O(V^2logV+VE)\(,套用二叉堆优化的Dijkstra时间复杂度\)O(VElogE)$。

（稠密图\(V^2\approx E\)，使用Floyd算法即可，无负边权直接做\(V\)次Dijkstra。）

设虚拟结点，与其他点建边权为0的边，从虚拟结点跑spfa得\(h_i\)，重建图赋值\((u, v)\)边权\(w(u, v)\)为\(w(u, v)+h_u-h_v\)，这保证了最短路径不变而且所有权重均非负，跑n次Dijkstra求最短路，算法求得距离为\(dis(s, t)\)，非不可达点的实际距离为\(dis(s, t)-(h_s-h_t)\)。

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
const int M=6e3+5,N=3e3+5,inf=1e9;
struct Edge{
    int t,n,v;
}e[M+N];
int hd[N];
int cnt,n,m;
inline void build(int f,int t,int v){
    e[++cnt]=(Edge){t,hd[f],v};
    hd[f]=cnt;
}
bool inq[N],vis[N];
int h[N],t[N];
bool spfa(){
    static queue<int> q;
    q.push(0);//虚拟结点定为0 
    h[0]=0;inq[0]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        inq[u]=0;
        for(int i=hd[u];i;i=e[i].n){
            int v=e[i].t;
            if(h[v]>h[u]+e[i].v){
                h[v]=h[u]+e[i].v;
                if(!inq[v]){
                    ++t[v];
                    if(t[v]==n+1) return 0;//入队n+1次，有负环 
                    q.push(v);
                    inq[v]=1;
                }
            }
        }
    }
    return 1;
}
int dis[N][N];
bool cho[N];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
void dij(int S){
    for(int i=1;i<=n;++i){
        dis[S][i]=inf;
        cho[i]=0;
    }
    dis[S][S]=0;
    q.push(pii(0,S));
    while(!q.empty()){
        pii t=q.top();
        q.pop();
        int u=t.second;
        if(cho[u]) continue;
        cho[u]=1;
        for(int i=hd[u];i;i=e[i].n){
            int v=e[i].t;
            if(dis[S][v]>dis[S][u]+e[i].v){
                dis[S][v]=dis[S][u]+e[i].v;
                q.push(pii(dis[S][v],v));
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int a,b,v;
        scanf("%d%d%d",&a,&b,&v);
        build(a,b,v);
    }
    for(int i=1;i<=n;++i){
        h[i]=inf;
        build(0,i,0);//虚拟结点到其他点建边权为0的边 
    }
    if(!spfa()){
        puts("-1");
        return 0;
    }
    for(int u=1;u<=n;++u){
        for(int i=hd[u];i;i=e[i].n){
            e[i].v+=h[u]-h[e[i].t];
        }
    }
    for(int i=1;i<=n;++i){
        dij(i);
    }
    for(int i=1;i<=n;++i){
        long long ans=0;
        for(int j=1;j<=n;++j) ans+=(long long)j*(dis[i][j]-(dis[i][j]==inf?0:(h[i]-h[j])));
        printf("%lld\n",ans);
    }
    return 0;
}

10.7

$ \(:给定域\)F\(，\)F\(上的向量空间\)V$是一个集合，其上定义加法和数乘运算且这两个运算满足八个公理。

$ \(:对于向量空间中\)V\(上\)n\(个元素的向量组\)(_1, , _n)$,若存在不全为\(0\)的数\(a_i \in F\)满足 \[ a_{1}\mathbf{v}_{1}+a_{2}\mathbf {v}_{2}+\ldots +a_{n}\mathbf{v}_{n} = 0 \]

则称这\(n\)个向量线性相关（linearly dependent），否则称为线性无关（linearly independent）。

$ \(:对于向量空间中 VV 上 nn 个元素的向量组\)(_1, , _n)$，其线性组合（linear combination）是如下形式的向量

\[ a_{1}\mathbf{v}_{1} + a_{2}\mathbf {v} _{2}+\ldots +a_{n}\mathbf {v} _{n} \] ​​ 其中\(a_1, \ldots, a_n \in F\)

一组向量线性无关 \(\Leftrightarrow\)没有向量可用有限个其他向量的线性组合所表示

$ $:对于向量空间中 \(V\) 上 \(n\) 个元素的向量组 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)，其所有线性组合所构成的集合称为 \((\mathbf{v}_1, \ldots, \mathbf{v}_n)\)的张成（span），记为 \(\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)\)

$ $:若向量空间 \(V\) 中向量组 \(\mathfrak{B}\) 既是线性无关的又可以张成 \(V\)，则称其为\(V\) 的基（basis）。

\(\mathfrak{B}\)中的元素称为基向量。如果基中元素个数有限，就称向量空间为有限维向量空间，将元素的个数称作向量空间的维数。

设 \(\mathfrak {B}\) 是向量空间 \(V\) 的基。则\(\mathfrak {B}\)具有以下性质：

1.\(V\) 是 \(\mathfrak {B}\)的极小生成集，就是说只有\(\mathfrak {B}\)能张成\(V\)，而它的任何真子集都不张成全部的向量空间。

2.\(\mathfrak {B}\) 是 \(V\) 中线性无关向量的极大集合，就是说 \(\mathfrak {B}\) 在\(V\) 中是线性无关集合，而且\(V\) 中没有其他线性无关集合包含它作为真子集。

3.\(V\) 中所有的向量都可以按唯一的方式表达为\(\mathfrak {B}\) 中向量的线性组合。

$ $

对于数 \(a_0, a_1, \ldots, a_n\)，将 \(a_i\)的二进制表示$ (b_{m}b_0)_2$​ 看作一个向量。向量组 \(\mathbf{a}_1, \ldots, \mathbf{a}_n\)可以张成一个向量集合 \(\mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n)\)，加上我们的异或运算和乘法运算（显然满足 8 条公理），即可形成一个向量空间 \(V = (\{0, 1\}, \mathrm{span}(\mathbf{a}_1, \ldots, \mathbf{a}_n), \oplus, \cdot)\)

设集合\(S\)中最大的数在二进制意义下有\(L\)位，我们使用一个 \([0\dots L]\)的数组\(a\)来储存线性基。

这种线性基的构造方法保证了一个特殊性质，对于每一个\(i\),\(a_i\)有以下两种可能：

（如果排成矩阵，形成一个下三角矩阵）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
const int MAXL=60;
ll a[MAXL+1];int lbsiz;
void insert(ll t){//高斯消元解出的对角矩阵的非零行构成的向量组 
    for(int j=MAXL;j>=0;--j){// 逆序枚举二进制位
        if(!((t>>j)&1)) continue;// 如果 t 的第 j 位为 0，则跳过
        if(a[j]) t^=a[j];
        else{// 找到可以插入 a[j] 的位置
            // 用 a[0...j - 1] 消去 t 的第 [0, j) 位上的 1
// 如果某一个a[k]=0也无须担心，因为这时候第k位不存在于线性基中，不需要保证t的第k位为 0	
            for(int k=0;k<j;++k) if((t>>k)&1) t^=a[k];
            // 用 t 消去 a[j + 1...L] 的第 j 位上的 1
            for(int k=j+1;k<=MAXL;++k) if((a[k]>>j)&1) a[k]^=t;
                // 插入到 a[j] 的位置上
            a[j]=t;++lbsiz;
            return;// 不要忘记，结束插入过程
        }
    }
}

最大异或和：将线性基中所有向量异或起来得到的向量所对应的数。

1
2
3
4
5
ll querymax(){
    ll res=0;
    for(int i=0;i<=MAXL;++i) res^=a[i];
    return res;
}

集合任选大于1个元素异或出的第k大数

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
vector<ll> v;
bool zero;int n;//zero: 是否能异或出0
void init(){
    lbsiz=0;
    v.clear();
    memset(a,0,sizeof a);
}
void prepare(){
    zero=(lbsiz!=n);
    for(int i=0;i<=MAXL;++i){
        if(a[i]) v.push_back(a[i]);
    }
}
ll query(ll k){
    if(zero) --k;
    if(k>=(1ll<<v.size())) return -1;
    ll res=0;
    for(int i=MAXL;i>=0;--i) if((k>>i)&1) res^=v[i];
    return res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int ttt=1;ttt<=T;++ttt){
        init();
        scanf("%d",&n);ll t;
        for(int i=1;i<=n;++i){
            scanf("%lld",&t);
            insert(t);
        }
        prepare();
        printf("Case #%d:\n",ttt);
        int q;scanf("%d",&q);
        while(q--){
            scanf("%lld",&t);
            printf("%lld\n",query(t));
        }
    }
    return 0;
}

10.8

P4151 [WC2011]最大XOR和路径

异或路径问题：转化成任意一条路径，和任意个圈的异或。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int M=200000+5,N=50000+5,MAXL=60;
struct Edge{
	int t,n;
	ll v;
}e[M];
int hd[N],cnt;
inline void build(int f,int t,ll v){
	e[++cnt]=(Edge){t,hd[f],v};
	hd[f]=cnt;
}
ll a[MAXL+3],dis[N];
bool vis[N];
void insert(ll t){
	for(int j=MAXL;j>=0;--j){
		if(!((t>>j)&1)) continue;
		if(a[j]) t^=a[j];
		else{
			for(int k=0;k<j;++k){
				if((t>>k)&1) t^=a[k];
			}
			for(int k=j+1;k<=MAXL;++k){
				if((a[k]>>j)&1){
					a[k]^=t;
				}
			}
			a[j]=t;
			return;
		}
	}
}
int n,m;
void dfs(int u,ll now){
	dis[u]=now;vis[u]=1;
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(!vis[v]){
			dfs(v,now^e[i].v);
		}else{
			insert(now^e[i].v^dis[v]);
		}
	}
}
ll query(ll x){
	for(int i=MAXL;i>=0;--i){
		if((x^a[i])>x){
			x^=a[i];
		}
	}
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	int a,b;ll d;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&d);
		build(a,b,d);
		build(b,a,d);
	}
	dfs(1,0);
	printf("%lld",query(dis[n]));
	return 0;
}

P4301 [CQOI2013] 新Nim游戏

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
#include<bits/stdc++.h>
using namespace std;

const int N=105;
int a[40],d[N];

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&d[i]);
	}
	sort(d+1,d+n+1,greater<int>());
	long long ans=0;
	for(int i=1;i<=n;++i){
		int t=d[i];
		for(int j=31;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				a[j]=t;
				break;
			}
		}
		if(!t) ans+=d[i];
	}
	printf("%lld",ans);
	return 0;
}

P3292 [SCOI2016]幸运数字

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
99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=20000+5,MAXL=61;
struct Edge{
	int t,n;
}e[N<<1];
int hd[N],cnt;
inline void build(int f,int t){
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}
struct Lbasis{//Linear Basis 
	ll a[MAXL+1];
	Lbasis(){memset(a,0,sizeof a);}
	Lbasis(const Lbasis& b){memcpy(a,b.a,sizeof a);} 
	void insert(ll t){
		for(int j=MAXL;j>=0;--j){
			if(!((t>>j)&1)) continue;
			if(a[j]) t^=a[j];
			else{
				for(int k=0;k<j;++k){
					if((t>>k)&1) t^=a[k];
				}
				for(int k=j+1;k<=MAXL;++k){
					if((a[k]>>j)&1){
						a[k]^=t;
					}
				}
				a[j]=t;
				return;
			}
		}
	}
	void merge(const Lbasis &b){
		for(int i=MAXL;i>=0;--i){
			if(b.a[i]){
				insert(b.a[i]);
			}
		}
	}
	ll max(){
		ll res=0;
		for(int i=0;i<=MAXL;++i){
			res^=a[i];
		}
		return res;
	}
}b[20][N];
int dep[N],anc[20][N];
ll val[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	anc[0][u]=f;
	b[0][u].insert(val[u]);
	for(int i=1;anc[i-1][u];++i){
		anc[i][u]=anc[i-1][anc[i-1][u]];
		b[i][u]=b[i-1][u];
		b[i][u].merge(b[i-1][anc[i-1][u]]);
	}
	for(int i=hd[u];i;i=e[i].n){
		int v=e[i].t;
		if(v==f) continue;
		dfs(v,u);
	}
}
ll ask(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	int dd=dep[x]-dep[y];
	Lbasis res;
	for(int i=19;i>=0;--i){
		if(dd&(1<<i)){
			res.merge(b[i][x]);
			x=anc[i][x];
		}
	}
	if(x==y){
		res.insert(val[x]);
		return res.max();
	}
	for(int i=19;i>=0;--i){
		if(anc[i][x]!=anc[i][y]){
			res.merge(b[i][x]);res.merge(b[i][y]);
			x=anc[i][x];y=anc[i][y];
		}
	}
	res.insert(val[x]);res.insert(val[y]);res.insert(val[anc[0][x]]);
	return res.max();
}
int n;
int main(){
	int q;
	scanf("%d%d",&n,&q);
	int a,b;
	for(int i=1;i<=n;++i){
		scanf("%lld",&val[i]);
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&a,&b);
		build(a,b);build(b,a);
	}
	dfs(1,0);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%lld\n",ask(x,y));
	}
	return 0;
}

10.9

Codeforces Round #747 (Div. 2)

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n;
		scanf("%lld",&n);
		printf("%lld %lld\n",-(n-1),n);
	}
	return 0;
}

B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		ll n,k;
		scanf("%lld%lld",&k,&n);
		ll ans=0,pw=1;
		while(n){
			if(n&1){
				ans=(ans+pw)%mod;
			}
			pw=(pw*k)%mod;
			n>>=1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C

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
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
char s[N];

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n;char tar[5];
		scanf("%d%s%s",&n,tar,s+1);
		char c=tar[0];
		bool eq=1;
		for(int i=1;i<=n;++i){
			if(c!=s[i]){
				eq=0;
				break;
			}
		}
		if(eq){
			puts("0");
			continue;
		}
		int ans=-1;
		for(int i=2;i<=n;++i){
			bool f=1;
			for(int j=i;j<=n;j+=i){
				if(s[j]!=c){
					f=0;
					break;
				}
			}
			if(f){
				ans=i;
				break;
			}
		}
		if(ans!=-1){
			printf("1\n%d\n",ans);
		}else{
			printf("2\n%d %d\n",n-1,n);
		}
	}
	return 0;
}

E1

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7,p=mod;
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
	    x=1,y=0;return;
	}
	exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
}
ll inv(ll a){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
} 
ll iv;
ll f(ll n){
	if(n==1) return 6;
	ll t=f(n-1)*iv%mod;
	return t*t%mod*96ll%mod;
}

int main(){
	ll n;
	iv=inv(6);
	cin>>n;
	cout<<f(n);
	return 0;
}

E2

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

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll p){
    ll ans=1;
    a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}
int color[10][10]={{1,2,4,5},{0,2,3,5},{0,1,3,4},{1,2,4,5},{0,2,3,5},{0,1,3,4}};
map<ll,int> label;
ll dp[7][(60*10000)+5];
int c[(60*10000)+5];
vector<vector<int> > G;
ll dfs(int u,int cl){
	if(c[u]!=-1&&c[u]!=cl){
		return 0;
	}
	if(~dp[cl][u]){
		return dp[cl][u];
	}
	if(G[u].empty()){
		return dp[cl][u]=1;
	}
	ll sum[2]={0,0};
	for(int i=0;i<4;++i){
		for(int j=0;j<G[u].size();++j){
			sum[j]=(sum[j]+dfs(G[u][j],color[cl][i]))%mod;
		}
	}
	if(G[u].size()==1){
		sum[1]=1;
	}
	return dp[cl][u]=(sum[0]*sum[1])%mod;
}
int main(){
    map<string,ll>mp;
    mp["white"] = 0;
    mp["blue"] = 1;
    mp["red"] = 2;
    mp["yellow"] = 3;
    mp["green"] = 4;
    mp["orange"] = 5;
    ll k,n;cin>>k>>n;
    map<ll,int> ar;
    ll totno=(1ll<<k)-1;
    int lab=0;
    for(int i=1;i<=n;++i){
    	ll x;string s;
    	cin>>x>>s;
    	ar[x]=mp[s];
    	ll cur=x;
    	while(cur>=1&&!label.count(cur)){
    		label[cur]=++lab;
    		--totno;
    		cur/=2;
    	}
    }
    memset(dp,-1,sizeof dp);
    memset(c,-1,sizeof c);
    G.assign(lab+5,vector<int>());
    for(auto x:label){
    	if(ar.count(x.first)){
    		c[x.second]=ar[x.first];
    	}
    	if(label.count(x.first<<1)){
    		G[x.second].push_back(label[x.first<<1]);
    	}
    	if(label.count(x.first<<1|1)){
    		G[x.second].push_back(label[x.first<<1|1]);
    	}
    }
    ll ans=0;
    for(int i=0;i<6;++i)
    	ans=(ans+dfs(label[1],i))%mod;
    ans=(ans*qpow(4,totno))%mod;
    cout<<ans;
	return 0;
}

发表于 更新于 分类于

有多少整数\(b\in [0,h)\),使得\(\sum\limits_{i=1}^{n}a_ix_i=b\)有非负整数解。

令\(dis_i\)表示最小的符合\((\sum\limits_{i=1}^{n}a_ix_i)\space mod\space a_k=i(\forall k \in[1.n])\)的\(\sum\limits_{i=1}^{n}a_ix_i\), 则\(i+t\cdot a_k,\forall t \in \mathbb{N}\)都有解。

\(\forall i \in [0,a_k)\),\(\forall j\in[1,n],j\neq k\)建边\((i,(i+a_j)mod\space a_k)\),边权为\(a_j\), 从0开始跑最短路可求\(dis_i\),\(a_k\)取\(a_1...a_n\)中最小的可保证建边最少运行最快。

\[ ans=\sum\limits_{i=1}^{n}(\lfloor\frac{h-dis_i}{a_k}\rfloor+1) \]

Luogu P3403 跳楼机

题意为: 给定 h,x,y,z，对于 k∈[1,h]，有多少个 k 满足 ax+by+cz=k

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int cnt,hd[N];
struct Edge{
	int t,v,n;
}e[N*20];
typedef long long ll;
void build(int f,int t,int v){
	e[++cnt]=(Edge){t,v,hd[f]};
	hd[f]=cnt;
}
queue<int> q;
bool inq[N];
ll dis[N];
int main(){
	ll h,x,y,z;
	scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
	--h;
	for(int i=0;i<x;++i){
		build(i,(i+y)%x,y);
		build(i,(i+z)%x,z);
	}
	for(int i=0;i<N;++i){
		dis[i]=2e18;
	}
	q.push(0);
	dis[0]=0;
	inq[0]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=hd[u];i;i=e[i].n){
			int v=e[i].t;
			if(dis[v]>dis[u]+e[i].v){
				dis[v]=dis[u]+e[i].v;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	unsigned long long ans=0;
	for(int i=0;i<x;++i){
		if(dis[i]<=h)
			ans+=(h-dis[i])/x+1;
	}
	printf("%llu\n",ans);
	return 0;
}

墨墨突然对等式很感兴趣，他正在研究 \(\sum_{i=1}^n a_ix_i=b\)存在非负整数解的条件，他要求你编写一个程序，给定 \(n, a_{1\dots n}, l, r\),求出有多少\(b\in[l,r]\)可以使等式存在非负整数解。

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
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int cnt,hd[N];
struct Edge{
	int t,v,n;
}e[N*24];
typedef long long ll;
void build(int f,int t,int v){
	e[++cnt]=(Edge){t,v,hd[f]};
	hd[f]=cnt;
}
queue<int> q;
bool inq[N];
ll dis[N],a[20];
int main(){
	ll n,l,r;
	scanf("%lld%lld%lld",&n,&l,&r);
	l--;
	ll mn=1e18,k=-1;
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		if(a[i]<mn){
			k=i;
			mn=a[i];
		}
	}
	for(int i=0;i<mn;++i){
		for(int j=1;j<=n;++j){
			if(j!=k){
				build(i,(i+a[j])%mn,a[j]);
			}
		}
	}
	for(int i=0;i<N;++i){dis[i]=2e18;}
	q.push(0);
	dis[0]=0;
	inq[0]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=hd[u];i;i=e[i].n){
			int v=e[i].t;
			if(dis[v]>dis[u]+e[i].v){
				dis[v]=dis[u]+e[i].v;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	unsigned long long al=0,ar=0;
	for(int i=0;i<mn;++i){
		if(dis[i]<=r){
			ar+=(r-dis[i])/mn+1;
			if(dis[i]<=l){
				al+=(l-dis[i])/mn+1;
			}
		}
	}
	printf("%llu\n",ar-al);
	return 0;
}

发表于 更新于 分类于

\(O(n^2v)\)算法

用\(f(i,j)\)表示以位置i结尾，公差为j的等差数列有多少个。

转移的时候，枚举一个小于i的k，满足\(h_k+j= h_i\)

由f(k,j)转移到\(f(i,j)\)

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
#include<bits/stdc++.h>
using namespace std;

const int N=1000+5;
int a[N],f[N][40005];
const int ofs=20001,mod=998244353;

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int ans=0;
	for(int i=2;i<=n;++i){
		for(int j=-20001;j<=20001;++j){
			for(int k=1;k<i;++k){
				if(a[k]+j==a[i]){
					f[i][j+ofs]=(f[i][j+ofs]+f[k][j+ofs]+1)%mod;
				//	printf("%d %d %d\n",a[k],a[i],f[i][j+ofs]);
				}
			}
			ans=(ans+f[i][j+ofs])%mod;
		}
	}
	printf("%d",(ans+n)%mod);
	return 0;
}

\(O(nv)\)

注意到前两重循环交换后不影响结果正确性。我们此时先枚举公差j。

考虑之前\(O(n^2v)\)的算法转移的时候枚举一个小于i的k，然后当\(h_k = h_i- j\)的时候从\(f(k,j)\)转移到\(f(i,j)\)。

我们发现，转移相当于一个求和，对小于i的所有高度等于\(h_i-j\)的位置的\(f\)值求和。

令\(g(t)\)为\(\sum\limits_{1\leq k<i,h_k-j=t}f(k,j)\)

其含义为\(h_1\)到\(h_{i-1}\)，有多少高度为t结尾的等差数列。

在转移时，\(f(i)=g(h_i-j)\),同时维护g的值，\(g(h_i)+=f(i)\)

每次状态转移由\(O(n)\)优化到\(O(1)\)

对之前的代码稍作修改可通过该题,\(O(nv)\)，如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

const int N=1000+5;
int a[N],f[N][100005],g[100005];
const int ofs=40001,mod=998244353;

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int ans=0;
	for(int j=-20001;j<=20001;++j){
		memset(g,0,sizeof g);
		for(int i=1;i<=n;++i){
			f[i][j+ofs]=(f[i][j+ofs]+/*f[k][j+ofs]+1*/g[a[i]-j+ofs])%mod;
			g[a[i]+ofs]=(g[a[i]+ofs]+f[i][j+ofs]+1)%mod;
			ans=(ans+f[i][j+ofs])%mod;
		}
	}
	printf("%d",(ans+n)%mod);
	return 0;
}

简单优化冗余

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
#include<bits/stdc++.h>
using namespace std;

const int N=1000+5;
int a[N],f[N],g[80005];
const int ofs=40001,mod=998244353;

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int ans=0;
	for(int j=-20001;j<=20001;++j){
		memset(g,0,sizeof g);
		memset(f,0,sizeof f);
		for(int i=1;i<=n;++i){
			f[i]=g[a[i]-j+ofs]%mod;
			g[a[i]+ofs]=(g[a[i]+ofs]+f[i]+1)%mod;
			ans=(ans+f[i])%mod;
		}
	}
	printf("%d",(ans+n)%mod);
	return 0;
}

真·正解 \(O(n^2)\)

出题人想复杂了，枚举公差不必。

枚举之前的数，作差得到公差即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

const int N=1000+5;
int a[N],f[N][80005];
const int ofs=40001,mod=998244353;

int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int ans=0;
	for(int i=2;i<=n;++i){
		for(int j=1;j<i;++j){
			int d=a[j]-a[i];
			f[i][d+ofs]+=f[j][d+ofs]+1;
			f[i][d+ofs]%=mod;
			ans=(ans+f[j][d+ofs]+1)%mod;
		}
	}
	printf("%d",(ans+n)%mod);
	return 0;
}

发表于 更新于 分类于

用作处理随机数据，具有区间赋值操作的序列操作问题 把值相同的区间合并成一个结点保存在 set 里面。 对于add，assign 和 sum 操作，用 set 实现的珂朵莉树的复杂度为\(O(nloglogn)\)，而用链表实现的复杂度为\(O(nlog)\)。 

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
typedef long long ll;
struct Node{
  ll l, r;//闭区间！
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值，作为时间复杂度保证
	auto itr=split(r+1),itl=split(l);//进行求取区间左右端点操作时，必须先 split 右端点，再 split 左端点。若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，可能会导致 RE。
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
//其他的操作，每块都操作（暴力）
void do_sth(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		//do something
	}
}
//例如，区间加
void add(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v+=v;	
	}
}
//例如，区间第k小的是几
ll kth(ll l,ll r,ll k){
	vector<pair<ll,ll> > v;
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		v.push_back(make_pair(itl->v,itl->r-itl->l+1));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();++i){
		k-=v[i].second;
		if(k<=0) return v[i].first;
	}
}
int main(){
	for(ll i=1;i<=n;++i){//区间初始化
        ll x;scanf("%lld",&x);
		odt.insert(Node(i,i,x));
	}
	return 0;
}
Willem, Chtholly and Seniorious

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
99
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
struct Node{
  ll l, r;
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值 
	auto itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
void add(ll l,ll r,ll v){
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v+=v;	
	}
}
ll seed;
ll kth(ll l,ll r,ll k){
	vector<pair<ll,ll> > v;
	auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		v.push_back(make_pair(itl->v,itl->r-itl->l+1));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();++i){
		k-=v[i].second;
		if(k<=0) return v[i].first;
	}
}
int rnd(){
	int ret(seed);
	seed=(seed * 7 + 13)%1000000007;
    return ret;
}
ll qpow(ll a,ll p,ll mod){
    ll ans=1;
	a%=mod;
    while(p){
        if(p&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        p>>=1;
    }
    return ans%mod;
}
ll ask(ll l,ll r,ll x,ll y){
	auto itr=split(r+1),itl=split(l);
	ll ret=0;
	for(;itl!=itr;++itl) {
		ret=(ret+(itl->r-itl->l+1)*qpow(itl->v,x,y))%y;
	}
	return ret;
}
int main(){
	ll m,vmax;
	scanf("%lld%lld%lld%lld",&n,&m,&seed,&vmax);
	for(ll i=1;i<=n;++i){
		ll r=rnd();
		odt.insert(Node(i,i,(r%vmax)+1));
	}
	for(ll i=1;i<=m;++i){
		ll op=(rnd()%4)+1;
		ll l=rnd()%n+1;
		ll r=rnd()%n+1;
		if(l>r) swap(l,r);
		ll x;
		if(op==3){x=rnd()%(r-l+1)+1;}else{x=(rnd()%vmax)+1;}
		if(op==1){
			add(l,r,x);
		}else if(op==2){
			assign(l,r,x);
		}else if(op==3){
			printf("%lld\n",kth(l,r,x));
		}else if(op==4){
			ll y=rnd()%vmax+1;
			printf("%lld\n",ask(l,r,x,y));
		}
	}
	return 0;
}

BZOJ1858

0 l r 把 [l, r]区间内的所有数全变成 0

1 l r 把 [l, r] 区间内的所有数全变成 1

2 l r 把 [l,r] 区间内的所有数全部取反，也就是说把所有的 0 变成 1，把所有的 1 变成 0

3 l r 询问 [l, r] 区间内总共有多少个 1

4 l r 询问 [l, r] 区间内最多有多少个连续的 1 

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
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
struct Node{
  ll l, r;//闭区间！
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(ll x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l, ll r, ll v){//区间赋值 
	auto itr=split(r+1),itl=split(l);
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
void flipv(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) {
		itl->v^=1;
	}
}
ll ask1(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
    ll ret=0;
	for(;itl!=itr;++itl) {
		if(itl->v==1){
            ret+=itl->r-itl->l+1;
        }
	}
    return ret;
}
ll ask2(ll l,ll r){
    auto itr=split(r+1),itl=split(l);
    ll ret=0,pre=0;
	for(;itl!=itr;++itl) {
		if(itl->v==1){
            ret=max(ret,pre=pre+itl->r-itl->l+1);
        }else{
            pre=0;
        }
	}
    return ret;
}
void getint(int &x){
    char c;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0';
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    int pos=1,val;
    getint(val);
	for(int i=2;i<=n;++i){//区间初始化
        ll x;getint(x);
        if(x!=val){
		    odt.insert(Node(pos,i-1,val));
            pos=i;
            val=x;
        }
	}
    odt.insert(Node(pos,n,val));
    while(m--){
        ll op,l,r;
        getint(op);getint(l);getint(r);
        ++l,++r;
        if(op<=1){
            assign(l,r,op);
        }else if(op==2){
            flipv(l,r);
        }else if(op==3){
            printf("%d\n",ask1(l,r));
        }else if(op==4){
            printf("%d\n",ask2(l,r));
        }
    }
	return 0;
}

luogu P4979

assign 操作需要优化才能通过 

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;

typedef int ll;
struct Node{
  ll l, r;
  mutable ll v;//mutable让我们可以在后面的操作中修改 v 的值
  //可以直接修改已经插入 set 的元素的 v 值，而不用将该元素取出后重新加入 set
  Node(const ll &il, const ll &ir, const ll &iv):l(il),r(ir),v(iv){}
  bool operator < (const Node &o)const{return l<o.l;}
};
set<Node> odt;
//包含点 x的区间（设为 [l,r)）分裂为两个区间[l,x)和[x,r)并返回指向后者的迭代器
ll n;
auto split(const ll &x) {
	if (x>n) return odt.end();
	auto it=--odt.upper_bound((Node){x, 0, 0});
	if(it->l==x) return it;
	ll l=it->l,r=it->r,v=it->v;
	odt.erase(it);
	odt.insert(Node(l,x-1,v));
	return odt.insert(Node(x,r,v)).first;
} 
void assign(ll l,ll r,const ll &v){//区间赋值 
    set<Node>::iterator itr;
    if(r==n){
        itr=odt.end();
    }else{
        itr=--odt.upper_bound((Node){r+1, 0, 0});
        if(itr->v==v){
            r=itr->r;
        }else{
            if(itr->l!=r+1){
                ll tl=itr->l,tr=itr->r,tv=itr->v;
                odt.erase(itr);
                odt.insert(Node(tl,r,tv));
                itr=odt.insert(Node(r+1,tr,tv)).first;
            }
        }
    }
    auto itl=--odt.upper_bound((Node){l, 0, 0});
    if(itl->v==v){
        l=itl->l;
    }else{
        if(itl->l!=l){
            ll tl=itl->l,tr=itl->r,tv=itl->v;
            odt.erase(itl);
            odt.insert(Node(tl,l-1,tv));
            itl=odt.insert(Node(l,tr,tv)).first;
        }
    }
	odt.erase(itl,itr);
	odt.insert(Node(l,r,v));
}
bool ask(const ll &l,const ll &r){
    auto itr=split(r+1);
    auto itl=split(l);
    int vn=itl->v,vp=-1;
    if(itl!=odt.begin()){
        auto it=itl;
        --it;
        vp=it->v;
    }
    ++itl;
    for(;itl!=itr;++itl){
        if(itl->v!=vn){
            return 0;
        }
    }
    if(itl!=odt.end()){
        if(itl->v==vp){
            return 0;
        }
    }
    return 1;
}
void getint(int &x){
    char c;
    for(c=getchar();c>'9'||c<'0';c=getchar());
    for(x=0;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+c-'0';
}
inline char recd(char &o) {
    while ((o = getchar()) < 'A' || o > 'Z'); return o;
}
const int N=500000+5;
char s[N];
int main(){
    getint(n);
    int pos=1;
    char val=getchar();
    while(val<'A'||val>'C')
        val=getchar();
    for(int i=2;i<=n;++i){
        char c=getchar();
        if(c!=val){
            odt.insert(Node(pos,i-1,val-'A'));
            pos=i;
            val=c;
        }
    }
    odt.insert(Node(pos,n,val-'A'));
    int m,l,r;
    char op;
    getint(m);
    while(m--){
        recd(op);
        getint(l);getint(r);
        if(op=='A'){
            recd(op);
            assign(l,r,op-'A');
        }else{
            puts(ask(l,r)?"Yes":"No");
        }
    }
	return 0;
}

发表于 更新于 分类于

luogu1654

一个01串中每个长度为\(X\)的全1子串可贡献\(X^3\)的分数。

给出n次操作的成功率（在01串后附加1的概率）\(p[i]\)，求分数的期望。

设\(a[i]\)表示前i位中第i位为1的长度的期望：

\(a[i]=(a[i−1]+1)×p[i]\)

即为在i-1的末尾加一个概率为\(p[i]\)出现的1

设\(b[i]\)表示前i位中第i位为1的长度的平方的期望，\((x+1)^2=x^2+2x+1\),故

\(b[i]=(b[i−1]+2×a[i−1]+1)×p[i]\)

同理，设\(c[i]\)表示前i位中第i位为1的长度的立方的期望：(\((x+1)^3=x^3+3x^2+3x+1\))

\(c[i]=(c[i−1]+3×b[i−1]+3×a[i−1]+1)×p[i]\)

但本题求的是前n位（而不是第n）的得分期望，故

\(f[i]=(f[i−1]+3×b[i−1]+3×a[i−1]+1)×p[i]+f[i-1]×(1-p[i])\)

\(=f[i-1]+(3×b[i−1]+3×a[i−1]+1)×p[i])\) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;

const int N=100005;
double a[N],b[N],f[N];
int main(){
	int n;scanf("%d",&n);
	for(int i=1;i<=n;++i){
		double p;scanf("%lf",&p);
		a[i]=(a[i-1]+1)*p;
		b[i]=(b[i-1]+a[i-1]*2+1)*p;
		f[i]=f[i-1]+(3*b[i-1]+3*a[i-1]+1)*p;
	}
	printf("%.1lf",f[n]);
	return 0;
}

———————————————— 版权声明：本文为CSDN博主「ShineEternal」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/kkkksc03/article/details/99619790

发表于 更新于 分类于

https://ac.nowcoder.com/acm/contest/11255/B

\[ \space \]

\(f(x)\) 当前选的数字为x，之后的选的数的数量(X)的期望

\(E(X)=f(x)=\sum_1^{x-1} p_i \cdot 1+p_x \cdot (1+f(x))+\sum_{x+1}^{n}(f(i)+1)\cdot p_i\)

\[ f(x)=\frac{1+\sum_{x+1}^{n}f(i)\cdot p_i}{1-p_x } \] 则总数量为（题目中用不到）

\[ E(X+1)=\sum_1^n p_i \cdot (1+f(i)) \]

形式上\(E(x)=\sum q_i \cdot c_i\)

\((X+1)^2\)的期望

\(E((X+1)^2)=\sum q_i \cdot (c_i+1)^2=\sum q_i \cdot ({c_i}^2+2c_i+1)=E(X^2)+2E(X)+1\)

\(g(x)\)为当前选的数字为x，之后得分(\(E(X^2)\))的期望

\(g(x)=\sum_1^{x-1} p_i \cdot 1+p_x \cdot(g(x)+2f(x)+1)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i)+1)\)

\[ g(x)=\frac{\sum_1^{x-1} p_i \cdot 1+p_x \cdot(2f(x)+1)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i)+1)}{1-p_x} \] \[ =\frac{1+p_x \cdot 2f(x)+\sum_{x+1}^n p_i \cdot(g(i)+2f(i))}{1-p_x} \]

则答案为

\[ E((X+1)^2)=\sum_1^n p_i \cdot (1+2f(i)+g(i)) \]

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mo=998244353;
const int N=105;
ll a[N],f[N],g[N];

ll inv(ll a){
	ll ans=1,p=mo-2;
	while(p){
		if(p&1) ans=(ans*a)%mo;
		a=(a*a)%mo;
		p>>=1;
	}
	return ans%mo;
}

int main(){
	ll n,S=0;
	scanf("%lld",&n);
	for(ll i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		S+=a[i];
	}
	ll t=inv(S);
	for(ll i=1;i<=n;++i){
		a[i]=(a[i]*t)%mo;
	}
	S=0;
	for(ll i=n;i>0;--i){
		f[i]=(1+S)%mo*inv(1+mo-a[i])%mo;
		S=(S+f[i]*a[i]%mo)%mo;
		//cout<<f[i]<<endl;
	}
	S=0;
	for(ll i=n;i>0;--i){
		g[i]=(1+ 2*a[i]%mo*f[i]%mo + S)%mo * inv(1+mo-a[i])%mo;
		S=(S + a[i]*(g[i] + 2*f[i] %mo)%mo )%mo;
	}
	ll ans=0;
	for(ll i=1;i<=n;++i){
		ans=(ans+(1+2*f[i]%mo+g[i])*a[i]%mo)%mo;
	}
	printf("%lld",ans);
	return 0;
}

发表于 更新于 分类于

Hierholzer算法，也称逐步插入回路法。算法流程为从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。

任取一个起点,开始下面的步骤

如果该点没有相连的点，就将该点加进路径中然后返回。

如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没有相连的点。(遍历一个点，删除一个点）处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的步骤,把当前这个点加入路径中。 

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
const int N=1e5+5,M=2e5+5;
struct Edge{
    int t,n,id;
}e[M*2];
int ans[M];
int ind[N],outd[N],hd[N];
bool vis[M];
int cnt,tot;
void build(int f,int t,int id){
    e[++cnt]=(Edge){t,hd[f],id};
    hd[f]=cnt;
    ++ind[t],++outd[f];
}
void dfs(int u){
    for(int i=hd[u];i;i=hd[u]/*hd[u]会被修改成e[i].n*/){
        while(i&&vis[abs(e[i].id)]){
            i=e[i].n;
        }
        hd[u]=i;//已经访问过的边不再遍历,故修改第一条边 
        if(!i) break;
        vis[abs(e[i].id)]=1;
        dfs(e[i].t);
        ans[++tot]=e[i].id;
    }
}
int main(){
    int cs,n,m;
    scanf("%d%d%d",&cs,&n,&m);//cs 1：无向图 2：有向图 
    for(int i=1;i<=m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        build(x,y,i);
        if(cs==1) build(y,x,-i);
    }
    if(cs==1){
        for(int i=1;i<=n;++i){
            if(ind[i]&1){
                puts("NO");return 0;
            }
        }	 
    }else{
        for(int i=1;i<=n;++i){
            if(ind[i]!=outd[i]){
                puts("NO");return 0;
            }
        }
    }
    dfs(e[1].t);
    if(tot<m){
        puts("NO");
    }
    else{
        puts("YES");
        for(int i=m;i>=1;--i){
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

发表于 更新于 分类于

This blog is a derivative of 数位dp总结 之 从入门到模板 by wust_wenhao (csdn) #51 D. Beautiful numbers （数位dp+离散化）under CC 4.0 BY-SA, example codes are modified, some contents are added

引入

数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位......数的每一位就是数位啦！

之所以要引入数位的概念完全就是为了dp。数位dp的实质就是换一种暴力枚举的方式，使得新的枚举方式满足dp的性质，然后记忆化就可以了。

两种不同的枚举：对于一个求区间[le,ri]满足条件数的个数，最简单的暴力如下： 

1
2
for(int i=le;i<=ri;i++)
        if(right(i)) ans++;

然而这样枚举不方便记忆化，或者说根本无状态可言。 新的枚举：控制上界枚举，从最高位开始往下枚举，例如：ri=213，那么我们从百位开始枚举：百位可能的情况有0,1,2(觉得这里枚举0有问题的继续看)

然后每一位枚举都不能让枚举的这个数超过上界213（下界就是0或者1，这个次要），当百位枚举了1，那么十位枚举就是从0到9，因为百位1已经比上界2小了，后面数位枚举什么都不可能超过上界。所以问题就在于：当高位枚举刚好达到上界是，那么紧接着的一位枚举就有上界限制了。具体的这里如果百位枚举了2，那么十位的枚举情况就是0到1，如果前两位枚举了21，最后一位之是0到3(这一点正好对于代码模板里的一个变量limit 专门用来判断枚举范围)。最后一个问题：最高位枚举0：百位枚举0，相当于此时我枚举的这个数最多是两位数，如果十位继续枚举0，那么我枚举的就是以为数咯，因为我们要枚举的是小于等于ri的所以数，当然不能少了位数比ri小的咯！(这样枚举是为了无遗漏的枚举，不过可能会带来一个问题，就是前导零的问题，模板里用lead变量表示，不过这个不是每个题目都是会有影响的，可能前导零不会影响我们计数，具体要看题目)

由于这种新的枚举只控制了上界所以我们的Main函数总是这样: 

1
2
3
4
5
6
int main()
{
    long long le,ri;
    while(~scanf("%lld%lld",&le,&ri))
        printf("%lld\n",solve(ri)-solve(le-1));
}
统计[1,ri]数量和[1,le-1]，然后相减就是区间[le,ri]的数量了，这里我写的下界是1，其实0也行，反正相减后就没了，注意题目中le的范围都是大于等于1的(不然le=0,再减一就G_G了) 在讲例题之前先讲个基本的动态模板(先看后面的例题也行)：dp思想，枚举到当前位置pos，状态为state(这个就是根据题目来的，可能很多，毕竟dp千变万化)的数量(既然是计数,dp值显然是保存满足条件数的个数) 
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
typedef long long ll;
int a[20];
ll dp[20][state];//不同题目状态不同
ll dfs(int pos,/*state变量*/,bool lead/*前导零*/,bool limit/*数位上界变量*/)//不是每个题都要判断前导零
{
    //递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
    if(pos==-1) return 1;/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
    //第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
    if(!limit && !lead && dp[pos][state]!=-1) return dp[pos][state];
    /*常规写法都是在没有限制的条件记忆化，这里与下面记录状态是对应，具体为什么是有条件的记忆化后面会讲*/
    int up=limit?a[pos]:9;//根据limit判断枚举的上界up;这个的例子前面用213讲过了
    ll ans=0;
    //开始计数
    for(int i=0;i<=up;i++)//枚举，然后把不同情况的个数加到ans就可以了
    {
        if() ...
        else if()...
        ans+=dfs(pos-1,/*状态转移*/,lead && i==0,limit && i==a[pos]) //最后两个变量传参都是这样写的
        /*这里还算比较灵活，不过做几个题就觉得这里也是套路了
        大概就是说，我当前数位枚举的数是i，然后根据题目的约束条件分类讨论
        去计算不同情况下的个数，还有要根据state变量来保证i的合法性，比如题目
        要求数位上不能有62连续出现,那么就是state就是要保存前一位pre,然后分类，
        前一位如果是6那么这意味就不能是2，这里一定要保存枚举的这个数是合法*/
    }
    //计算完，记录状态
    if(!limit && !lead) dp[pos][state]=ans;
    /*这里对应上面的记忆化，在一定条件下时记录，保证一致性，当然如果约束条件不需要考虑lead，这里就是lead就完全不用考虑了*/
    return ans;
}
ll solve(ll x)
{
    int pos=0;
    while(x)//把数位都分解出来
    {
        a[pos++]=x%10;//个人老是喜欢编号为[0,pos),看不惯的就按自己习惯来，反正注意数位边界就行
        x/=10;
    }
    return dfs(pos-1/*从最高位开始枚举*/,/*一系列状态 */,true,true);//刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}
int main()
{
    ll le,ri;
    while(~scanf("%lld%lld",&le,&ri))
    {
        //初始化dp数组为-1,这里还有更加优美的优化,后面讲
        printf("%lld\n",solve(ri)-solve(le-1));
    }
}
相信读者还对这个有不少疑问，笔者认为有必要讲一下记忆化为什么是if(!limit)才行，大致就是说有无limit会出现状态冲突，举例： 约束：数位上不能出现连续的两个1(11、112、211都是不合法的)

假设就是[1,210]这个区间的个数

状态:dp[pos][pre]:当前枚举到pos位，前面一位枚举的是pre(更加前面的位已经合法了)，的个数(我的pos从0开始)

先看错误的方法计数，就是不判limit就是直接记忆化

那么假设我们第一次枚举了百位是0，显然后面的枚举limit=false，也就是数位上0到9的枚举，然后当我十位枚举了1，此时考虑dp[0][1],就是枚举到个位，前一位是1的个数，显然dp[0][1]=9;(个位只有是1的时候是不满足的)，这个状态记录下来，继续dfs，一直到百位枚举了2，十位枚举了1，显然此时递归到了pos=0,pre=1的层，而dp[0][1]的状态已经有了即dp[pos][pre]!=-1；此时程序直接return dp[0][1]了，然而显然是错的，因为此时是有limit的个位只能枚举0，根本没有9个数，这就是状态冲突了。有lead的时候可能出现冲突，这只是两个最基本的不同的题目可能还要加限制，反正宗旨都是让dp状态唯一

对于这个错误说两点：一是limit为true的数并不多，一个个枚举不会很浪费时间，所以我们记录下! limit的状态解决了不少子问题重叠。第二，有人可能想到把dp状态改一下dp[pos][state][limit]就是分别记录不同limit下的个数，这种方法一般是对的，关于这个具体会讲，下面有题bzoj3209会用到这个。

数位的部分就是这些，然后就是难点，dp部分，dp大牛的艺术，弱鸡只能看看+...+

既然从高位往低位枚举，那么状态一般都是与前面已经枚举的数位有关并且通常是根据约束条件当前枚举的这一位能使得状态完整(比如一个状态涉及到连续k位，那么就保存前k-1的状态，当前枚举的第k个是个恰好凑成成一个完整的状态，不过像那种状态是数位的和就直接保存前缀和为状态了)，不过必然有一位最简单的一个状态dp[pos]当前枚举到了pos位。dp部分就要开始讲例题了，不过会介绍几种常用防tle的优化。

HDU 2089 不要62


入门题。就是数位上不能有4也不能有连续的62，没有4的话在枚举的时候判断一下，不枚举4就可以保证状态合法了，所以这个约束没有记忆化的必要，而对于62的话，涉及到两位，当前一位是6或者不是6这两种不同情况我计数是不相同的，所以要用状态来记录不同的方案数。

dp[pos][sta]表示当前第pos位，前一位是否是6的状态，这里sta只需要去0和1两种状态就可以了，不是6的情况可视为同种，不会影响计数。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[20],dp[2][20];

int dfs(int pos,int pre,int sta,bool lim){
//pos:position [0,n)
//pre:previous selected number
//sta:status, it means pre==6 in this problem
//lim:limitation, it means if the i-th numbers before pos are all a[i] or not
	if(pos==-1){//the number 0
		return 1;
	}
	if(!lim&&dp[sta][pos]!=-1){//memorization
		return dp[sta][pos];
	}
	int rg=lim?a[pos]:9,tmp=0;
	for(int i=0;i<=rg;++i){
		if(pre==6&&i==2) continue;
		if(i==4) continue;
		tmp+=dfs(pos-1,i,i==6,lim&&i==a[pos]);
	}
	if(!lim) dp[sta][pos]=tmp;
	return tmp;
}

int solve(int x){
	int pos=0;
	while(x){
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,-1,0,1);
}

int main(){
	int l,r;
	while(~scanf("%d%d",&l,&r)&&l+r){
		memset(dp,-1,sizeof dp);
		printf("%d\n",solve(r)-solve(l-1));
	}
	return 0;
}


入门就不多讲了，开始讲常用优化吧！

第一:memset(dp,-1,sizeof dp);放在多组数据外面。

这一点是一个数位特点，使用的条件是：约束条件是每个数自身的属性，而与输入无关。

具体的：上一题不要62和4，这个约束对每一个数都是确定的，就是说任意一个数满不满足这个约束都是确定，比如444这个数，它不满足约束条件，不管你输入的区间是多少你都无法改变这个数不满足约束这个事实，这就是数自身的属性（我们每组数据只是在区间计数而已，只能说你输入的区间不包含444的话，我们就不把它统计在内，而无法改变任何事实）。

由此，我们保存的状态就可以一直用(注意还有要limit，不同区间是会影响数位在有限制条件下的上限的)

这点优化就不给具体题目了，这个还有进一步的扩展。不过说几个我遇到的简单的约束：

1.求数位和是10的倍数的个数,这里简化为数位sum%10这个状态，即dp[pos][sum]这里10 是与多组无关的，所以可以memset优化，不过注意如果题目的模是输入的话那就不能这样了。

2.求二进制1的数量与0的数量相等的个数，这个也是数自身的属性。

3.。。。。。

还是做题积累吧。搞懂思想！

下面介绍的方法就是要行memset优化，把不满足前提的通过修改，然后优化。

介绍之前,先说一种较为笨拙的修改，那就是增加状态，前面讲limit的地方说增加一维dp[pos][state][limit]，能把不同情况下状态分别记录(不过这个不能memset放外面)。基于这个思想，我们考虑：约束为数位是p的倍数的个数，其中p数输入的，这和上面sum%10类似，但是dp[pos][sum]显然已经不行了，每次p可能都不一样，为了强行把memset提到外面加状态dp[pos][sum][p]，对于每个不同p分别保存对应的状态。这里前提就比较简单了，你dp数组必须合法，p太大就G_G了。所以对于与输入有关的约束都可以强行增加状态(这并不代表能ac，如果题目数据少的话就随便你乱搞了)

例题：HDU 4734

题目给了个f(x)的定义：F(x) = An * 2n-1 + An-1 * 2n-2 + ... + A2 * 2 + A1 * 1，Ai是十进制数位，然后给出a,b求区间[0,b]内满足f(i)<=f(a)的i的个数。

常规想：这个f(x)计算就和数位计算是一样的，就是加了权值，所以dp[pos][sum]，这状态是基本的。a是题目给定的，f(a)是变化的不过f(a)最大好像是4600的样子。如果要memset优化就要加一维存f(a)的不同取值，那就是dp[10][4600][4600]，这显然不合法。

这个时候就要用减法了，dp[pos][sum]，sum不是存当前枚举的数的前缀和(加权的)，而是枚举到当前pos位，后面还需要凑sum的权值和的个数，

也就是说初始的是时候sum是f(a),枚举一位就减去这一位在计算f(i)的权值，那么最后枚举完所有位 sum>=0时就是满足的，后面的位数凑足sum位就可以了。

仔细想想这个状态是与f(a)无关的(新手似乎很难理解)，一个状态只有在sum>=0时才满足，如果我们按常规的思想求f(i)的话，那么最后sum>=f(a)才是满足的条件。


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
#include<bits/stdc++.h>
using namespace std;

const int N=10000+5;
int dp[11][N];
int a[20],fa;
int f(int x){
	int ans=0,pw=1;
	while(x){
		ans+=x%10*pw;
		pw<<=1;
		x/=10;
	}
	return ans;
}

int dfs(int pos,int sum,bool lim){
	if(pos==-1){
		return sum<=fa;
	}
	if(sum>fa){
		return 0;
	}
	if(!lim&&dp[pos][fa-sum]!=-1){
		return dp[pos][fa-sum];
	}
	int rg=lim?a[pos]:9,ans=0;
	for(int i=0;i<=rg;++i){
		ans+=dfs(pos-1,sum+i*(1<<pos),lim&&i==a[pos]);
	}
	if(!lim){
		dp[pos][fa-sum]=ans;
	}
	return ans;
	
}

int solve(int x){
	int pos=0;
	while(x){
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,0,1);
}

int main(){
	int T;
	scanf("%d",&T);
	memset(dp,-1,sizeof dp);
	for(int i=1;i<=T;++i){
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		fa=f(aa);
		printf("Case #%d: %d\n",i,solve(bb));
	}
	return 0;
}


例题 POJ 3252


这题的约束就是一个数的二进制中0的数量要不能少于1的数量，通过上一题，这题状态就很简单了，dp[pos][num],到当前数位pos,0的数量减去1的数量不少于num的方案数，一个简单的问题，中间某个pos位上num可能为负数(这不一定是非法的，因为我还没枚举完嘛，只要最终的num>=0才能判合法，中途某个pos就不一定了)，这里比较好处理，Hash嘛，最小就-32吧(好像),直接加上32，把32当0用。这题主要是要想讲一下lead的用法，显然我要统计0的数量，前导零是有影响的。至于!lead&&!limit才能dp，都是类似的，自己慢慢体会吧。

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
#include<cstdio>
#include<cstring>
#pragma comment(linker, "/STACK:10240000,10240000")
using namespace std;

int dp[33][65];
int a[33];

int dfs(int pos,int dlt,bool lead,bool lim){
	if(pos==-1){
		return dlt>=32;
	}
	if(!lim&&!lead&&dp[pos][dlt]!=-1){
		return dp[pos][dlt];
	}
	int rg=lim?a[pos]:1;
	int ans=0;
	for(int i=0;i<=rg;++i){
		if(lead&&i==0){
			ans+=dfs(pos-1,dlt,lead,lim&&i==a[pos]);
		}
		else{
			ans+=dfs(pos-1,dlt+(i==0?1:-1),lead&&i==0,lim&&i==a[pos]);
		} 
	}
	if(!lim&&!lead){
		dp[pos][dlt]=ans;
	}
	return ans;
}

int solve(int x){
	int i=0;
	memset(dp,-1,sizeof dp);
	while(x){
		a[i++]=x&1;
		x>>=1;
	}
	return dfs(i-1,32,1,1);
}

int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	printf("%d",solve(b)-solve(a-1));
	return 0;
}

Bit Sequence（2020 ICPC济南站 L）

Let f(x)f(x) denote the number of 1s in the binary representation of xxx.

Now MianKing has a sequence a0...m−1a_{0...m-1}a0...m−1​ and he wants to know the number of integer x∈[0,L]x x∈[0,L] satisfies that: ∀i∈[0,m−1],f(x+i) mod 2=aii, f(x+i)mod2=a_i∀i∈[0,m−1],f(x+i) mod 2=ai​

You need to help him calculate the answer.

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=100+5;
int a[N],dig[N],cnt,m,f[550];
ll dp[65][2][2][2],L;

ll cal(int sum,int one,int lim){
	int s=lim?L%128:127;
	ll ans=0;
	for(int i=0;i<=s;++i){
		bool ff=1;
		for(int j=0;j<m&&ff;++j){
			if(i+j<128){
				ff=(f[i+j]^sum)==a[j+1];
			}else{
				ff=(f[i+j]^one^sum==a[j+1]);
			}
		}
		ans+=ff;
	}
	return ans;
}

ll dfs(int pos,int sum,int one,int lim){
	ll &x=dp[pos][sum][one][lim];
	if(x!=-1) return x;
	if(pos<=6){
		x=cal(sum,one,lim);
		return x;
	}
	int rg=lim?dig[pos]:1;
	ll ans=0;
	for(int i=0;i<=rg;++i){
		int no=one;
		if(i){
			no^=1;
		}else{
			no=0;
		}
		ans+=dfs(pos-1,sum^i,no,lim&&i==rg);
	}
	return x=ans;
}

ll solve(ll x){
	memset(dp,-1,sizeof dp);
	memset(dig,0,sizeof dig);
	cnt=0;
	int len=0;
	for(int i=63;i>=0;--i){
		dig[i]=(x>>i)&1;
		if(dig[i]){
			len=max(len,i);
		}
	}
	return dfs(len,0,0,1);
}

int main(){
	for(int i=1;i<=512;++i){
		f[i]=f[i>>1]^(i&1);
	}
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%lld",&m,&L);
		for(int i=1;i<=m;++i){
			scanf("%d",&a[i]);
		}
		printf("%lld\n",solve(L));
	}
	return 0;
}

hdu355 Bomb

若从反面做，先找没有49的数，和不要62基本相同。 

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[2][100];
ll a[100];

ll dfs(int pos,int pre,bool lim){
	if(pos==-1){
		return 1ll;
	}
	if(!lim&&dp[pre==4][pos]!=-1) return dp[pre==4][pos];
	int rg=lim?a[pos]:9;
	ll ans=0;
	for(int i=0;i<=rg;++i){
		if(pre==4&&i==9){
			continue;
		}
		ans+=dfs(pos-1,i,lim&&i==a[pos]);
	}
	if(!lim){
		dp[pre==4][pos]=ans;
	}
	return ans;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(dp,-1,sizeof dp);
		ll len=0;
		ll n;
		scanf("%lld",&n);
		ll tmp=n;
		while(n){
			a[len++]=n%10;
			n/=10;
		}
		printf("%lld\n",tmp+1-dfs(len-1,0,1));
	}
	return 0;
}
从正面做 
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll dp[3][100];
ll a[100];

ll dfs(int pos,int sta,bool lim){
	if(pos==-1){
		return sta==2;
	}
	if(!lim&&dp[sta][pos]!=-1) return dp[sta][pos];
	int rg=lim?a[pos]:9;
	ll ans=0;
	for(int i=0;i<=rg;++i){
		int ns=sta;
		if(ns<2){
			if(i==4){
				ns=1;
			}else if(i==9&&ns==1){
				ns=2;
			}else{
				ns=0;
			}
		}
		ans+=dfs(pos-1,ns,lim&&i==a[pos]);
	}
	if(!lim){
		dp[sta][pos]=ans;
	}
	return ans;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(dp,-1,sizeof dp);
		ll len=0;
		ll n;
		scanf("%lld",&n);
		while(n){
			a[len++]=n%10;
			n/=10;
		}
		printf("%lld\n",dfs(len-1,0,1));
	}
	return 0;
}

hdu3652 B-number

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
#include<bits/stdc++.h>
using namespace std;

int dp[4][30][50],a[50];//sta==1 前方为1 sta==2 已有 13

int dfs(int pos,int sta,int m,bool lim){
	if(pos==-1){
		return sta==2&&m==0;
	}
	if(!lim&&dp[sta][m][pos]!=-1){
		return dp[sta][m][pos];
	}
	int rg=lim?a[pos]:9,ans=0;
	for(int i=0;i<=rg;++i){
		int ns=sta;
		if(sta==0&&i==1){
			ns=1;
		}
		else if(sta==1){
			if(i!=1)
				ns=0;
			if(i==3){
				ns=2;
			}
		}
		ans+=dfs(pos-1,ns,(m*10+i)%13,lim&&i==a[pos]);
	}
	if(!lim){
		dp[sta][m][pos]=ans;
	}
	return ans;
}

int main(){
	int n;
	while(~scanf("%d",&n)){
		memset(dp,-1,sizeof dp);
		int len=0;
		while(n){
			a[len++]=n%10;
			n/=10;
		}
		printf("%d\n",dfs(len-1,0,0,1));
	}
	return 0;
}

如果一个数能整除它的所有的非零数位，那么相当于它能整除个位数的最小公倍数。因此记忆化搜索中的参数除了len(当前位)和flag（是否达到上界），有一个pre_lcm表示前面的数的最小公倍数，判断这个数是否是Beautiful Numbers，还要有一个参数表示前面数，但是这个数太大，需要缩小它的范围。 可以发现所有个位数的最小公倍数是2520，假设当前的Beautiful Numbers是x， 那么 x % lcm{ dig[ i ] } = 0, 又 2520%lcm{ dig[ i ] } = 0。 那么x%2520%lcm{ dig[i] } = 0，x范围由9*10^18变为2520。 

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int a[20];
ll dp[20][50][2525];
int mp[2525];

ll lcm(ll a,ll b){
	return a/__gcd(a,b)*b;
}

//dp[i][j][k] 表示长度为i的，对2520取模为k的，最小公倍数序数为j的数的个数.
//1~9最小公倍数只有48个，预处理出来。（mp数组） 
ll dfs(int pos,int lm,int num,bool lim){
	if(pos==-1){
		return num%lm==0;
	}
	if(!lim&&dp[pos][mp[lm]][num]!=-1){
		return dp[pos][mp[lm]][num];
	}
	int rg=lim?a[pos]:9;
	ll ans=0;
	for(int i=0;i<=rg;++i){
		
		int now=(num*10+i)%2520;
		int nlm=lm;
		if(i) nlm=lcm(i,lm);
		ans+=dfs(pos-1,nlm,now,lim&&i==a[pos]);
	}
	if(!lim){
		dp[pos][mp[lm]][num]=ans;
	}
	return ans;
}

ll solve(ll x){
	int len=0;
	while(x){
		a[len++]=x%10;
		x/=10;
	}
	return dfs(len-1,1,0,1);
}

int main(){
	int T;
	cin>>T;
	int cnt=0;
	for(int i=1;i<=2520;++i){
		if(2520%i==0){
			mp[i]=++cnt;
		}
	}
	memset(dp,-1,sizeof dp);
	while(T--){
		ll a,b;
		cin>>a>>b;
		cout<<solve(b)-solve(a-1)<<'\n';
	}
	return 0;
}

发表于 更新于 分类于

高斯消元

模板 luogu P3389

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
#include<bits/stdc++.h>
using namespace std;

const double eps=1e-6;
const int N=100+5;
double a[N][N];
int n;

int gauss(){
	int c,r;
	for(c=1,r=1;c<=n;++c){
		int t=r;
		for(int i=r;i<=n;++i){
			if(fabs(a[i][c])>fabs(a[t][c])){
				t=i;
			}
		}//选最大的（提高精度+将0交换到下面）
		if(fabs(a[t][c])<eps) continue;
		for(int i=c;i<=n+1;++i) swap(a[t][i],a[r][i]);//交换到上部
		for(int i=n+1;i>=c;--i) a[r][i]/=a[r][c];//行首行列式数值变成1
		for(int i=r+1;i<=n;++i){
			if(fabs(a[i][c])>eps){
				double d=a[i][c];
				for(int j=n+1;j>=c;--j){
					a[i][j]-=a[r][j]*d;
				}
			}
		}
		++r;
	}
	if(r<=n){
        for(int i=r;i<=n;++i){
            if(fabs(a[i][n+1])>eps){
                return 2;//无解
            }
        }
		return 0;//没有唯一解
	}
	for(int i=n;i>0;--i){
		for(int j=i+1;j<=n;++j){
			a[i][n+1]-=a[j][n+1]*a[i][j];
		}
	}
	return 1;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n+1;++j){
			scanf("%lf",&a[i][j]);
		}
	}
	if(gauss()!=1){
		for(int i=1;i<=n;++i){
			printf("%.2lf\n",a[i][n+1]);
		}
	}else{
		puts("No Solution");
	}
	return 0;
}

ICPC2020 Jinan

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
#include<bits/stdc++.h>
using namespace std;

const int N=200+5;
int a[N][N],b[N][N];
int m[N][N];
typedef long long ll;
const ll mod=998244353;

ll qpow(ll a,ll p){
	if(p==0){
		return 1;
	}else if(p==1){
		return a%mod;
	}
	ll ret=qpow(a,p>>1);
	ret=(ret*ret)%mod;
	if(p&1) ret=(ret*a)%mod;
	return ret;
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&b[i][j]);
		}
	}
	int ans=0;
	for(int k=1;k<=n;++k){
		memset(m,0,sizeof m);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				m[i][j]^=a[i][j];
			}
			if(b[i][k]){
				m[i][i]^=1;
			}
		}
		int c,r;
		for(c=1,r=1;c<=n;++c){
			int t=r;
			for(int i=r;i<=n;++i){
				if(m[i][c]){
					t=i;
					break;
				}
			}
			if(m[t][c]==0) continue;
			if(t!=r){
				for(int i=c;i<=n;++i){
					swap(m[t][i],m[r][i]);
				}
			}
			for(int i=r+1;i<=n;++i){
				if(m[i][c]!=0){
					int d=m[i][c];
					for(int j=n;j>=c;--j){
						m[i][j]=(m[i][j]-m[r][j]*d+4)%2;
					}
				}
			}
			++r;
		}
		ans+=n-r+1;
	}
	printf("%lld",qpow(2,ans));
	return 0;
}

\(mod 2\)等价于异或，所以可以用bitset优化一个64的常数。

矩阵树定理

本章节的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，转自OIWIKI Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。

本篇记号声明

本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。

无向图情况

设 \(G\) 是一个有 \(n\) 个顶点的无向图。定义度数矩阵 \(D(G)\) 为：

\[ D_{ii}(G) = \mathrm{deg}(i), D_{ij} = 0, i\neq j \]

设 \(\#e(i,j)\) 为点 \(i\) 与点 \(j\) 相连的边数，并定义邻接矩阵 \(A\) 为：

\[ A_{ij}(G)=A_{ji}(G)=\#e(i,j), i\neq j \]

定义 Laplace 矩阵（亦称 Kirchhoff 矩阵）\(L\) 为：

\[ L(G) = D(G) - A(G) \]

记图 \(G\) 的所有生成树个数为 \(t(G)\)。

有向图情况

设 \(G\) 是一个有 \(n\) 个顶点的有向图。定义出度矩阵 \(D^{out}(G)\) 为：

\[ D^{out}_{ii}(G) = \mathrm{deg^{out}}(i), D^{out}_{ij} = 0, i\neq j \]

类似地定义入度矩阵 \(D^{in}(G)\)

设 \(\#e(i,j)\) 为点 \(i\) 指向点 \(j\) 的有向边数，并定义邻接矩阵 \(A\) 为：

\[ A_{ij}(G)=\#e(i,j), i\neq j \]

定义出度 Laplace 矩阵 \(L^{out}\) 为：

\[ L^{out}(G) = D^{out}(G) - A(G) \]

定义入度 Laplace 矩阵 \(L^{in}\) 为：

\[ L^{in}(G) = D^{in}(G) - A(G) \]

记图 \(G\) 的以 \(r\) 为根的所有根向树形图个数为 \(t^{root}(G,r)\)。所谓根向树形图，是说这张图的基图是一棵树，所有的边全部指向父亲。

记图 \(G\) 的以 \(r\) 为根的所有叶向树形图个数为 \(t^{leaf}(G,r)\)。所谓叶向树形图，是说这张图的基图是一棵树，所有的边全部指向儿子。

定理叙述

矩阵树定理具有多种形式。其中用得较多的是定理 1、定理 3 与定理 4。

定理 1（矩阵树定理，无向图行列式形式） 对于任意的 \(i\)，都有

\[ t(G) = \det L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n} \]

其中记号 \(L(G)\binom{1,2,\cdots,i-1,i+1,\cdots,n}{1,2,\cdots,i-1,i+1,\cdots,n}\) 表示矩阵 \(L(G)\) 的第 \(1,\cdots,i-1,i+1,\cdots,n\) 行与第 \(1,\cdots,i-1,i+1,\cdots,n\) 列构成的子矩阵(原矩阵去掉第\(i\)行同时去掉第\(i\)列（\(1\leq i\leq n\)），即矩阵的主子式)。也就是说，无向图的 Laplace 矩阵具有这样的性质，它的所有 \(n-1\) 阶主子式都相等。

定理 2（矩阵树定理，无向图特征值形式） 设 \(\lambda_1, \lambda_2, \cdots, \lambda_{n-1}\) 为 \(L(G)\) 的 \(n - 1\) 个非零特征值，那么有

\(t(G) = \frac{1}{n}\lambda_1\lambda_2\cdots\lambda_{n-1}\)

定理 3（矩阵树定理，有向图根向形式） 对于任意的 \(k\)，都有

\[ t^{root}(G,k) = \det L^{out}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]

因此如果要统计一张图所有的根向树形图，只要枚举所有的根 \(k\) 并对 \(t^{root}(G,k)\) 求和即可。

定理 4（矩阵树定理，有向图叶向形式） 对于任意的 \(k\)，都有

\[ t^{leaf}(G,k) = \det L^{in}(G)\binom{1,2,\cdots,k-1,k+1,\cdots,n}{1,2,\cdots,k-1,k+1,\cdots,n} \]

因此如果要统计一张图所有的叶向树形图，只要枚举所有的根 \(k\) 并对 \(t^{leaf}(G,k)\) 求和即可。 ### 「HEOI2015」小 Z 的房间 

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
#include<bits/stdc++.h>
using namespace std;

const int N=105;
char mp[N][N];
int n,m;
typedef long long ll;
ll L[N][N];
int id[N][N],cnt;
const ll mod=1e9;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%s",mp[i]+1);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			if(mp[i][j]=='.'){
				id[i][j]=++cnt;
				if(mp[i-1][j]=='.'){
					L[id[i][j]][id[i-1][j]]--;
					L[id[i-1][j]][id[i][j]]--;
					L[id[i][j]][id[i][j]]++;
					L[id[i-1][j]][id[i-1][j]]++;
					
				}
				if(mp[i][j-1]=='.'){
					L[id[i][j]][id[i][j-1]]--;
					L[id[i][j-1]][id[i][j]]--;
					L[id[i][j]][id[i][j]]++;
					L[id[i][j-1]][id[i][j-1]]++;
				}
				
			}
		}
	}
	int r=cnt-1;
	for(int i=1;i<=r;++i){
		for(int j=1;j<=r;++j){
			L[i][j]=(L[i][j]+mod)%mod;
		}
	}
	ll ans=1;
	for(int i=1;i<=r;++i){
		for(int j=i+1;j<=r;++j){
			while(L[j][i]){
				ll t=L[i][i]/L[j][i];
				for(int k=i;k<=r;++k){
					L[i][k]=(L[i][k]-t*L[j][k]%mod+mod)%mod;
					swap(L[i][k],L[j][k]);
				}
				ans*=-1;
			}
		}
		ans=ans*L[i][i]%mod;
	}
 	printf("%lld",(ans+mod)%mod);
	return 0;
}
注意处理整数时，写法的不同。

Luogu P2144 [FJOI2007]轮状病毒

需要高精度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
n=int(input())
n=n+1
a=[[0 for i in range(n+2)]for j in range(n+2)]
a[1][1]=n-1
a[2][n]=-1
a[n][2]=-1
for i in range(2,n+1):
    a[i][1]=-1
    a[1][i]=-1
    a[i][i]=3
    if i+1<=n :
        a[i][i+1]=-1
        a[i+1][i]=-1
ans=1
for i in range(1,n):
    for j in range(i+1,n):
        while a[j][i]!=0:
            t=a[i][i]//a[j][i]
            for k in range(i,n):
                a[i][k]-=t*a[j][k]
                a[i][k],a[j][k]=a[j][k],a[i][k]
            ans=-ans
    ans*=a[i][i]
print(ans)