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("---
");
// for(int i=0;i<b.size();++i) debug("%d ",b[i]); debug("
");
while(T--)
{
if(!unfold(b)) return 0;
// for(int i=0;i<b.size();++i) debug("%d ",b[i]); debug("
");
}
return 1;
}
void dfs(int rest,int las)
{
if(check())
{
++an;
// for(int i=0;i<a.size();++i) debug("%d ",a[i]); debug("
");
}
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
",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
",sub0::sol());
}
else if(k==2)
{
printf("%d
",sub1::sol());
}
else
{
printf("%d
",sub2::sol());
}
return 0;
}