ccbeginner

TIOJ 2052

Jan 18th, 2020
101
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //TIOJ 2052
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int C[1025][1025];
  6. int cnt[100];
  7. int d;
  8. string s;
  9. string alph = "_ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  10.  
  11. int ord(char c){
  12.     if('A' <= c && c <= 'Z')return c-'A'+1;
  13.     if('a' <= c && c <= 'z')return c-'a'+27;
  14.     return -1;
  15. }
  16.  
  17. int calc(int len){
  18.     int ret = 1, sum = 0;
  19.     for(int i = 1; i < alph.size(); ++i){
  20.         if(cnt[i] == 0)continue;
  21.         sum += cnt[i];
  22.         ret = ret * C[sum][cnt[i]] % d;
  23.         //cout << alph[i] << ' ' << ret << ' ';
  24.     }
  25.     //cout << endl;
  26.     return ret;
  27. }
  28.  
  29. void init(){
  30.     for(unsigned i = 0; i < s.size(); ++i)++cnt[ord(s[i])];
  31.     for(int i = 1; i <= s.size(); ++i){
  32.         for(int j = 0; j <= i; ++j){
  33.             if(j == 0 || j == i)C[i][j] = 1;
  34.             else C[i][j] = (C[i-1][j] + C[i-1][j-1]) % d;
  35.         }
  36.     }
  37. }
  38.  
  39. int32_t main(){
  40.     int ans = 0;
  41.     cin >> d >> s;
  42.     init();
  43.     for(unsigned i = 0; i < s.size(); ++i){
  44.         for(int c = 1; alph[c] < s[i]; ++c){
  45.             if(cnt[c] == 0)continue;
  46.             //cout << alph[c] << endl;
  47.             --cnt[c];
  48.             ans = (ans + calc(s.size()-i-1)) % d;
  49.             ++cnt[c];
  50.         }
  51.         --cnt[ord(s[i])];
  52.     }
  53.     cout << ans << endl;
  54.     return 0;
  55. }
RAW Paste Data