题号 NC113788
名称 Subsequences (hard version)
来源 CF1183H
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

思路:

我们令表示到了第i个位子,长度为j且不同的字符串有多少.
很显然,到了第i个位子,长度为j,第j个位子可以选,然后前面选取j-1个长度,或者第j个位子不选,前面选取j的长度.但是这样会有重复的,这时就要容斥一下了,所包含的重复状态一定是.然后第i个选长度为0的方案数都是1.这个题就解决了.
当然这个题有个值得注意的地方,就是答案在转移的时候会炸,但是你不及时退出的话,答案会偏大.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e2+5,M=30;
ll f[N][N];//到了第i个,长度为j的不同子序列的个数是多少. 
char s[N];
int last[N],cnt[M];//当前这个位子的字符上一次出现的位子.
int main()
{
    ll n,k;cin>>n>>k;
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)    last[i]=cnt[s[i]-'a'],cnt[s[i]-'a']=i,f[i][0]=1;
    ll ans=0;f[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            f[i][j]=(f[i-1][j]+f[i-1][j-1]);
            if(last[i])    f[i][j]-=f[last[i]-1][j-1];
        } 
    for(int i=n;i>=1;i--)
    {
        if(k>=f[n][i])    ans+=(n-i)*f[n][i],k-=f[n][i];
        else            
        {
            ans+=(n-i)*k,k=0;break;
        }
    }if(k==1)    ans+=n,k--;
    if(k)        puts("-1");
    else        cout<<ans<<'\n';
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目2月20日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴