题意：给定一个字符串S，长度为n≤100，然后定义一个操作是将S的一个含有L个字符的子序列看作一个字符串插入到一个无重复元素的set里，每次操作的cost是(n-L)，然后问对于给定的k（k最大可取1e12），最少需要多少总cost才能使得set的元素个数达到k。难度2200分，有点虚高其实，不过还是不那么好想的。用先后顺序去重是关键idea。
做这种代码段但是考思维的小题还是挺有意思的。。。。
这题是mike出的，感觉挺经典那种。他有一个easy version是k≤100，这个要求的话就很松了，mike的题解直接用了一种及其暴力的方法：把每个subsequence当作一个点，相差一个字符的点之间连边建图，直接暴力跑bfs。。。这个肯定是个时间和空间复杂度都爆炸的算法，但是k≤100的时候很快就能搜到，只要及时跳出bfs就可以了。
这个H版本要求k最大可能是1e12，这就不能再那么操作了。首先写几个简单的样例就可以发现这个主要跟unique的子序列的长度和数量有关系，如果我们能求出来对应于某一长度j的unique子序列有多少个，那就可以解决这个问题了。这个就是一个引导方向，可以先试着设dp[i][j]表示以i为结尾的长度为j的子序列个数。状态定义好了之后考虑转移，按照大问题转化为小问题的思想，dp[i][j]表示的以i结尾的unique子序列，那么如果去掉s[i]之后这些子序列一定是互不相同的长度为j-1的子序列，数量没有多也没有少。所以现在就是要考虑怎么算出来前i-1个字符构成的子序列里面有多少个了。利用已经计算得得信息，这个一定是某些dp[pos][j-1]之和，但是有一种情况的是不同的pos对应的子串可能一样，所以这个题目最精彩的部分就来了，每次在相同的字符中选取最靠后的作为计算点。第一这样起码不会比选择前面的点坏，如果前面的点能凑成q个子序列那么后面的点凑成的相同长度的子序列只会多不会少，即不漏；第二这个就避免了重复计算的现象，不重不漏即为正确的dp转移。所以如果用\[lst[i][w]\]表示前i个字符里面字符为\[‘a’+w (w \in [0,25])\],可以写出来状态转移方程为
\[dp[i][j]=\sum_{w=0}^{25} dp[lst[i-1][w]][j-1]\]至于lst显然很简单的一个dp就推出来了lst[i][j]=((int)(s[i]-‘a’)==j)?i:lst[i-1][j];
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e2+5;
const ll ub=(ll)100000000000000;
ll lst[maxn][35];
ll dp[maxn][maxn];
char s[maxn];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;ll k;//error1
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++)
for(int j=0;j<26;j++)
lst[i][j]=((int)(s[i]-'a')==j)?i:lst[i-1][j];
for(int i=1;i<=n;i++){
dp[i][1]=1;
for(int j=2;j<=i;j++){
for(int w=0;w<26;w++){
dp[i][j]+=dp[lst[i-1][w]][j-1];
dp[i][j]=min(dp[i][j],ub);
}
}
}
ll ans=0,cnt;
for(int j=n;j>=1;j--){
cnt=0;
for(int w=0;w<26;w++)
cnt+=dp[lst[n][w]][j];
if(k>cnt) k-=cnt,ans+=cnt*(n-j);
else{
cout<<ans+k*(n-j);
return 0;
}
}
if(k==1)
cout<<ans+n;
else
cout<<-1;
return 0;
}