アルファベット小文字からなる文字列 $S$ が与えられる.
最初,文字列 $T$ を空として,$S$ の文字数が正であるかぎり以下の処理を行う.
処理: $S$ の先頭,または,最後の文字を取り除き,取り除いた文字を $T$ の末尾に加える.
最終的に,文字列 $T$ としてあり得る文字列は何通りあるかを求める問題.
左右どちらから取るかを文字数の回数分だけ選べば,$T$ は確定する.
これは $2^{|S|}$ パターンしか無いので,全部試せば良い.
後は,$T$ をソートするなり,$\verb|set|$ に突っ込むなりして,異なるものを数えれば良い.
時間計算量は,工夫すれば $O(2^{|S|})$ 程度,愚直にやっても $O(|S|^2 2^{|S|})$ 程度.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
int main(){
int i, j, k, N;
int a,b;
char in[100];
set<string> s;
N = reader(in);
rep(i,1<<N){
string str;
a = 0; b = N-1;
rep(j,N){
if(i&1<<j) str += in[a++];
else str += in[b--];
}
s.insert(str);
}
writer((int)s.size(),'\n');
return 0;
}
Current time: 2024年04月26日02時56分20秒
Last modified: 2014年12月05日01時34分27秒 (by laycrs)
Tags: Competitive_Programming yukicoder
トップページに戻る
Logged in as: unknown user (not login)