2022/11/07-13 训练小记

P7961 [NOIP2021] 数列

显然是一个 \(dp\),首先考虑状态应如何设计。

看到 \(n\) 的限制,首先可以想到记一维 \(i\) 表示当前已被确定的 \(a\) 序列中的元素数量。

发现该题的难点在于从低位向高维的进位难以转移,因此我们可以从低位向高位考虑。

再开一维 \(j\) 表示当前考虑到了 \(S\) 的第 \(0\dots j\) 位,一维 \(p\) 表示第 \(0\dots j-1\) 向第 \(j\) 位的进位为 \(p\)

注意 \(p\) 可以大于 \(1\),即第 \(j\) 位的进位暂且不以二进制形式写开。

由于还有\(S\) 的二进制表示中 \(1\) 不多于 \(K\) 的限制,所以再记一个 \(k\) 表示当前 \(S\) 的第 \(0\dots j-1\) 位中已有 \(k\)\(1\)

这个时候枚举一个 \(t\) 表示我们添加了多少 \(2^j\)\(S\)\((i+t\leq n)\),这样一来,如果 \(p+t\) 为偶数,第 \(j\) 位就会在处理掉第 \(j\) 位的所有进位后变成 \(0\);反之则为 \(1\)。所以 \((p+t)\bmod 2\) 的值即为处理掉第 \(j\) 位的进位后第 \(j\) 位是否为 \(1\)。又因为每两个 \(1\) 可以向下一位进一个 \(1\),所以第 \(j\) 位对第 \(j+1\) 位会有 \(\lfloor \dfrac{p+t}{2} \rfloor\) 的进位。

综上所述,我们设计状态 \(dp(i,j,k,p)\) 表示 \(a\) 序列中已确定了 \(i\) 个元素,当前考虑到了 \(S\) 的第 \(0\dots j\) 位,当前 \(S\) 的第 \(0\dots j-1\) 位中有 \(k\)\(1\),第 \(0\dots j-1\) 向第 \(j\) 位的进位为 \(p\)。则 \(dp(i,j,k,p)\) 会向 $dp(i+t,j+1,k+(p+t)\bmod 2,\lfloor \frac{p+t}{2} \rfloor) $ 转移(枚举 \(t\in [0,n-i]\))。

由于答案满足分配律,不难想到 \(dp(i,j,k,p)\) 对新状态的贡献为

\[dp(i,j,k,p) \times {i+t\choose t}\times v_j^t \]

预处理一下组合数和 \(v_j\) 的幂次,即可做到 \(\mathcal{O}(n^4m)\) 转移。

转移的时候先枚举 \(j\) 再枚举 \(i\) 好像合理一些,但是先 \(i\)\(j\) 也过了QwQ

那么如何统计答案呢?由转移的过程不难想到统计答案时需要枚举 \(dp(n,m+1,?,?)\),枚举 \(k,p\) 即可。

\(k+\mathrm{popcnt}(p)\leq K\) 时答案是合法的,因为第 \(m+1\) 位的进位还会让 \(S\) 中新增 \(\mathrm{popcnt}(p)\)\(1\)

\(\texttt{Main Code}\)

// 代码中交换了 i 与 j 的定义
for(int i=0;i<=m;++i){
	for(int j=0;j<=n;++j){
		for(int k=0;k<=K;++k){
			for(int p=0;p<=n;++p){
				for(int t=0;t<=n-j;++t)
					dp[i+1][j+t][k+(t+p&1)][t+p>>1]+=
                    dp[i][j][k][p]*C[j+t][t]%mod*pv[i][t]%mod;
			}
		}
	}
}
i64 ans=0;
for(int k=0;k<=K;++k){
	for(int p=0;p<=n;++p){
		if(k+popcnt(p)<=K) (ans+=dp[m+1][n][k][p])%=mod;
	}
}

P7140 [THUPC2021 初赛] 区间矩阵乘法

不难发现 \(d\) 的值域是根号级别的。猜想正解是一种 \(\mathcal{O}(n\sqrt n)\) 的做法。

先来化简一下要求的式子

\[\begin{align} \sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1+d\cdot i+j} a_{p_2 + d\cdot j + k} &=\sum_{i=0}^{d-1}\sum_{j=0}^{d-1}a_{p_1+j+d\cdot i}\sum_{k=0}^{d-1}{a_{p_2+d\cdot j+k}}\\ &=\sum_{j=0}^{d-1}(sum_{p_2+d \cdot (j+1)-1}-sum_{p_2+d \cdot j-1})\sum_{i=0}^{d-1}{a_{p_1+j+d \cdot i}} \end{align} \]

如果使用同余前缀和(记 \(s_{i,j}\) 表示 \(\sum_{i=0}^{\lfloor \frac{j}{i} \rfloor}{a_{j-d \cdot i}}\) ),后面那个 \(\sum\) 可以用同余前缀和 \(\mathcal{O}(1)\) 求出。

暴力遍历 \(j \gets [0,d-1]\) 的复杂度是 \(\mathcal{O}(\sqrt n)\) 的,而 \(s\) 可以通过递推式

\[s_{i,j}=\left\{ \begin{array}{ll} a_j,j\leq i\\ s_{i,j-i}+a_j,j>i \end{array} \right. \]

\(\mathcal{O}(n\sqrt n)\) 预处理出。所以总时间复杂度 \(\mathcal{O}((n+m)\sqrt n)\);空间复杂度 \(\mathcal{O}(n\sqrt n)\),如果动态处理前缀和可以做到 \(\mathcal{O}(n)。\)

(最终的式子:\(\sum_{j=0}^{d-1}(sum_{p_2+d \cdot (j+1)-1}-sum_{p_2+d \cdot j-1})(s_{p_1+j+d(d-1)}-s_{p_1+j}+a_{p_1+j})\),这里的 \(sum_j\) 亦可写作 \(s_{1,j}\)

\(\texttt{Main Code}\)

void build(int n){
	int block=sqrt(n)+1;
	for(int i=1;i<=block;++i){
		for(int j=1;j<=n;++j){
			if(j<=i) s[i][j]=a[j];
			else s[i][j]=s[i][j-i]+a[j];
		}
	}
}
inline i32 query(int d,int p1,int p2){
	ans=0;
	for(int j=0;j<=d-1;++j) 
		ans+=(s[1][p2+d*(j+1)-1]-s[1][p2+d*j-1])*(s[d][p1+j+d*(d-1)]-s[d][p1+j]+a[p1+j]);
	return ans;
}	

P7145 [THUPC2021 初赛] 合法序列

看到 \(k\leq 4\) 和二进制,不难想到是一个状压 \(dp\)

由于 \(2^k \leq 16\),所以可以先枚举第 \(0\dots2^k-1\) 位的数,对于其中合法的情况,记 \(dp(i,s)\) 表示当前考虑到第 \(i\) 位,以第 \(i\) 位为末尾的末 \(k\) 位为 \(s\) 的方案数。时间复杂度 \(\mathcal{O}(2^{2^k} \times 2^k \times n)\)

\(dp(i,s)=dp(i-1,s>>1)[a_{s>>1}=1]+dp(i-1,(s>>1)|(1<<(k-1)))[a_{(s>>1)|(1<<(k-1))}=1]\)

\(\texttt{Main Code}\)

inline int calc(int x){
	int ret=0;
	for(int i=x;i<x+k;++i){
		ret<<=1;
		ret|=a[i];
	}
	return ret;
}
void solve(int x){
	for(int i=(1<<k)-1;i>=0;--i,x>>=1) a[i]=(x&1);
	for(int i=0;i<=(1<<k)-k;++i){
		int val=calc(i);
		if(a[val]==0) return;
	}
	memset(dp,0,sizeof(dp));
	dp[calc((1<<k)-k)][(1<<k)-1]=1;
	for(int i=(1<<k);i<n;++i){
		for(int s=0;s<(1<<k);++s){
			if(!a[s]) continue;
			if(a[s>>1]) dp[s][i]=dp[s>>1][i-1];
			if(a[(s>>1)|(1<<k-1)]) dp[s][i]+=dp[(s>>1)|(1<<k-1)][i-1];
			if(dp[s][i]>mod) dp[s][i]-=mod;
		}
	}
	for(int s=0;s<(1<<k);++s){
		if(!a[s]) continue;
		ans+=dp[s][n-1];
		if(ans>mod) ans-=mod;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>k;
	for(int i=0;i<(1<<(1<<k));++i) solve(i);
	cout<<ans;
}

好像有大佬用AC自动机上dp,我大受震撼


P7137 [THUPC2021 初赛] 切切糕

原文地址:http://www.cnblogs.com/chroneZ/p/16883467.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性