sdutojMountainSubsequences

 1 #include 
 2 #include 
 3 #define maxn 100005
 4 #define mod 2012
 5 using namespace std;
 6 
 7 char str[maxn];
 8 int dp[30],dl[maxn],dr[maxn],s[maxn];
 9 int main()
10 {
11     int n;
12     while(cin>>n)
13     {
14         cin>>str;
15         for(int i=0;i)
16             s[i]=str[i]-‘a‘;
17         memset(dp,0,sizeof(dp));
18         memset(dl,0,sizeof(dl));
19         memset(dr,0,sizeof(dr));
20         for(int i=0;i)
21         {
22             for(int j=0;j)
23                 dl[i]=(dl[i]+dp[j])%mod;
24             dp[s[i]]=(dp[s[i]]+dl[i]+1)%mod;
25         }
26         memset(dp,0,sizeof(dp));
27         for(int i=n-1;i>=0;i--)
28         {
29             for(int j=0;j)
30                 dr[i]=(dr[i]+dp[j])%mod;
31             dp[s[i]]=(dp[s[i]]+dr[i]+1)%mod;
32         }
33         int ans=0;
34         for(int i=0;i)
35             ans=(ans+dl[i]*dr[i])%mod;
36         cout37     }
38     return 0;
39 }

 1 #include 
 2 #include 
 3 #include 
 4 using namespace std;
 5 const int maxn = 100000+5;
 6 int n;
 7 char s[maxn];
 8 int dl[maxn], dr[maxn], dp[26], cnt[26];
 9 const int mod = 2012;
10 int main() {
11     freopen("data.in", "r", stdin);
12     freopen("data.out", "w", stdout);
13     while(~scanf("%d", &n)) {
14         scanf("%s", s);
15         for(int i = 0; i ‘a‘;
16         memset(dp, 0, sizeof(dp));
17         memset(cnt, 0, sizeof(cnt));
18         memset(dl, 0, sizeof(dl));
19         memset(dr, 0, sizeof(dr));
20         for(int i = 0; i ) {
21             for(int j = 0; j ) {
22                 dl[i] += dp[j] + cnt[j];
23                 dl[i] %= 2012;
24             }
25             cnt[s[i]] ++;
26             cnt[s[i]] %= 2012;
27             dp[s[i]] += dl[i];
28             dp[s[i]] %= 2012;
29 
30         }
31 
32         memset(dp, 0, sizeof(dp));
33         memset(cnt, 0, sizeof(cnt));
34 
35         for(int i = n - 1; i >= 0; i-- ) {
36             for(int j = 0; j ) {
37                 dr[i] += dp[j] + cnt[j];
38                 dr[i] %= 2012;
39             }
40             cnt[s[i]] ++;
41             cnt[s[i]] %= 2012;
42             dp[s[i]] += dr[i];
43             dp[s[i]] %= 2012;
44         }
45         int ans = 0;
46         for(int i = 0; i ) {
47             ans += dl[i] * dr[i] ;
48             ans %= 2012;
49         }
50         printf("%d\n", ans);
51     }
52 }