【BZOJ 4197】[NOI2015] 寿司晚宴

相关链接

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

解题报告

考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$

Code

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

const int N = 509;
const int M = 6561;

int pri[] = {2, 3, 5, 7, 11, 13, 17, 19};
int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3];
LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M];
vector<int> sta[N];

inline void relax(LL &a, LL b) {
	a = (a + b) % MOD;
}

inline int num(int x, int t) {
	for (; t; x /= 3, t--);
	return x % 3;
}

inline int SET(int w, int t, int v) {
	static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187};
	int ret = 0;
	for (int i = 0; i < 8; i++, w /= 3, t >>= 1) {
		if (t & 1) {
			ret += buf[i] * v;
		} else {
			ret += buf[i] * (w % 3);
		}
	}
	return ret;
}

int main() {
	freopen("dinner.in", "r", stdin);
	freopen("dinner.out", "w", stdout);
	cin>>n>>MOD; 
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < 8; j++) {
			int t = num(i, j);
			if (t == 1) {
				sta1[i] |= 1 << j;
			} else if (t == 2) {
				sta2[i] |= 1 << j;
			}
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < (1 << 8); j++) {
			for (int k = 1; k <= 2; k++) {
				tt[i][j][k] = SET(i, j, k);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		gpri[i] = i;
		for (int j = 0; j < 8; j++) {
			if (gpri[i] % pri[j] == 0) {
				spri[i] |= (1 << j);
				while (gpri[i] % pri[j] == 0) {
					gpri[i] /= pri[j];
				}
			}
		}
	}
	f = arr1, g = arr2, h = arr3;
	g[0] = f[0] = 1;
	for (int i = 2; i <= n; i++) {
		if (gpri[i] == 1) {
			for (int j = M - 1; ~j; j--) {
				if (g[j]) {
					int sta = 0;
					for (int k = 0; k < 8; k++) {
						if (spri[i] >> k & 1) {
							sta |= num(j, k);
						}
					}
					if (sta == 0) {
						relax(f[tt[j][spri[i]][1]], g[j]);
						relax(f[tt[j][spri[i]][2]], g[j]);
					} else if (sta < 3) {
						relax(f[tt[j][spri[i]][sta]], g[j]);
					}
				}
			}
			memcpy(g, f, sizeof(arr1));
			swap(f, g);
		} else {
			sta[gpri[i]].push_back(spri[i]);
		}
	}
	for (int i = 2; i <= n; i++) {
		if (!sta[i].empty()) {
			memcpy(h, g, sizeof(arr1));
			memcpy(ori, g, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (g[k]) {
						int s1 = vv & sta1[k];
						if (!s1) {
							relax(f[tt[k][vv][2]], g[k]);
						} 
					}
				}
				memcpy(g, f, sizeof(arr1));
				swap(f, g);
			}
			memcpy(f, h, sizeof(arr1));
			for (int j = 0; j < (int)sta[i].size(); j++) {
				int vv = sta[i][j];
				for (int k = M - 1; ~k; k--) {
					if (h[k]) {
						int s2 = vv & sta2[k];
						if (!s2) {
							relax(f[tt[k][vv][1]], h[k]);
						}
					}
				}
				memcpy(h, f, sizeof(arr1));
				swap(f, h);
			}
			for (int k = 0; k < M; k++) {
				f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD;
			}
		}
	}
	LL ans = 0;
	for (int i = 0; i < M; i++) {
		relax(ans, f[i]);
	}
	printf("%lld\n", ans);
	return 0;
}

【TopCoder SRM713】DFSCount

相关链接

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

题目大意

给定一个$n(n \le 14)$的简单无向图,问$DFS$序总共可能有多少种不同情况

解题报告

这是一个非常妙妙的$DP$
考虑定义$f_{i,j}$表示当前在第$i$个点,已经走过的点压成二进制状态为$j$
但我们发现这样无法实现$DFS$模拟当中的退回操作

但我们考虑一下$DFS$树:这货是没有横叉边的,只有返祖边
这意味着我们如果决定朝一个方向走,那么一定是把那一个连通块走完才会退回来
于是我么可以不一步一步转移,我们可以把一整块连通块一起转移,这样就不需要模拟$DFS$的回退操作了

至于这份代码是:$O(n^2 2^n)$的
实现得精细一点可以做到$O(n 2^n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
int n,id[15];
bool g[15][15],vis[15];
LL f[15][17000],pw[15],pol[15];

class DFSCount {
    public:
    	long long count(vector<string> G) {
    		pw[0] = 1;
    		for (int i=1;i<=14;i++) {
				pw[i] = pw[i-1] * i;
			}
    	    n = G.size();
    	    for (int i=0;i<n;i++) {
				for (int j=0;j<n;j++) {
					if (G[i][j] == 'Y') g[i][j] = 1;
					else g[i][j] = 0;
				}
			}
    	    memset(f, 0, sizeof(f));
			for (int i=0;i<n;i++) {
				f[i][(1<<n)-1] = 1;
			}
			for (int sta=(1<<n)-2;sta>0;sta--) {
				for (int i=0;i<n;i++) {
					if (!(sta&(1<<i))) continue;
					for (int j=0;j<n;j++) {
						vis[j] = (sta & (1 << j));
					}
					int cnt = 0;
					for (int j=0;j<n;j++) {
						if (g[i][j] && !(sta&(1<<j))) {
							if (!vis[j]) {
								DFS(j, ++cnt);
								pol[cnt] = 0;
							}
							pol[id[j]] += f[j][(1<<j)|sta];
						}
					}
					f[i][sta] = pw[cnt];
					for (int j=1;j<=cnt;j++) {
						f[i][sta] *= pol[j];
					}
				}
			}
			LL ret = 0;
			for (int i=0;i<n;i++) {
				ret += f[i][1<<i];
			}
			return ret;
   		}
   	private:
   		void DFS(int w, int ID) {
			vis[w] = 1; 
			id[w] = ID;
			for (int i=0;i<n;i++) {
				if (g[w][i] && !vis[i]) {
					DFS(i, ID);
				} 
			}   
		}
};

【HDU 4626】Jinkeloid

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4626
数据生成器:http://paste.ubuntu.com/24454724/
神犇题解Ⅰ:https://blog.sengxian.com/solutions/hdoj-4626
神犇题解Ⅱ:http://blog.csdn.net/u012345506/article/details/52040466
FWT相关:http://blog.csdn.net/liangzhaoyang1/article/details/52819835

解题报告

我们使用状压$DP$的话,每次询问相当于强制某些位为$0$
于是我们可以先$FWT$一发,搞出每个状态的方案数
然后我们可以再做一发子集$DP$,搞出每个状态的超集
然后询问就可以$O(1)$回答了
于是总的时间复杂度是:$O(20 \cdot 2^{20} + m + n)$

另外的话,因为本题的$k$非常的小
于是之前$FWT$那一块还可以用容斥来解决
只不过这样单次询问的复杂度是:$O(3^k)$的

Code

这个代码里$DP$超集那一块还是很妙妙的

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

const int N = 3000000;
const int M = 100009;
const int UNIVERSE = (1 << 20) - 1; 
const int SGZ = 20;

char pat[M];
int n,m,sta;
LL a[N],f[N],zero;

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 void FWT(LL *arr, int len, int ty) {
	for (int d=1;d<len;d<<=1) {
		for (int i=0;i<=len;i+=d*2) {
			for (int j=0;j<d;j++) {
				LL t1 = arr[i+j], t2 = arr[i+j+d];
				arr[i+j] = t1 + t2;
				arr[i+j+d] = t1 - t2;
				if (ty == -1) {
					arr[i+j] /= 2;
					arr[i+j+d] /= 2;
				}
			}
		}
	}
}	

int main() {
	for (int T=read();T;T--) {
		memset(a, 0, sizeof(a));
		scanf("%s",pat);
		n = strlen(pat);
		a[0]++; sta = zero = 0;
		for (int i=0;i<n;i++) {
			sta ^= 1 << pat[i] - 'a';
			zero += a[sta]++;
		}  
		FWT(a, UNIVERSE, 1);
		for (int i=0;i<=UNIVERSE;i++) {
			a[i] = a[i] * a[i];
		}
		FWT(a, UNIVERSE, -1);
		a[0] = zero;
		for (int i=1;i<=UNIVERSE;i++) {
			a[i] /= 2;
		}
		for (int i=0;i<=UNIVERSE;i++) {
			if ((i ^ UNIVERSE) < i) {
				swap(a[i], a[i^UNIVERSE]); 
			}
		}
		for (int j=0;j<SGZ;j++) {
			for (int i=0;i<=UNIVERSE;i++) {
				if (i & (1<<j)) {
					a[i^(1<<j)] += a[i];
				}
			}
		}	
		m = read();
		for (int tt=1;tt<=m;tt++) {
			int k = read(), sta = 0;
			for (int i=1;i<=k;i++) {
				scanf("%s",pat);
				sta |= 1 << pat[0] - 'a';
			}
			printf("%lld\n",a[sta]);
		}
	}
	return 0;
}

【HDU 4623】Crime

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4623
神犇题解:http://blog.csdn.net/keshuai19940722/article/details/49455357

解题报告

脑袋里一直想着去年$ZJOI$的小星星
然后就各种优化,最后还是$T$成狗 QwQ

然后正解就是把每个数按照因数种类不同分组
最后搞下来只有$14$种不同的,然后暴力状压$DP$就可以了

Code

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

const int N = 3000000;
const int M = 16;

int n,mx,MX,MOD,f[N][M],cnt[M],bit[M],cur[M],sym[M],suf[M],leg[M][M];
int ty[]={0,1,2,3,2,4,5,6,2,3,7,8,5,9,10,11,2,1,5,1,7,12,13,1,5,4,14,3,10};

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 decode(int w, int *arr) {
	for (int i=mx;i;i--) {
		arr[i] = w % bit[i];
		w /= bit[i];
	}
}

inline int solve() {
	memset(cnt,0,sizeof(cnt));
	mx = MX = 0;
	for (int i=1;i<=n;i++) {
		cnt[ty[i]]++;
		mx = max(mx, ty[i]);
	}
	for (int i=1;i<=mx;i++) {
		bit[i] = cnt[i] + 1;
		MX = MX * bit[i] + cnt[i];
	}
	suf[mx] = 1;
	for (int i=mx-1;i;i--) {
		suf[i] = suf[i+1] * bit[i+1];
	}
	memset(f,0,sizeof(f));
	f[0][0] = 1;
	for (int i=0;i<MX;i++) {
		decode(i, cur);
		for (int j=0;j<=mx;j++) {
			if (!f[i][j]) continue;
			for (int k=1;k<=mx;k++) {
				if ((leg[k][j] || !j) && cur[k] < cnt[k]) {
					int to = i + suf[k];
					f[to][k] = (f[to][k] + (LL)f[i][j] * (cnt[k] - cur[k])) % MOD;
				}
			}
		}
	}
	int ret = 0;
	for (int i=1;i<=mx;i++) {
		ret = (ret + f[MX][i]) % MOD;
	}
	return ret;
}

int main() {
	for (int i=1;i<=28;i++) {
		if (sym[ty[i]]) continue;
		sym[ty[i]] = i;
	}
	for (int i=1;i<=14;i++) {
		for (int j=1;j<=14;j++) {
			if (gcd(sym[i], sym[j]) == 1) {
				leg[i][j] = 1;
			}
		} 
	}
	for (int T=read();T;T--) {
		n = read(); MOD = read();
		printf("%d\n",solve());
	}
	return 0;
}

【HDU 4628】Pieces

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4628

解题报告

这题只是划分子序列,于是我们可以状压DP
用枚举子集的话,时间复杂度就是:$O(3^n)$的

Code

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

char s[20];
int n,f[1<<17];

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 judge(int x) {
    int tot=0; char tmp[20];
    for (int i=1;i<=n;i++,x>>=1) {
        if (x&1) {
            tmp[++tot] = s[i];
        }
    }
    for (int i=1,j=tot;i<j;i++,j--) {
        if (tmp[i] != tmp[j]) {
            return 0;
        }
    }
    return 1;
}

int main() {
    for (int T=read();T;T--) {
        memset(f,60,sizeof(f));
        scanf("%s",s+1); 
        n = strlen(s+1);
        for (int i=1,MX=1<<n;i<MX;i++) {
            if (judge(i)) {
                f[i] = 1;
            } else {
                for (int j=i;j;j=(j-1)&i) {
                    f[i] = min(f[i], f[j] + f[i^j]);
                }
            } 
        }    
        printf("%d\n",f[(1<<n)-1]);
    } 
    return 0;
}

【日常小测】迷宫

题目大意

给定一个$n \times 6(n \le 10^9)$的方格纸,你需要在每一个方格中填上一个$[1,6]$之间的数
要求任意一个数与它↙,←,↖,↗,→,↘这六个方向的数既不能相同,也不能和为7
并且规定左上角必须为$1$,且按照先从上往下逐行再从左往右的顺序,第一个$2$必须要出现在$5$之前,第一个$3$必须要出现在$4$之前
问有多少种合法的填色方案,输出对$1004535809$取模

解题报告

先不考虑最后题解的关于出现顺序的限制。这样的话,显然可以矩阵快速幂
但直接压状态的的话,矩阵大概长成$10^4 \times 10^4$,单次矩阵乘法都无法满足
不过我们仔细观察即可发现,对于其实1,6是等价的,同理2,53,4
于是我们每一个格子的状态就只有三种了,最后有效的状态一行只有96
这样就可以直接矩阵快速幂了

现在考虑最后的那个限制,我们可以容斥一下
我们可以先排除掉不包含2,5这一对的方案数,然后除以二
同理3,4也一样处理

于是最后就是一个状压DP用矩阵快速幂优化
最后再容斥一下,时间复杂度:$O(96 ^ 3 \log n)$

Code

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

const int MOD = 1004535809;

int n,tot,vout,sta[100][7],cur[7];
struct Matrix{
	int f[100][100];
	inline Matrix() {memset(f,0,sizeof(f));}
	inline Matrix(int x) {memset(f,0,sizeof(f));for(int i=1;i<=tot;i++)f[i][i]=x;}
	inline Matrix(const Matrix &M) {for(int i=1;i<=tot;i++)for(int j=1;j<=tot;j++)f[i][j]=M.f[i][j];}
	inline Matrix operator * (const Matrix &M) {
		Matrix ret;
		for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++) for (int k=1;k<=tot;k++) 
			ret.f[i][k] = (ret.f[i][k] + (LL)f[j][k] * M.f[i][j]) % MOD;
		return ret;
	}
	inline Matrix operator ^ (int t) {
		Matrix ret(1),tmp(*this);
		for (;t;t>>=1,tmp=tmp*tmp)
			if (t&1) ret=ret*tmp;
		return ret;
	}
	inline void out() {
		for (int i=1;i<=tot;i++) {
			for (int j=1;j<=tot;j++) {
				printf("%d ",f[j][i]);
			} cout<<endl;
		}
	}
}ans,trans;

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 w, int v) {
	if (w == 7) {
		memcpy(sta[++tot],cur,sizeof(cur));
	} else {
		for (int i=1;i<=3;i++) if (i != v) 
			cur[w] = i, DFS(w+1, i);
	}
}

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

inline bool check(int a, int b) {
	for (int i=1;i<=6;i++) {
		if (i > 1 && sta[a][i-1] == sta[b][i]) return 0;
		if (i < tot && sta[a][i+1] == sta[b][i]) return 0;
	} return 1;
}

int main() {
	freopen("board.in","r",stdin);
	freopen("board.out","w",stdout);
	n = read(); DFS(1, -1);
	for (int i=1;i<=tot;i++) for (int j=1;j<=tot;j++)
		if (check(i, j)) trans.f[j][i] = 1 << 6;
	for (int i=1;i<=tot;i++) if (sta[i][1] == 1) ans.f[i][1] = 1 << 5;
	trans = trans ^ (n - 1); ans = ans * trans;
	for (int i=1;i<=tot;i++) vout = (vout + ans.f[i][1]) % MOD; 
	vout = (vout - 2ll * Pow(2, n * 6ll - 1)) % MOD; 
	vout = (LL)vout * Pow(4, MOD-2) % MOD;
	vout = (vout + Pow(2, n * 6ll - 1)) % MOD; 
	printf("%d\n",(vout+MOD)%MOD);
	return 0;
}

【BZOJ 4635】数论小测验

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4635
数据生成器:http://paste.ubuntu.com/24360378/
神犇题解:http://www.cnblogs.com/clrs97/p/5625508.html

解题报告

对于第一问,显然可以用莫比乌斯反演做到$O(Tm)$

对于第二问,考虑枚举$k$,然后$10^3$以内的数最多有$4$种不同的质因数
于是搞一个状压$DP$,用矩阵快速幂优化
单词询问时间复杂度:$O(32m^2 + 32^3 log (n))$
看起来蛮有希望过的,但卡了一下午常也没有卡过 QwQ

正解的话,我们可以学习Claris用容斥
具体来讲枚举$k$,然后枚举$k$的每一个质因数是否满足条件
然后配合一点预处理之类的,就可以做到$O(m^2 + m \log m)$了

Code

这份代码在BZOJ被卡常了 QwQ

#include<bits/stdc++.h>
#define LL long long
using namespace std; 
 
const int MOD = 1000000007;
const int N = 10000009;
const int M = 32;
 
int n,m,SZ,s1[N],hc[N],to[1001];
int tot,pri[N>>3],mu[N]; bool vis[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 ret = 1;
    for (;t;t>>=1,w=(LL)w*w%MOD) 
        if (t&1) ret=(LL)ret*w%MOD;
    return ret;
}
 
inline void GetMu() {
    mu[1] = 1;
    for (int i=2;i<N;i++) {
        if (!vis[i]) mu[i] = -1, pri[++tot] = i;
        for (int j=1;j<=tot&&pri[j]*i<N;j++) {
            vis[i*pri[j]] = 1;
            if (i%pri[j]) mu[i*pri[j]] = -mu[i];
            else {mu[i*pri[j]] = 0; break;}
        } 
        mu[i] = mu[i-1] + mu[i];
    } 
}
 
inline int cal(int mx) {
    int ret = 0;
    for (int l=1,r,tmp;l<=mx;l=r+1) {
        r = mx / (mx / l);
        tmp = (LL)(mu[r] - mu[l-1]) * hc[mx/l] % MOD;
        ret = (ret + tmp) % MOD;
    }
    return (ret + MOD) % MOD;
}
 
struct Matrix{
    int a[M][M];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(const Matrix *A) {
        for (int i=0;i<M;i++) for (int j=0;j<M;j++) a[i][j] = A->a[i][j];
	}
    inline Matrix(int x) {
        memset(a,0,sizeof(a)); 
        for (int i=0;i<SZ;i++) a[i][i] = x;
    } 
    inline void operator *= (const Matrix &A) {
        Matrix ret; 
        for (int i=0,*t1,*t3;i<SZ;i++) {
        	t1 = ret.a[i]; const int *t2 = A.a[i];
			for (int j=0;j<SZ;j++) {
				t3 = a[j];
				for (int k=0;k<SZ;k+=4) { 
					t1[k] = (t1[k] + (LL)t3[k] * t2[j]) % MOD; 
					t1[k+1] = (t1[k+1] + (LL)t3[k+1] * t2[j]) % MOD; 
					t1[k+2] = (t1[k+2] + (LL)t3[k+2] * t2[j]) % MOD;
					t1[k+3] = (t1[k+3] + (LL)t3[k+3] * t2[j]) % MOD;
				}
			}
		}
        for (int i=0;i<SZ;i++) for (int j=0;j<SZ;j++) a[i][j] = ret.a[i][j];
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this);
        for (;t;t>>=1,w*=w) if (t&1) ret*=w;
        return ret;
    }
}ans,trans;
 
inline int solve(int w) {
    tot = 0; 
    for (int i=2,tmp=w;i<=tmp;i++) {
        if (tmp % i == 0) {
            pri[++tot] = i; tmp /= i;
            while (tmp % i == 0) pri[tot] *= i, tmp /= i;
        }
    } 
    ans = Matrix(); trans = Matrix(); 
    ans.a[0][0] = 1; SZ = 1 << tot;
    memset(to,0,sizeof(to));
    for (int i=1,t=1,ww;ww=pri[i],i<=tot;i++,t<<=1) 
		for (int j=ww;j<=m;j+=ww) to[j] |= t;
    for (int i=1,tt;tt=to[i],i<=m;i++) {
        for (int p=0,ww;ww=p,p<SZ;p++) 
            ++trans.a[p|tt][p];
    }
    trans = trans ^ n;
    ans *= trans;
    return ans.a[SZ-1][0];
}
 
int main() {
    int T = read(), type = read();
    if (type == 1) {
        GetMu(); 
        for (int t=1,vout;vout=0,t<=T;t++) {
            n = read(); m = read(); 
            int L = read(), R = read();
            for (int l=1,r;l<=m;l=r+1) {
                r = m / (m / l);
                hc[m / l] = Pow(m / l, n);
            }
            for (int l=L,r,tmp;l<=R;l=r+1) {
                r = m / (m / l); tmp = cal(m / l);
                vout = (vout + (min(r,R)-max(L,l)+1ll) * tmp) % MOD;
            }           
            printf("%d\n",vout);
        }
    } else if (type == 2) {
        for (int t=1,vout,l,r;vout=0,t<=T;t++) {
            n = read(); m = read(); l = read(), r = read();
            for (int w=l;w<=r;w++) vout = (vout + solve(w)) % MOD;
            printf("%d\n",vout);
        }
    }
    return 0;
}

【BZOJ 3925】[ZJOI2015] 地震后的幻想乡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3925
神犇题解Ⅰ:http://blog.csdn.net/skywalkert/article/details/47792065
神犇题解Ⅱ:http://www.cnblogs.com/yousiki/p/6437155.html

解题报告

题目上说:

对于$n$个$[0,1]$之间的随机变量$x_1,x_2,\cdots ,x_n$,第$k$小的那个的期望值是$\frac{k}{n+1}$

即加入$k$条边后恰好有生成树的情况的最大边的期望权值为$\frac{k}{n+1}$
设$g_k$为加入$k$条边后恰好使所有点连通的方案数
于是原题的答案为$\frac{1}{m+1}\sum\limits_{i=1}^{m}{\frac{i \cdot g_i}{m \choose i}}$

设$f_k$为加入$k$条边后原图不连通的方案数
我们可以交换一下求和顺序可使答案变为:$\frac{1}{m+1}\sum\limits_{i=0}^{m}{\frac{f_i}{m \choose i}}$
于是问题变为求$f_k$与$g_k$

我们首先可以发现,$f_k$加$g_k$一定等于所有的方案
那么设点集$S$的诱导子图中的边数为$cnt_{S}$,仅对于点集$S$有效的$f_k,g_k$为$f_{S,k},g_{S,k}$
则有:$f_{S,k}+g_{S,k}={cnt_S \choose k}$,于是只需要求出$g_{S,k},f_{S,k}$中的任意一个

类比带标号的连通图计数,我们可以列出递推式:$f_{S,i+j} = \sum\limits_{T \subset S}{g_{T,i} {cnt_{S-T} \choose j}}$
又$g_{S,k}={cnt_S \choose k} – f_{S,k}$,所以这个递推式可以直接递推
于是这题就做完啦!时间复杂度:$O(m 4^n)$
又因为上述$T \subset S$所以我们直接枚举子集,复杂度优化到$O(m 3^n)$

【BZOJ 4607】[PA2015 Final] Edycja

相关链接

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

前言

这题大概放了三个月了
每一次清理题目的时候都会翻出这个题
然后看一两个小时又扔回去,因为不会啊

解题报告

就是先有一个结论:一号操作最后做不会使答案变劣
然后还有一个结论:对于每一种字符,至多进行一次二号操作
这两个似乎比较显然,想一想都能想出来

有了这两个结论之后我们就可以得到一个贪心的策略:

定义$tra(x,y)$为所有最开始为$x$的位置在目标串中不为$y$的个数
对于每一种字符$c$我们,我们找到字符$g_c$($g_c$可能等于$c$)
满足$g_c$能使$tra(c,g_c)$最小

考虑将26个字符看成26个点,把$g_c$看作由$c$连向$g_c$的一条边,这显然是一个图
如果这个图上不存环,那么此时已经是最优解。

但如果有环,则你不能找到一种合法的交换顺序,这是不合法的
另外,需要注意,如果一个连通块是一个内向树,则我们是可以多花费一次二号操作的代价使其合法的
比如下面这个图,我们可以先将$a$移动到$e$,然后移动环上的其他字符,最后把$e$移到$a$:

刚刚有说,如果有环,那么环是不合法的,于是我们需要调整一些出边,来破坏掉环
这里又有一个结论:我们破坏环的过程不会产生新的环,这个看起来非常显然,详细证明可以找Claris
至于破坏掉环的过程非常复杂,不能贪心,但我们注意到环的个数最多为13,所以我们可以用状压DP来做
于是这题嘴巴上就做完了!但感觉细节非常多的样子,于是就不写代码了(逃

【日常小测】排列

题目大意

给定$n(n \le 10^9),k(k \le 4)$,定义$p_i$为排列中第$i$个数
询问长度为$n$且$|p_i-i| \le k$的排列的个数$\pmod {1e9+7}$

解题报告

不难发现$k$很小,于是我们可以状压DP
进一步观察,有用的状态只有70个
于是我们可以$O(70^3 \log n)$的复杂度用矩阵快速幂解决

不过这题还可以用线性$K$阶递推式的那个解法
用特征多项式做到一个比较优的复杂度
GEOTCBRL就是用这个A的,太强大了_(:з」∠)_

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
 
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 n,K,t,tot,itr[1000],num[1000];
struct Matrix{
    int a[70][70];
    inline Matrix() {memset(a,0,sizeof(a));}
    inline Matrix(Matrix *tmp) {memcpy(a,tmp->a,sizeof(a));}
    inline Matrix(int v) {memset(a,0,sizeof(a));for(int i=0;i<tot;i++)a[i][i]=v;}
    inline void reset() {memset(a,0,sizeof(a));}
    inline Matrix operator * (const Matrix &B) {
        Matrix ret;
        for (int i=0;i<tot;i++) for (int j=0;j<tot;j++) for (int k=0;k<tot;k++) 
            ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * B.a[i][k]) % MOD;
        return ret;
    }
    inline Matrix operator ^ (int t) {
        Matrix ret(1),w(this); 
        for (;t;t>>=1,w=w*w)
            if (t&1) ret=ret*w;
        return ret;
    }
}ans,tra;
 
int main() {
    for (;~scanf("%d%d",&n,&t);tot=0) {
        t <<= 1; K = 1 << t;
        ans.reset(); tra.reset();
        for (int i=0;i<K;i++) {
            if (__builtin_popcount(i) != t/2) continue;
            else itr[i] = tot, num[tot++] = i;
        }
        for (int h=0,cur,i;i=num[h],h<tot;h++) {
            for (int j=0;j<=t;j++) {
                if (i&(1<<j)) continue;
                cur = i | (1 << j);
                if (!(cur&1)) continue;
                tra.a[h][itr[cur>>1]] = 1;
            }
        } 
        t = itr[(1<<(t/2))-1]; ans.a[t][0] = 1; 
        tra = tra ^ n; ans = ans * tra;  
        printf("%d\n",ans.a[t][0]);
    }
    return 0;
}

【BZOJ 4762】最小集合

相关链接

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

吐槽

这题之前在绍一集训的时候就考过一次,今天又考了
但还是写炸了,或许老年选手不适合写代码吧!

解题报告

为了代码好写,我们先按照二进制位取反
这样的话,问题变为选出一些数,使其或起来为全集,且少一个都不行

我们考虑$f[i][j]$为将前$i$个数加入集合之后,或起来为$j$的方案数
这样可以防止一个数被之前的数代替,但对于之后的数却无能为力
于是我们加一维$f[i][j][k]$,其中$k$表示后面的数或起来为$k$

这样就可以使用类似容斥的思想进行两种转移

  1. $f[i][j][k] \to f[i+1][j|a_i][k-(k \& a_i)]$表示不强制非法
  2. $-f[i][j][k] \to f[i+1][j|a_i][(k-(k \& a_i))|(a_i-(a_i \& j))]$表示强制非法
    ps: 根据容斥原理,第二种转移会配上$-1$的系数

此时我们已经可以进行$O(n \cdot 4^{\omega})$的DP了
再仔细想想,第三维一定是第二维的子集,于是复杂度降到$O(n \cdot 3^{\omega})$

Code

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

const int N = 1001;
const int M = (1 << 10) - 1;
const int MOD = 1000000007;

int n,vout,a[N],f[1<<10][1<<10];

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();
	for (int i=1;i<=n;i++) a[i] = read() ^ M;
	f[0][0] = 1; 
	for (int t=1;t<=n;t++) {
		for (int i=M,ti,tj,uni;~i;--i) {
			if ((ti = (a[t] | i)) > i) {
				uni = ti - i;
				for (int j=i;;(--j)&=i) {
					tj = (j - (j & a[t]));
					f[ti][tj] = (f[ti][tj] + f[i][j]) % MOD;
					f[ti][tj|uni] = (f[ti][tj|uni] - f[i][j]) % MOD;
					if (!j) break;
				}
			}
		}
	}
	printf("%d\n",(f[M][0]+MOD)%MOD);
	return 0;
}

【BZOJ 4416】[SHOI2013] 阶乘字符串

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4416
神犇题解Ⅰ:http://blog.csdn.net/flaze_/article/details/52607165
神犇题解Ⅱ:http://309459245.lofter.com/post/1dd7269e_a37f28d

解题报告

第一次做这么神奇的判定性题目
感觉非常神奇啊!神清气爽!

闲来无事写了一份beamer,大家随便看看吧
另外,这货的证明是错的:http://blog.csdn.net/horizon_smz/article/details/50905084
slide

Code

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

const int N = (1<<21) + 9;
const int M = 500;
const int SGZ = 21;

int n,m,f[N],last[SGZ],nxt[M][21];
char pat[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();T;T--) {
		m = read();
		scanf("%s",pat+1);
		n = strlen(pat+1);
		if (m > 21) {
			puts("NO");
			continue;
		}
		for (int i=0;i<m;i++) 
			last[i] = nxt[n+1][i] = n + 1;
		for (int i=n;~i;i--) {
			for (int j=0;j<m;j++) 
				nxt[i][j] = last[j];
			if (i) last[pat[i]-'a'] = i;
		}
		for (int i=1,lim=1<<m;i<lim;i++) {
			f[i] = 0;
			for (int j=0;j<m;j++) {
				if (i & (1 << j)) {
					f[i] = max(f[i], nxt[f[i^(1<<j)]][j]);
				}
			}	
		}
		if (f[(1<<m)-1] <= n) puts("YES");
		else puts("NO");
	}
	return 0;
}

【BZOJ 4145】[AMPPZ2014] The Prices

相关链接

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

解题报告

先来说一个自己YY的暴力
枚举每一个合法集合,考虑这个集合的物品全部在某一个商店购买
如果我们把这些集合再拿来搞一搞组合,显然可以搞出来正确答案
使用背包DP的话,直接做复杂度是$O(4^m)$,考虑一点优化:
根据我们对于集合的定义,两个集合能够组合在一起,当且仅当两个集合没有交集
然后写个程序跑一跑,发现这种组合大概只会有4e7个,于是暴力搞一搞就好啦!
然后就垫底了 QwQ

现在考虑正解
刚刚我们其实是把整个商店买了哪些物品当作一个新物品,然后用新物品来进行背包DP
考虑我们直接把商店里面的物品拿来做背包DP会有什么问题:商店本身的花费$d_i$不好整
于是我们分阶段来背包DP,每一个商店一个阶段。
在这个阶段中,我们给所有状态加上这个商店的花费$d_i$,表示我们钦定这个商店要买东西
然后把物品拿来做背包,最后再和上个阶段的对应状态取个$min$
然后就做完啦!时间复杂度: $O(nm{2^m})$

Code

贴的这份代码是我YY的暴力

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

const int N = 100+9;
const int M = 65536;

int n,m,cost[N],f[M];
pair<int,int> que[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 w, int sta, int c) {
	if (w == m + 1) {
		f[sta] = min(f[sta], c);
	} else {
		DFS(w+1, sta, c);
		DFS(w+1, sta|(1<<w-1), c+cost[w]);
	}
}

void update(int t, int sta, int w) {
	if (t == m + 1) {
		f[sta|w] = min(f[sta|w], f[sta] + f[w]);
	} else {
		update(t+1, sta, w);
		if ((sta&(1<<(t-1))) == 0)
			update(t+1, sta, w|(1<<(t-1)));
	}
}

int main() {
	memset(f,60,sizeof(f));
	n = read(); m = read();
	for (int i=1,d;i<=n;i++) {
		d = read();
		for (int j=1;j<=m;j++) 
			cost[j] = read();
		DFS(1, 0, d);
	}
	for (int i=1,lim=1<<m;i<lim;i++)
		que[i] = make_pair(__builtin_popcount(i), i);
	sort(que+1, que+(1<<m));
	for (int i=1,lim=1<<m;i<lim;i++) 
		update(1, que[i].second, 0);
	printf("%d\n",f[(1<<m)-1]);
	return 0;
}

—————————— UPD 2017.2.7 ——————————
感觉使用以下代码来枚举子集可能会使我的暴力不那么接近于TLE:

for (int i=s;i;i=(i-1)&s) {}

【BZOJ 4006】[JLOI2015] 管道连接

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4006
神犇题解:http://www.cnblogs.com/lidaxin/p/5301180.html
斯坦纳树相关:http://endlesscount.blog.163.com/blog/static/821197872012525113427573/

解题报告

带关键点的最小生成树

好像在梦里见过的样子……
今天看到这个题居然想了很久这应该怎么做……

就是搞一个斯坦纳树就可以啦!
就是状压DP用SPFA的方式来更新

【BZOJ 3864】Hero meet devil

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3864
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4799463.html
神犇题解Ⅱ:http://blog.csdn.net/popoqqq/article/details/46826271
神犇题解Ⅲ:http://blog.csdn.net/u011542204/article/details/51674319

解题报告

一开始一眼看成了“最长公共子串”
居然心里在嘲讽 $ WJMZBMR$ 也有naive的时候

先考虑一个这样的状态:$f[i][j][k]$ 表示文本串匹配到第$i$位、模式串匹配到第$j$位、最长公共子序列长度为$k$个时的方案数
但这样直接转移是错误的,因为这会使第三维的$k$意义变为:“最长公共子序列长度至少为$k$”。比如下面这个例子:

文本串:$azbzcz$
模式串:$abcd$
现在考虑在文本串末尾加入$d$
则$f[6][3][2]$会转移到$f[7][4][3]$去
但$f[7][4][3]$这个状态根本就是非法的

于是为了解决这个问题,我们不得不预处理出那些状态/转移是合法的
但我们发现这样的话,一般的预处理必须依赖文本串长成啥样,但这样做是爆炸的
于是考虑一个新的定义:$f[i][a_1][a_2]\ldots[a_n]$ 表示文本串到第$i$位时,文本串匹配到第$j$位,LIS的长度为$a_j$的方案数
这样的话,如果我们始终保持进行最优的转移,就不需要记录文本串的状态了
另外,我们还可以优化,因为$f[i][j] \le f[i][j+1] \le f[i][j]+1$,于是我们可以打成差分,然后压成二进制状态$S$
于是我们的状态就变成了$f[i][S]$,再预处理出转移数组 $trans[S][C]$ 表示状态为$S$,加入字符$C$之后应该到的状态
于是进行类似的转移就可以啦:$f[i+1][trans[S][C]] = f[i+1][trans[S][C]] + f[i][S]$