CodeForces 1314E Strange Function

https://codeforces.com/contest/1314/problem/E

定义一个对于可重集合 \(a\) 的函数 \(f\) ,返回值为所有 \(a\) 中出现过的数字的出现次数的集合.

E.g., \(f(\{5,5,1,2,5,2,3,3,9,5\})=\{1,1,2,2,4\}\)

定义 \(f^k(a)=f^{k-1}(f(a))\) .

问对于所有长度小于等于 \(n\) 的序列 \(a\) , \(f^k(a)\) 的可能结果数.

答案对 \(998244353\) 取模

\(1 \le n,k \le 2020\)

Tutorial

当 \(k=1\) 时.

我们要统计的就是有多少序列 \(b_1,b_2,\cdots,b_m\) 满足 \(b_1 \ge b_2 \ge \cdots \ge b_m\) 且 \(\sum b_i \le n\) .

\(O(n^2)\) DP计算

当 \(k=2\) 时.

我们要判断对于 \(b_1 \ge b_2 \ge \cdots \ge b_m\) 是否存在 \(c_1 \ge c_2 \ge \cdots \ge c_l\) 满足 \(f(c)=b\) 且 \(\sum c_i \le n\) .

\(b\) 中的数就是 \(c\) 中的数的出现次数,那么我们要构造一个数组 \(v_1,v_2,\cdots,v_m\) ,其中 \(v_i\) 表示 \(v_i\) 这个数字在 \(c\) 中出现了 \(b_i\) 次.所以所有 \(v_i\) 的值两两不同,而 \(\sum c_i=\sum b_iv_i\) .

贪心构造 \(v_1=1,v_2=2,\cdots,v_m=m\) .

设 \(dp(i,j,k)\) 表示当前 \(\sum b_iv_i=i\) ,\(m=j\) , \(b_m=k\) .由于 \(j \cdot k \le n\) ,所以状态数是 \(O(n^2 \log n)\) 的.

时间复杂度 \(O(n^2 \log n)\)

当 \(k \ge 3\) 时.

注意当 \(|f^2(a)| \le \sqrt {2n}\) 其中 \(\sqrt {2n}\) 最大为 \(64\) .所以可以枚举 \(f^{k-1}(a)\) 的形态 \(b_1 \ge b_2 \ge \cdots \ge b_m\) ,一共有 \(\mathcal {P} (64)\) 种方案,大概是几百万的数量级.

对于每种 \(b\) ,用 \(k=2\) 时的构造方法展开 \(k-1\) 次,判断最后 \(a\) 数组长度是否 \(\le n\) 即可.

加上剪枝即可通过.

Code

#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline char nc()
{
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<class T> void read(T &x)
{
    x=0; int f=1,ch=nc();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=nc();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10-‘0‘+ch;ch=nc();}
    x*=f;
}
const int mod=998244353;
const int maxn=2020+5;
int k;
int n;
inline int add(int x) {return x>=mod?x-mod:x;}
namespace sub0
{
    int dp[maxn][maxn];
    int sol()
    {
        for(int i=1;i<=n;++i)
        {
            dp[i][i]=1;
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=n,sum=0;j>=1;--j)
            {
                sum=add(sum+dp[i][j]);
                if(i+j<=n)
                {
                    dp[i+j][j]=add(dp[i+j][j]+sum);
                }
            }
        }
        int an=0;
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        {
            an=add(an+dp[i][j]);
        }
        return an;
    }
}
namespace sub1
{
    vector<int> dp[maxn][maxn];
    int sol()
    {
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j)
        {
            dp[i][j].resize(n/j+1);
        }
        for(int i=1;i<=n;++i)
        {
            dp[i][1][i]=1;
        }
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=n;++j)
            {
                for(int k=n/j,sum=0;k>=1;--k)
                {
                    sum=add(sum+dp[i][j][k]);
                    int t=i+(j+1)*k;
                    if(t<=n)
                    {
                        dp[t][j+1][k]=add(dp[t][j+1][k]+sum);
                    }
                }
            }
        }
        int an=0;
        for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=n/j;k>=1;--k)
        {
            an=add(an+dp[i][j][k]);
        }
        return an;
    }
}
namespace sub2
{
    const int N=64;
    int an;
    vector<int> a;
    bool unfold(vector<int> &a)
    {
        vector<int> b;
        int m=a.size();
        int sum=0;
        for(int i=1;i<=m;++i)
        {
            sum+=i*a[i-1];
            if(sum>n) return 0;
        }
        for(int i=m;i>=1;--i)
        {
            int T=a[i-1];
            while(T--) b.push_back(i);
        }
        a=b;
        return 1;
    }
    bool check()
    {
        int T=k-1;
        vector<int> b=a;
        // debug("---\n");
        // for(int i=0;i<b.size();++i) debug("%d ",b[i]); debug("\n");
        while(T--)
        {
            if(!unfold(b)) return 0;
            // for(int i=0;i<b.size();++i) debug("%d ",b[i]); debug("\n");
        }
        return 1;
    }
    void dfs(int rest,int las)
    {
        if(check())
        {
            ++an;
            // for(int i=0;i<a.size();++i) debug("%d ",a[i]); debug("\n");
        }
        else return;
        for(int i=1;i<=las&&i<=rest;++i)
        {
            a.push_back(i);
            dfs(rest-i,i);
            a.pop_back();
        }
    }
    int sol()
    {
        // a.push_back(2),a.push_back(1);
        // debug("%d\n",check());
        for(int i=1;i<=N;++i)
        {
            a.push_back(i);
            dfs(N-i,i);
            a.pop_back();
        }
        return an;
    }
}
int main()
{
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    read(n),read(k);
    if(k==1) 
    {
        printf("%d\n",sub0::sol());
    }
    else if(k==2)
    {
        printf("%d\n",sub1::sol());
    }
    else 
    {
        printf("%d\n",sub2::sol());
    }
    return 0;
}

CodeForces 1314E Strange Function

原文：https://www.cnblogs.com/ljzalc1022/p/13040049.html