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，我大受震撼