【Codeforces 814E】An unavoidable detour for home

相关链接

题目传送门:http://codeforces.com/contest/814/problem/E
官方题解:http://codeforces.com/blog/entry/52449
神犇题解Ⅰ:https://loj.ac/article/37
神犇题解Ⅱ:http://kczno1.blog.uoj.ac/blog/2660

解题报告

我们考虑分层图的话
那每一层的一个点一定会与上一层的某个点相连,剩下的度数只能层内消化
又因为这题对祖先有严格的限制,所以每一层都是原序列中连续的一段
于是$O(n^5)$的暴力$DP$就可以写了

至于$O(n^3)$的$DP$,就是$DP$套$DP$
预处理出转移的$buf$,然后转移的时候直接乘就好了
但这个预处理的时候要讨论很多情况啊,反正我自己考场上是想不出来的_(:з」∠)_

Code

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

const int N = 52;
const int MOD = 1000000007;
const int REV2 = 500000004;

int n, f[N][N], s2[N], s3[N], buf[N][N][N], C[N][N], prm[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	f[read() + 1][1] = 1;
	for (int i = 2; i <= n; i++) {
		s2[i] = s2[i - 1];
		s3[i] = s3[i - 1];
		if (read() == 2) {
			s2[i]++;
		} else {
			s3[i]++;
		}
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	prm[2] = 1;
	for (int i = 3; i <= n; i++) {
		prm[i] = REV2;
		for (int j = 2; j < i; j++) {
			prm[i] = (LL)prm[i] * j % MOD;
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (i == 0 && j == 0 && k == 0) {
					buf[i][j][k] = 1;
				} else if (i == 0 && j == 0) {
					for (int l = 2; l < k; l++) {
						(buf[i][j][k] += ((LL)buf[i][j][k - 1 - l] * C[k - 1][l] % MOD) * prm[l + 1] % MOD) %= MOD;
					}
				} else if (i == 0) {
					buf[i][j][k] = j > 1? (LL)(j - 1) * buf[i][j - 2][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i][j][k - 1] % MOD: 0) %= MOD;
				} else {
					buf[i][j][k] = j? (LL)j * buf[i - 1][j - 1][k] % MOD: 0;
					(buf[i][j][k] += k? (LL)k * buf[i - 1][j + 1][k - 1] % MOD: 0) % MOD;
				} 
			}
		}
	} 
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (f[i][j]) {
				int t2 = s2[i] - s2[j];
				int t3 = s3[i] - s3[j];
				for (int k = i + 1; k <= n; k++) {
					f[k][i] = (f[k][i] + (LL)f[i][j] * buf[k - i][t2][t3]) % MOD;
				}
			}
		}
	} 
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = (ans + (LL)f[n][i] * buf[0][s2[n] - s2[i]][s3[n] - s3[i]]) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

【Codeforces 799D】Field expansion

相关链接

题目传送门:http://codeforces.com/contest/799/problem/D

解题报告

不难发现,至多只会使用$O(2 \log 10^5)$个物品
于是定义$f_i$表示长为$i$时,宽最多为多少
暴力转移即可,时间复杂度:$O(10^5 \log 10^5)$

Code

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

const int N = 100009;
const int INF = 1e9;

int n,v[N],f[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline bool cmp(int a, int b) {
	return a > b;
}

inline int solve(int a, int b, int h, int w) {
	memset(f, 0, sizeof(f));
	f[min(h, a)] = min(b, w);
	int ans = 1;
	for (int j=1;j<=n;j++,ans++) {
		for (int i=a;i;i--) {
			if (f[i]) {
				int tt = min((LL)a, (LL)i * v[j]);
				f[tt] = max(f[tt], f[i]);
				if (tt == a && f[i] == b) {
					return ans;
				}
				tt = min((LL)b, (LL)f[i] * v[j]);
				f[i] = tt;
				if (i == a && tt == b) {
					return ans;
				}
			}
		}
	}
	return INF;
}

int main() {
	int a = read(), b = read();
	int h = read(), w = read();
	n = read();
	for (int i=1;i<=n;i++) {
		v[i] = read();
	}
	sort(v+1, v+1+n, cmp);
	n = min(n, 34);
	if ((h >= a && w >= b) || (h >= b && w >= a)) {
		puts("0");
		exit(0);
	}
	int ans1 = solve(a, b, h, w);
	int ans2 = solve(a, b, w, h);
	if (ans1 >= INF && ans2 >= INF) {
		puts("-1");
	} else {
		printf("%d\n",min(ans1, ans2));
	}
	return 0;
}

【TopCoder SRM713】CoinsQuery

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14572&rd=16882

题目大意

给$n(n \le 100)$类物品,第$i$类物品重量为$w_i(w_i \le 100)$,价值为$v_i(v_i \le 10^9)$,数量无限
给定$m(m \le 100)$个询问,第$i$询问请你回答总重量恰好为$q_i(q_i \le 10^9)$的物品,价值和最大为多少
你还需要求出使价值最大的方案数是多少(同类物品视作一样,摆放顺序不同算不同)

解题报告

规定每个物品重量不超过$100$那么我们就可以矩乘
但有一个问题:我们不仅要让价值最大,还要求方案数

但类比倍增Floyd:在一定条件,矩乘重载运算符之后仍然满足结合律
比如说这个题,我们可以:

重载加法为:两种方案取最优
重载乘法为:将两种方案拼起来(方案数相乘,价值相加)

然后直接做是$O(m n^3 \log n)$的,会在第$21$个点$TLE$
于是我们预处理转移矩阵的幂次,然后对于每个询问就是向量与矩阵相乘,单次复杂度是$O(n^2)$的
于是总的时间复杂度优化到:$O(m n^2 \log n + n^3 \log n)$

Code

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

const int MOD = 1000000007;
const int N = 101;

struct Data{
	LL val,chs;
	inline Data() {val = chs = -1;}
	inline Data(LL a, LL b):val(a),chs(b) {}
	inline Data operator + (const Data &D) {
		if (chs == -1 || D.chs == -1) {
			return chs != -1? *this: D;
		} else {
			Data ret(max(val, D.val), 0);
			(ret.chs += (val == ret.val? chs: 0)) %= MOD;
			(ret.chs += (D.val == ret.val? D.chs: 0)) %= MOD;
			return ret;
		}
	}
	inline Data operator * (const Data &D) {
		if (!~chs || !~D.chs) return Data(-1, -1);
		return Data(val + D.val, chs * D.chs % MOD);
	}
}e(0,1);
struct Matrix{
	Data a[N][N]; int x,y;
	inline Matrix() {x = y = 0;}
	inline Matrix(int X, int Y):x(X),y(Y) {}
	inline Matrix operator * (const Matrix &M) {
		Matrix ret(M.x, y);
		for (int i=1;i<=M.x;i++) {
			for (int k=1;k<=x;k++) {
				for (int j=1;j<=y;j++) {
					ret.a[i][j] = ret.a[i][j] + (a[k][j] * M.a[i][k]);
				}
			}
		}
		return ret;
	}
}tra[32];

class CoinsQuery {
    public:
    	vector<LL> query(vector<int> w, vector<int> v, vector<int> query) {
    	    int m = query.size(), n = w.size();
			tra[0].x = tra[0].y = 100;
    	    for (int i=0;i<n;i++) {
				tra[0].a[w[i]][1] = tra[0].a[w[i]][1] + Data(v[i], 1);
			}
			for (int i=2;i<=100;i++) {
				tra[0].a[i-1][i] = e;
			}
			for (int i=1;i<=30;i++) {
				tra[i] = tra[i-1] * tra[i-1];
			}
    	    
			vector<LL> ret;
    	    for (int tt=0;tt<m;tt++) {
				Matrix ans(100, 1);
				ans.a[1][1] = e;
				int cur = query[tt];
				for (int i=0;cur;cur>>=1,++i) {
					if (cur & 1) {
						ans = ans * tra[i];
					}
				}
				ret.push_back(ans.a[1][1].val);
				ret.push_back(ans.a[1][1].chs);
			}
    	    return ret;
   		}
   	private:
};

【BZOJ 4828】[HNOI2017] 大佬

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4828

解题报告

先$DP$出最多可以有多少天不做题
然后我们发现两次$D$人其实是独立的
于是我们再$DP$出攻击达到$x$的最小天数

最后回答每个询问的时候
用个双指针扫一扫

Code

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

const int N = 109;
const int M = 930000;

int n,m,mc,tot,MX,ispri[N],w[N],a[N],f[N][N];
pair<int,int> itm[M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void DFS(int t, LL sum) {
	if (t > MX) return;
	else {
		DFS(t + 1, sum);
		if (ispri[t]) {
			for (;sum*=t,sum<=1e8;) {
				itm[++tot].first = sum;
				DFS(t + 1, sum);
			}
		}
	}
}

inline int cal(int x) {
	int ret = x + 1;
	for (int i=min(MX,x-1),cnt,tmp;i;i--) {
		if (x % i) continue;
		cnt = i + 1; tmp = x;
		for (int j=i;j>1&&tmp>1;j--) {
			while (tmp % j == 0) {
				tmp /= j;
				++cnt;
			}
		}
		if (tmp == 1) {
			ret = min(ret, cnt);
		} else {
			break;
		}
	}
	return ret;
}

int main() {
	n = read(); m = read(); mc = read();
	for (int i=1;i<=n;i++) {
		a[i] = read();
	}
	for (int j=1;j<=n;j++) {
		w[j] = read();
	}
	//DP最多空出来的天数 
	memset(f, -1, sizeof(f));
	f[1][mc] = 0;
	for (int i=1;i<=n;i++) {
		for (int j=a[i];j<=mc;j++) {
			if (f[i][j] == -1) continue;
			int t1 = min(j - a[i] + w[i], mc), t2 = j - a[i];
			if (t1 >= 0) {
				f[i + 1][t1] = max(f[i + 1][t1], f[i][j]);
			}
			if (t2 >= 0) {
				f[i + 1][t2] = max(f[i + 1][t2], f[i][j] + 1);
			}
		}
	}
	MX = -1; 
	for (int j=2;j<=n+1;j++) {
		for (int i=0;i<=mc;i++) {
			MX = max(MX, f[j][i]);
		}
	} 
	//搞出每一个物品的最小花费 
	for (int j=2;j<=100;j++) {
		ispri[j] = 1;
		for (int i=2;i*i<=j;i++) {
			if (j % i == 0) {
				ispri[j] = 0;
			}
		}
	}
	DFS(1, 1); 
	for (int i=1;i<=tot;i++) {
		itm[i].second = cal(itm[i].first);
	}
	itm[++tot] = make_pair(0, 0);
	sort(itm+1, itm+1+tot);
	//对于每个询问用一个双端队列
	for (int tt=1;tt<=m;tt++) {
		int C = read(), ans = 0;
		for (int i=tot,pfx=1,cur=-1e9;i;i--) {
			while (pfx <= tot && itm[pfx].first <= C - itm[i].first) {
				cur = max(cur, itm[pfx].first - itm[pfx].second);
				pfx++;
			}
			if (cur + itm[i].first - itm[i].second >= C - MX) {
				ans = 1; 
				break;
			}
		}
		printf("%d\n",ans);
	} 
	return 0;
}

【BZOJ 4861】[BeiJing2017] 魔法咒语

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4861

解题报告

对于$L \le 100$的情况,我们定义$f_{i,j}$表示长度为$i$,在$ac$自动机上匹配到点$j$的答案
然后暴力转移就可以了,时间复杂度:$O(10^4L)$

对于其他的点,我们构造转移矩阵,用矩阵快速幂来优化
至于如何把长度为$2$的和为$1$的给统一起来?我们可以加一个点缓存一下
时间复杂度:$O(200^3 \log L)$

Code

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

const int MOD = 1000000007;

int n,m,L,len[109];
char s1[109][109],s2[109][109];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

class AC_Automaton{
	int cnt,ch[109][26],vis[109],fail[109];
	vector<int> G[109];
	queue<int> que;
	public:
		inline AC_Automaton() {
			cnt=1;
		}
		inline void insert(char *s) {
			int l = strlen(s + 1), w = 1;
			for (int i=1;i<=l;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			}
			vis[w] = 1;
		}
		inline void build() {
			for (int i=0;i<26;i++) {
				if (!ch[1][i]) ch[1][i] = 1;
				else fail[ch[1][i]] = 1, que.push(ch[1][i]);
			}
			while (!que.empty()) { 
				int w = que.front(); que.pop(); 
				G[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i] && ch[w][i] != 1) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else {
						ch[w][i] = ch[fail[w]][i];
					}
				}
			} 
			DFS(1, 0);
		}
		inline int size() {
			return cnt;
		}
		inline int MOVE(int w, int j) {
			if (vis[j]) return -1;
			for (int i=1;i<=len[w];i++) {
				j = ch[j][s1[w][i]-'a'];
				if (vis[j]) return -1;
			}
			return j;
		}
	private:
		void DFS(int w, int t) {
			t |= vis[w];
			if (t) vis[w] = 1; 
			for (int i=G[w].size()-1;~i;i--) {
				if (G[w][i] != i) { 
					DFS(G[w][i], t);
				}
			}
		}
}ac;

namespace SUBTASK_ONE{
	int f[109][109],tot,ans;
	int tra[109][109];
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=ac.size();j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		f[0][1] = 1;
		for (int i=0;i<L;i++) {
			for (int j=1;j<=ac.size();j++) {
				if (f[i][j]) {
					for (int k=1,t1,t2;k<=n;k++) {
						if ((t1=tra[j][k]) != -1 && (t2=i + len[k]) <= L) {
							f[t2][t1] = (f[t2][t1] + f[i][j]) % MOD; 
						}
					}
				}
			}
		}
		for (int i=1;i<=ac.size();i++) {
			ans = (ans + f[L][i]) % MOD;
		}
		printf("%d\n",ans);
	} 
};

namespace SUBTASK_TWO{
	int sz,tot,tra[109][109*109+109];
	struct Matrix{
		int a[209][209];
		inline Matrix() {
			memset(a,0,sizeof(a));
		}
		inline Matrix(int x) {
			memset(a,0,sizeof(a));
			for (int i=1;i<=sz;i++) a[i][i] = x;
		}
		inline Matrix operator * (const Matrix &M) {
			Matrix ret;
			for (int i=1;i<=sz;i++) {
				for (int j=1;j<=sz;j++) {
					for (int k=1;k<=sz;k++) {
						ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * M.a[i][k]) % MOD;	
					}
				}
			}
			return ret;
		}
		inline Matrix operator ^ (int t) {
			Matrix ret(1),tmp;
			for (int i=1;i<=sz;i++) {
				memcpy(tmp.a[i],a[i],sizeof(a[i]));
			}
			for (;t;t>>=1,tmp=tmp*tmp) {
				if (t&1) ret = ret * tmp;
			}
			return ret;
		}
		inline void init() {
			memset(a,0,sizeof(a));
		}
	}ans,trans;
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); sz = ac.size();
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=sz;j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		ans.a[1][1] = 1; int ori = sz; 
		for (int i=1;i<=ori;i++) trans.a[i][++sz]++;
		for (int i=1;i<=ori;i++) {
			for (int j=1;j<=n;j++) {
				if (!tra[i][j]) continue;
				if (len[j] == 1) ++trans.a[tra[i][j]][i];
				else trans.a[tra[i][j]+ori][i]++;
			}
		}
		trans = trans ^ L;
		ans = ans * trans;
		int vout = 0;
		for (int i=1;i<=ori;i++) vout = (vout + ans.a[i][1]) % MOD;
		cout<<vout<<endl;
	}
};

int main() {
	n = read(); m = read(); L = read();
	if (L <= 100) {
		SUBTASK_ONE::solve();
	} else {
		SUBTASK_TWO::solve();
	}
	return 0;
}

【BZOJ 3612】[HEOI2014] 平衡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3612
神犇题解:http://blog.csdn.net/Vmurder/article/details/42551603

解题报告

读题后我们发现需要求解这么一个问题:

用$k$个不同的数,来凑成$n$的方案数

这个看起来只能$O(kn^2)$来做$DP$
但我们可以将其优化到$O(nk)$
具体来说,考虑所有$k$个数,一起加或一起减
这样的话,我们就可以不用枚举新加入答案集合的数是哪一个了

回到原题,我们枚举左右两边取出来的重量,和左边用了几块橡皮
然后总的复杂度主要还是在$DP$那一块,复杂度是:$O(k^2n)$的

Code

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

const int N = 100009;
const int M = 11;

int n,K,MOD,f[N][M];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read(),ans;ans=0,T;T--) {
		n = read(); K = read(); MOD = read();
		memset(f,0,sizeof(f)); f[0][0] = 1;
		for (int i=1,lim=n*K;i<=lim;i++) {
			for (int k=1,LIM=min(i,K);k<=LIM;k++) {
				f[i][k] = (f[i-k][k] + f[i-k][k-1]) % MOD;
				if (i > n) f[i][k] = (f[i][k] - f[i-(n+1)][k-1]) % MOD;
			}
		}
		for (int i=0,lim=n*K;i<=lim;i++) {
			for (int k=0;k<K;k++) {
				ans = (ans + (LL)f[i][k] * f[i][K-k]) % MOD;
				ans = (ans + (LL)f[i][k] * f[i][K-k-1]) % MOD;
			}
		}
		printf("%d\n",(ans+MOD)%MOD);
	}
	return 0;
}

【Codeforces 800C】Vulnerable Kerbals

相关链接

题目传送门:http://codeforces.com/contest/800/problem/C

解题报告

写一写发现前缀积与$m$的$\gcd$是一个递增的关系,依次为倍数
于是我们将$0 \sim m-1$按照与$m$的$\gcd$分类
然后就是在拓扑图上搞一搞$DP$,输出的时候用拓展欧几里得求一发逆元
总的时间复杂度:$O(n \log n)$

Code

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

const int N = 5000000;
const int M = 10000;

int n,m,tot,ans,vis[N],id[N],in[M],num[M];
int head[M],nxt[N],to[N],f[M],itr[M];
vector<int> que[M],vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

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

inline void AddEdge(int u, int v) {
	static int E = 1; in[u]++; 
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void solve(int w) { 
	f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
	ans = max(ans, f[w]); 
	for (int i=head[w];i;i=nxt[i]) {
		if (f[w] > f[itr[to[i]]]) itr[to[i]] = w;
		if (--in[to[i]] == 0) solve(to[i]);
	}
}

void exgcd(int a, int b, LL &x, LL &y) {
	if (b) {exgcd(b, a%b, y, x); y -= a / b * x;}
	else {x = 1; y = 0;}
}

inline int REV(int a, int z) {
	int tmp = gcd(a, m), b; LL x, y; 
	a /= tmp; z /= tmp; b = m / tmp;
	exgcd(a, b, x, y);
	return x * z % m;
}

void print(int w, int v) {
	for (int i=0;i<=que[w].size()-1;i++) {
		int nv = que[w][i], rev = REV(v, nv);
		vout.push_back((rev+m)%m); v = nv;
	}
	if (itr[w]) print(itr[w], v);
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) vis[read()] = 1;
	for (int i=1;i<m;i++) if (!vis[i]) {
		int tmp = gcd(m, i); 
		if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp;
		que[id[tmp]].push_back(i);
	}
	for (int i=1;i<=tot;i++) {
		for (int j=1;j<=tot;j++) {
			if (num[j] > num[i] && num[j] % num[i] == 0) {
				AddEdge(i, j); 
			}
		}
	}
	for (int i=1;i<=tot;i++) if (!in[i]) solve(i);
	for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;}
	if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl;
	for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]); 
	return 0;
}

【HDU 4624】Endless Spin

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4624
神犇题解Ⅰ:http://www.cnblogs.com/chanme/p/4869377.html
神犇题解Ⅱ:http://blog.csdn.net/beginendzrq/article/details/51331954

解题报告

我们设$f_i$为染色$i$次后还有球没有被染色的概率
那么我们的答案$ans$为: $\sum\limits_{i = 0}^\infty {{f_i}} $

现在考虑如何求$f_i$,我们先来$O(2^n)$暴力容斥
具体来讲,我们枚举染色$i$次后还剩下哪些球为白色
设还有$k$个球为白色,这$k$个球位置分别为$v_1 \sim v_k$
那么单次染色的区间不能包含这$k$个位置,设合法的方案数为$A$
那么单次染色符合条件的概率$P=\frac{A}{\frac{n(n-1)}{2}}$
那么$i$次都符合要求的概率就是$P^i$
于是对于$f_i$来讲,贡献为$P^i \cdot (-1)^{k-1}$
这种情况对于答案$ans$的贡献为$(-1)^{k-1}\sum\limits_{i=0}^{\infty}{P^i}=\frac{(-1)^{k-1}}{1-P}$

现在考虑优化容斥的过程
我们发现每一种具体的方案对于答案的贡献只与剩余球的数量的奇偶性和$A$有关
于是我们可以搞一个状态为$O(n^4)$,转移为$O(1)$的DP来优化容斥

Code

这份代码在我本地跑出来是对的,但交上去就wa
于是只能打了一份表交上去:http://paste.ubuntu.com/24448347/

#include<bits/stdc++.h>
#define LL long long
#define LDB __float128
using namespace std;

const int N = 51;
const int M = N * N;

int n,ww,pp;
LL f[2][N][M][2]; 
LDB ans;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		ans = ww = 0; pp = 1;
		memset(f,0,sizeof(f));
		f[pp][0][0][0] = 1;
		n = read();
		for (int i=0;i<n;i++,ww^=1,pp^=1) { 
			memset(f[ww],0,sizeof(f[ww]));
			for (int j=0;j<=i;j++) {
				for (int k=i*i;~k;k--) {
					for (int p=0;p<=1;p++) {
						if (f[pp][j][k][p]) {
							f[ww][0][k+j*(j+1)/2][p^(j&1)] += f[pp][j][k][p];
							f[ww][j+1][k][p] += f[pp][j][k][p]; 
						}
					}
				}
			}
		}
		for (int j=0;j<=n;j++) {
			for (int k=n*n;~k;k--) {
				for (int p=0;p<=1;p++) {
					if (!f[pp][j][k][p]) continue;
					int v = k + j * (j + 1) / 2, t = p ^ (j & 1);
					LDB tmp = ((v < n * (n + 1) / 2)? ((LDB)v / (n * (n + 1) / 2 - v)): 0);
					if ((n-t)&1) ans += tmp * f[pp][j][k][p];
					else ans -= tmp * f[pp][j][k][p];
				}
			}
		}
		ans += 1; 
		printf("%.15Lf\n",(long double)ans);
	}
	return 0;
}

相关拓展

当然这题还可以改成:如果染到$k$个球都为黑色了就停止,询问停止时的期望步数
例题可以参考:凯旋三兵

【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ:http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解,好神啊!
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲,设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求?搞一个队列就可以了?或者二分也是可以的
另外还需要注意一点:$g_i$是单调递增的

现在我们再来考虑$c_i$的限制,我们使用分治来解决
在$solve(l,r)$的时候,我们找出$c_i$最大的那个点$k$,然后递归下去
在合并上来的时候,我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步:因为$c_k$是$[l,r]$中最大的那个,所以对于此时所有的转移,$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲,其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增,所以我们对于$[k,r]$从左到右分四段考虑:

  1. $g_i \le l$且$i-c_k \le k-1$
    我们的首先我们肯定可以使用线段树来更新
    但更进一步,对于这一类点,我们只需要在查询第一个点时使用线段树就可以了
    因为这是一个前缀,之后$i$每向右移一位,合法的$j$也最多增加$1$
    不难发现,总的暴力操作次数不大于左右区间中较小的一段
    时间复杂度:$O(\log + \min(r-k+1,k-l))$
  2. $g_i \le l$且$k-1 < i-c_k$
    对于这些点,我们查询的是整个左区间
    我们整体查一次,然后一起更新就可以了
    时间复杂度:$O(\log n)$
  3. $l < g_i < k$
    对于这些点,我们查询的是左区间的一个后缀,我们直接在线段树上查就好
    考虑所有会影响到$i$的$solve$,它们的左区间一定没有交集
    也就是说只会有一个$solve$的左区间包含$g_i$
    于是对于每一个$i$,在整个算法中只会被查询一次
    所以这部分复杂度是$O(n \log n)$的,且不需要考虑到分治的复杂度中去
  4. $g_i \le k$
    直接不管就好

现在我们来分析分治的复杂度:$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样,于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度,总时间复杂度仍然为$O(n \log n)$

值得一提的是,这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575,一定要引起重视啊

【BZOJ 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【日常小测】Hope

题目大意

给定排列的长度$n(n\le10^5)$和常数$k(k\le10^5)$
对于单个排列$A$中的每$i$位:我们连一条从$i$出发,到其右边第一个比它大的位,如果没有就不连
定义$A$的花费为 $\sum$其中每一个连通块的大小$^k$
询问所有长度为$n$的排列的花费和$(\bmod 998244353)$

解题报告

设$f_i$为排列长度为$i$的答案,假设我们已经求出了$f_{i-1}$
我们考虑枚举$i$放在哪里,那么$i$之前的数全部连向$i$,之后的数是递归一个子问题
于是我们可以写出暴力的$DP$:${f_i} = \sum\limits_{j = 1}^i {{j^k}(j – 1)!C_{i – 1}^{j – 1}{f_{i – j}}} $
我们化一化式子可以得到$\frac{f_i}{(i-1)!}=\sum\limits_{j=1}^{i}{j^k \cdot \frac{f_{i-j}}{(i-j)!}}$
这显然是一个卷积的形式,于是可以用$NTT$优化

另外,对于$f_i$来讲,$f_{1 \sim i-1}$都会对它有贡献
那么这有是一个典型的$CDQ$分治的模型,于是我们还需要套上一个$CDQ$分治

在另外的话,我们回顾一下推出暴力$DP$的过程
不难发现我们是以最大值的插入作为突破口
那么这种题目与最大值相关的问题,这应该算是套路之一吧!
例如:HDU 5575

—————————— UPD 2017.3.17 ——————————
Claris说这题在OEIS上能找到$O(n)$的递推式 QwQ
Claris太强啦! _(:з」∠)_

【BZOJ 4347】[POI2016] Nim z utrudnieniem

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/50788730

解题报告

这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的,显然不能通过此题
但我们注意到,对于一个数$a_i$来讲,小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$,每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了

虽然$md$可以到$10^8$,而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快? 可能是数据比较水吧?

哦,对了,这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧,$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;
 
int n,D,XOR,f[N][10],g[2][10],arr[M];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
int main() {
    n = read(); D = read(); 
    for (int i=1;i<=n;i++) XOR ^= (arr[i] = read());
    sort(arr+1, arr+1+n); 
    f[0][0] = 1;
    for (int i=1,LIM=1;i<=n;i++) {
        while (LIM <= arr[i]) LIM <<= 1;
        for (int v=1,nv;v<LIM;v++) {
            if ((nv=(arr[i]^v)) <= v) { 
                for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
                    g[1][t] = (f[nv][t] + f[v][d]) % MOD;       
                    g[0][t] = (f[nv][d] + f[v][t]) % MOD;
                }
                for (int d=0;d<D;d++) {
                    f[nv][d] = g[1][d];
                    f[v][d] = g[0][d];
                }
            }
        } 
    }
    if (n % D == 0) f[XOR][0]--;
    printf("%d\n",(f[XOR][0]+MOD)%MOD);
    return 0;
}

【BZOJ 4282】慎二的随机数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4282
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/48998981

解题报告

首先我们需要得到一个结论:一定存在一组最优解,使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论:

考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可,这样不会使答案变劣

于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a(相当于把那a个不确定位置在值域上留出位置)
然后对确定的串做一次LIS,然后加上不确定位置的个数即可

Code

我写LIS一直用的BIT,但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS,然后每一次lower_bound就可以了!

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

const int N = 200000+9;

int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];

class Fenwick_Tree{
	int mx[N];
	public:
		inline void modify(int p, int v) {
			for (int i=p;i<=tot;i+=lowbit(i))
				mx[i] = max(mx[i], v);
		}
		inline int query(int p) {
			int ret = 0; 
			for (int i=p-1;i;i-=lowbit(i))
				ret = max(ret, mx[i]);
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & (-x);
		}
}BIT;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	for (int i=1;i<=n;++i) {
		scanf("%s",pat+1);
		if (pat[1] == 'K') {
			arr[++tot] = read() - m;
			_hash[tot] = arr[tot];		
		} else ++m;
	}
	n = tot; sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		f[i] = BIT.query(arr[i]) + 1;
		vout = max(f[i], vout);
		BIT.modify(arr[i], f[i]);
	} 
	printf("%d\n",vout + m);
	return 0;
}

【BZOJ 3997】[TJOI2015] 组合数学

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3997
神犇题解:http://blog.csdn.net/popoqqq/article/details/45171469

解题报告

这题又™是结论题
需要用到的结论:

Dilworth定理:DAG的最小链覆盖=最大点独立集

类似的结论还有:

最大团=补图上的最小点覆盖的补集
最大反链的大小=最小链划分
最大链的大小=最小反链划分

知道结论之后,实际上就是让你求一些点,相互不能到达,且点权和最大
这样的话,从左下到右上搞一个DP就可以了!

Code

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

const int N = 1000+9;

int n,m,val[N][N],f[N][N],g[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	for (int T=read();T;T--) {
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		m = read(); n = read();
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				val[i][j] = read();
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=m,cur=0;j;j--) {
				f[i][j] = cur + val[i][j];
				cur = max(cur, g[j]);
				g[j] = max(g[j], f[i][j]);
			}
		}
		int vout = 0;
		for (int i=1;i<=m;i++) 
			vout = max(vout, g[i]);
		printf("%d\n",vout);
	}
	return 0;
}

【Codeforces 559E】Gerald and Path

相关链接

题目传送门:http://codeforces.com/contest/559/problem/E
官方题解:http://codeforces.com/blog/entry/19237
中文题面:http://blog.csdn.net/mengzhengnan/article/details/47057557

解题报告

这题官方题解是$O(n^4)$的
然而评论区给出了$O(n^3)$甚至$O(n^2)$的算法
不过评论区并没有给题解,只是扔了两份非常不可读的代码
于是我一个都没有懂 QwQ
后来自己想了一个$O(n^3)$的DP,来说一说吧!

考虑最常规的$DP$式子$f[i][j]$表示用了前$i$个路灯,已被照亮的区间的最右端点为$j$
这样的话,只有一种情况会出现问题:

ps:红色的部分会被漏掉
于是我们就预处理出所有路灯向左照的时候覆盖情况
因为超过第i个路灯的位置并且对答案有贡献的路灯最多一个
所以我们就可以枚举是那个路灯超过了i
这样的话,新增转移多了$n^2$个
又因为每一个转移会被使用$O(n)$次,于是总的时间复杂度为:$O(n^3)$

Code

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

const int N = 300+9;

int n,tot,Hash[N],f[N][N];
struct Mat{int p,l;}m[N];
struct Trans{int l,r,mx;};
vector<Trans> t[N]; 

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Val(int p, int l, int r) {
	if (r <= p) return 0;
	if (l >= p) return Hash[r] - Hash[l];
	return Hash[r] - Hash[p];
}

int main() {
	n = read(); 
	for (int i=1,p,l;i<=n;i++) {
		p = read(); l = read();
		Hash[++tot] = p;
		Hash[++tot] = p + l;
		Hash[++tot] = p - l;
		m[i] = (Mat){p,l};
	}
	auto cmp = [](const Mat &A, const Mat &B) {return A.p < B.p;};
	sort(m+1, m+1+n, cmp);
	sort(Hash+1, Hash+1+tot);
	tot = unique(Hash+1, Hash+1+tot) - Hash - 1;
	for (int i=1,r,l;i<=n;i++) {
		r = m[i].p; l = m[i].p-m[i].l;
		for (int j=1,cr,cl;j<i;j++) {
			if (l > m[j].p) continue;
			cr = max(r, m[j].p+m[j].l); cl = l;
			for (int k=j+1;k<i;k++) 
				cl = min(cl, m[k].p-m[k].l);
			cl = lower_bound(Hash+1, Hash+1+tot, cl) - Hash;
			cr = lower_bound(Hash+1, Hash+1+tot, cr) - Hash;
			t[j].push_back((Trans){cl,cr,i});
		}
		l = lower_bound(Hash+1, Hash+1+tot, l) - Hash;
		r = lower_bound(Hash+1, Hash+1+tot, r) - Hash;
		t[i].push_back((Trans){l,r,i});
		l = m[i].p; r = m[i].p + m[i].l;
		l = lower_bound(Hash+1, Hash+1+tot, l) - Hash;
		r = lower_bound(Hash+1, Hash+1+tot, r) - Hash;
		t[i].push_back((Trans){l,r,i});
	}
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=tot;j++) 
			f[i][j] = max(f[i][j], f[i-1][j]);
		for (int k=t[i].size()-1,l,r,mx;~k;k--) {
			l = t[i][k].l; r = t[i][k].r; mx = t[i][k].mx;
			for (int j=1;j<=tot;j++) {
				if (j >= r) break;
				f[mx+1][r] = max(f[mx+1][r], f[i][j] + Val(j, l, r));
			}
		}
	}
	int vout = 0;
	for (int i=1;i<=n+1;i++) {
		for (int j=1;j<=tot;j++) {
			vout = max(vout, f[i][j]);
		}
	}
	printf("%d\n",vout);
	return 0;
}

【BZOJ 3992】[SDOI2015] 序列统计

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3992
Latex题面:http://paste.ubuntu.com/23997878/
数据生成器:http://paste.ubuntu.com/24006205/
神犇题解:http://www.cnblogs.com/gromah/p/4431016.html
NTT相关:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-13

解题报告

这题$O(m^3logn)$的基于矩阵快速幂的算法大家都会吧?
然而只能通过 $60\% $ 的数据 QwQ

然后就需要一点黑科技了
考虑模数这么奇怪,于是可能是用元根来搞一搞
然后我们发现,我们可以用元根的幂次来表示 $0 \sim m – 1$ 的每一个数
于是我们就可以把乘法换成幂次的加法,于是就可以搞NTT了!
于是用NTT来搞生成函数,复杂度:$O(nmlogm)$
然后再套上一开始讲的快速幂,那么就是$O(mlogmlogn)$的复杂度啦!

Code

话说这似乎是第一次撸$NTT$呢!
还有一点小激动啊!
不过这一份代码封装太多了,好慢啊 QwQ

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

const int N = 9000;
const int M = N << 2;
const int MOD = 1004535809;

int l,n,m,x,pos[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int Pow(int w, int t, int mod) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%mod)
		if (t & 1) ret = (LL)ret * w % mod;
	return ret;
}

inline int Get_Primitive_Root(int w) {
	vector<int> pri; int cur = w - 1;
	for (int i=2,lim=ceil(sqrt(w));i<=cur&&i<=lim;i++) {
		if (cur % i == 0) {
			pri.push_back(i);
			while (cur % i == 0) cur /= i;
		}
	}
	if (cur > 1) pri.push_back(cur);
	if (pri.empty()) return 2;  
	for (int i=2;;i++) {
		for (int j=pri.size()-1;j>=0;j--) {
			if (Pow(i, w/pri[j], w) == 1) break;
			if (!j) return i;
		}
	}
}

struct Sequence{
	int a[M],POS[M],len;
	inline Sequence() {}
	inline Sequence(int l) {
		memset(a,0,sizeof(a));
		len = l; a[0] = 1;
	}
	inline Sequence(Sequence &B) {
		memcpy(this, &B, sizeof(B));
		len=B.len;
	}
	inline void NTT(int f) {
		static const int G = Get_Primitive_Root(MOD);
		int l = -1; for (int i=len;i;i>>=1) l++;
		if (!POS[1]) {
			for (int i=1;i<len;i++) { 
				POS[i] = POS[i>>1]>>1;
				if (i & 1) POS[i] |= 1 << l-1;
			} 
		}
		for (int i=0;i<len;i++) if (POS[i] > i) 
			swap(a[i], a[POS[i]]);
		for (int seg=2;seg<=len;seg<<=1) {
			int wn = Pow(G, MOD/seg, MOD);
			if (f == -1) wn = Pow(wn, MOD-2, MOD);
			for (int i=0;i<len;i+=seg) {
				for (int k=i,w=1;k<i+seg/2;k++,w=(LL)w*wn%MOD) {
					int tmp = (LL)w * a[k+seg/2] % MOD;
					a[k+seg/2] = ((a[k] - tmp) % MOD + MOD) % MOD;
					a[k] = (a[k] + tmp) % MOD;
				}
			}
		}
		if (f == -1) { 
			for (int i=0,rev=Pow(len,MOD-2,MOD);i<len;i++) 
				a[i] = (LL)a[i] * rev % MOD;
		}
	}
	inline void Multiply(Sequence B) {
		NTT(1); B.NTT(1);
		for (int i=0;i<len;i++)
			a[i] = (LL)a[i] * B.a[i] % MOD;
		NTT(-1); 
		for (int i=m-1;i<len;i++) 
			(a[i-m+1] += a[i]) %= MOD, a[i] = 0;
	} 
	inline void pow(int t) {
		Sequence ret(len),w(*this);
		for (;t;t>>=1,w.Multiply(w)) 
			if (t & 1) ret.Multiply(w);
		memcpy(this, &ret, sizeof(ret));
	}
}arr;

int main() {
	l = read(); m = read();
	x = read() % m; n = read();
	int PRT = Get_Primitive_Root(m);
	for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i;
	for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0;
	int len = 1; while (len < m) len <<= 1;
	arr.len = len << 1; arr.pow(l); 
	printf("%d\n",(arr.a[pos[x]]+MOD)%MOD);
	return 0;
}