Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define FOR(i,a,b) for(long i=a;i<b;i++)
- int n;
- int main(){
- //fastio;
- cin>>n;
- string s;
- cin>>s;
- int dp[n+2][n+2];
- memset(dp,0,sizeof(dp));
- vector<int> last(256,-1);
- dp[0][0]=1;
- FOR(i,0,n+1){
- FOR(j,i+1,n+1){
- dp[i][j]=0;
- }
- }
- FOR(i,1,n+1){
- FOR(j,0,n+1){
- dp[i][j]+=dp[i-1][j];
- if(j>=1){
- dp[i][j]+=dp[i-1][j-1];
- if(last[s[i-1]]!=-1){
- dp[i][j]-=dp[last[s[i-1]]][j-1];
- }
- }
- }
- last[s[i-1]]=i-1;
- }
- FOR(i,1,n+1){
- cout<<dp[n][i]<<"\n";
- }
- return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement