Advertisement
Ahmed_Negm

Untitled

Mar 29th, 2023
607
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.55 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(long i=a;i<b;i++)
  4. int n;
  5.  
  6. int main(){
  7. //fastio;
  8.  
  9. cin>>n;
  10. string s;
  11. cin>>s;
  12. int dp[n+2][n+2];
  13. memset(dp,0,sizeof(dp));
  14. vector<int> last(256,-1);
  15.  
  16. dp[0][0]=1;
  17.  
  18. FOR(i,0,n+1){
  19.     FOR(j,i+1,n+1){
  20.         dp[i][j]=0;
  21.     }
  22. }
  23.  
  24. FOR(i,1,n+1){
  25.     FOR(j,0,n+1){
  26.         dp[i][j]+=dp[i-1][j];
  27.         if(j>=1){
  28.             dp[i][j]+=dp[i-1][j-1];
  29.             if(last[s[i-1]]!=-1){
  30.                 dp[i][j]-=dp[last[s[i-1]]][j-1];
  31.             }
  32.             }
  33.  
  34.     }
  35.     last[s[i-1]]=i-1;
  36. }
  37.  
  38. FOR(i,1,n+1){
  39.     cout<<dp[n][i]<<"\n";
  40. }
  41.  
  42. return 0;}
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement