CF1515E Phoenix and Computers

这是一道很好的 \(\mathrm{dp}\) 题。

首先我们将电脑打开方式分为两种，一种为手动，一种为自动。

那么我们先来考虑 \(n\) 台电脑全部为手动的情况。

如果先打开 \(1\) 号，那么剩余 \(n-1\) 个数中 \([2,n]\) 的顺序一定是 \(2,3,\dots,n\)，共 \(1\) 种。

如果先打开 \(2\) 号，那么剩余 \(n-1\) 个数中 \([3,n]\) 的顺序一定是 \(3,4,\dots,n\)，所以这 \(n-2\) 个数可以在 \(n-1\) 个空中随便选 \(n-2\) 个位置，然后在把 \(1\) 填入剩余的空中，共有 \(\binom{n-1}{n-2}\) 种。

如果先打开 \(3\) 号，那么剩余 \(n-1\) 个数中 \([4,n]\) 的顺序一定是 \(4,5,\dots,n\)，所以这 \(n-3\) 个数可以在 \(n-1\) 个空中随便选 \(n-3\) 个位置，然后在把 \(2,1\) 按序填入剩余的空中，共有 \(\binom{n-1}{n-3}\) 种。

所以对于一般情况，如果先打开 \(k(1\le k\le n)\) 号，那么剩余 \(n-1\) 个数中 \([k+1,n]\) 的顺序一定是 \(k+1,k+2,\dots,n\)，所以这 \(n-k\) 个数可以在 \(n-1\) 个空中随便选 \(n-k\) 个位置，然后在把 \(k,k-1,\dots,1\) 按序填入剩余的空中，共有 \(\binom{n-1}{n-k}\) 种。

所以综上所述，\(n\) 台电脑全部为手动的情况共有 \(\sum_{i=1}^{n}\binom{n-1}{n-k}=2^{n-1}\)。

接下来我们考虑最后电脑开启的状态。

很明显最终电脑的状态是一段手动，一个自动，再来一段手动，如此交替。

设 \(f_{i,j}\) 表示前 \(i\) 台电脑，手动 \(j\) 台，第 \(i\) 台手动，且第 \(i+1\) 台为自动的方案数。

那么转移时就从一段手动转移到下一段手动，即 \(f_{i,j}\to f_{i+k+1,j+k}\)。

我们先来考虑这 \(k\) 台手动内部的顺序，我们已经证明，为 \(2^{k-1}\) 种。

再来考虑原来的 \(j\) 台手动和这 \(k\) 台的手动，可以随意穿插，共有 \(\binom{j+k}{k}\) 种。

以及原有的 \(f_{i,j}\) 种，我们可以得出转移方程 \(f_{i+k+1,j+k}=\sum_{k=1}^{n-i-1}f_{i,j}\times2^{k-1}\times\binom{j+k}{k}\)。

初始化 \(f_{i,i}=2^{i-1}\)。

答案为 \(\sum_{i=1}^nf_{n,i}\)。

时间复杂度：\(O(n^3)\)。

#include<iostream>
using namespace std;
int n,mod;
long long C[405][405],pow2[405],f[405][405],ans;
int main()
{
    cin>>n>>mod;
    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;
    }
    pow2[0]=1;
    for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]*2%mod;
    for(int i=1;i<=n;i++)
    {
        f[i][i]=pow2[i-1];
        for(int j=1;j<=i;j++)
        {
            for(int k=1;k<=n-i-1;k++) f[i+k+1][j+k]=(f[i+k+1][j+k]+f[i][j]*pow2[k-1]%mod*C[j+k][k]%mod)%mod;
        }
    }
    for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod;
    cout<<ans<<endl;
    return 0;
}

CF1528B Kavi on Pairing Duty

这是一道很好的 \(\mathrm{dp}\) 题。

引理：设 \(1\) 与 \(x\) 配对，则对于每一个 \(p(x<p\le2n)\)，设它与 \(q\) 配对，则 \([p,q]\)（或 \([q,p]\)）的长度与 \([1,x]\) 的长度相同。

设 \(f_i\) 表示 \(i\) 时的种数。

对 \(x\) 进行分类讨论。

当 \(n+1\le x\le2n\) 时，根据引理可得 \(1\) 与 \(x\) 配对，\(2\) 与 \(x+1\) 配对，\(3\) 与 \(x+2\) 配对，直至 \(2n-x+1\)与\(2n\) 配对。因为 \(n+1\le x\le2n\)，所以 \(1\le2n-x+1\le x\)，可以想象到连完之后中间会空下连续的一段，共 \(2x-2n-2\) 个点，个数为 \(f_{x-n-1}\)。所以当 \(n+1\le x\le2n\) 时，个数共有 \(\sum_{i=0}^{n-1}f_i\) 种。

当 \(2\le x\le n\) 时，易得 \(x-1\) 为 \(n\) 的约数且不等于 \(n\)，设 \(D(n)\) 表示 \(n\) 除自己外的约数个数，则当 \(2\le x\le n\) 时，个数共有 \(D(n)\) 种。

综上，\(f_n=\sum_{i=0}^{n-1}f_i+D(n)\)。

初始化 \(f_0=1\)。

时间复杂度：\(O(n\log n)\)。

#include<iostream>
using namespace std;
long long mod=998244353;
long long n;
long long dp[1000005];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=2;i*j<=n;j++) dp[i*j]++;
    }
    dp[0]=1;
    long long sum=1;
    for(int i=1;i<=n;i++)
    {
        dp[i]=(dp[i]+sum)%mod;
        sum=(sum+dp[i])%mod;
    }
    cout<<dp[n]<<endl;
    return 0;
}

CF1510D Digits

这是一道很好的 \(\mathrm{dp}\) 题。

状态很容易想出，设 \(f_{i,j}\) 表示前 \(i\) 位乘积 \(\%10\) 后为 \(j\)，且乘积最大的值。

但是转移时会发现乘积太大，无法直接转移。

因此我们可以运用对数化乘为加，即 \(x\times y=2^{\log_2x}\times2^{\log_2y}=2^{\log_2x+\log_2y}\)。

所以我们只需记录乘积的 \(\log\) 值即可。

转移方程：\(f_{i,k}=max(f_{i-1,k},f_{i-1,j}+\log_2a_i)\)。

至于方案，我们在更新答案的同时用一个 \(pre\) 数组来记录，即 \(pre_{i,k}=j\)。

初始化 \(f_{0,i}=-\inf\)，\(f_{0,1}=0\)。

时间复杂度：\(O(10n)\)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,k,cnt;
long long a[100005],pre[100005][15],ans[100005];
double f[100005][15];
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<=9;i++) f[0][i]=-1e9;
    f[0][1]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=9;j++) f[i][j]=f[i-1][j];
        for(int j=0;j<=9;j++)
        {
            int k=j*a[i]%10;
            if(a[i]==1||f[i][k]<f[i-1][j]+(double)log2(a[i]))
            {
                f[i][k]=f[i-1][j]+(double)log2(a[i]);
                pre[i][k]=j;
            }
        }
    }
    if(f[n][k]<0) cout<<-1<<endl;
    else
    {
        for(int i=n;i>=1;i--)
        {
            if(pre[i][k]!=-1)
            {
                ans[++cnt]=a[i];
                k=pre[i][k];
            }
        }
        if(cnt==0) cout<<-1<<endl;
        else
        {
            cout<<cnt<<endl;
            for(int i=1;i<=cnt;i++) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

CF1027E Inverse Coloring

这是一道很好的 \(\mathrm{dp}\) 题。

引理：当一个正方形的第一行与第一列确定之后，这个正方形的漂亮着色就已经确定了。

证明：易得。

因此问题就转变为了要求行与列的最大连续同色长度的乘积 \(<k\)。

行与列相同，所以可以只算一边。

设 \(f_{i,j}\) 表示在前 \(i\) 个中，最大连续黑色长度 \(\le j\) 的个数。

不难得出转移方程：\(f_{i,j}=\sum_{k=i-j}^{i-1}f_{k,min(j,k)}\)。

初始化：\(f_{i,i}=1\)

再利用差分，设 \(sum_i\) 表示长度为 \(n\)，且最大连续黑色长度 \(=i\) 的个数。

则 \(ans=\sum_{i=1}^n\sum_{j=1}^nsum_i\times sum_j\ [i\times j<k]\)。

最后因为有黑白两色，不要忘了 \(ans\times 2\)。

时间复杂度：\(O(n^3)\)。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
const int mod=998244353;
long long f[505][505],sum[505],ans;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i][i]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            for(int k=i-j;k<=i-1;k++) f[i][j]=(f[i][j]+f[k][min(j,k)])%mod;
        }
    }
    for(int i=1;i<=n;i++) sum[i]=(f[n][i]-f[n][i-1]+mod)%mod;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i*j<m) ans=(ans+sum[i]*sum[j]%mod)%mod;
        }
    }
    cout<<ans*2%mod<<endl;
    return 0;
}