oj.uz

Submission #494412

# Submission time Handle Problem Language Result Execution time Memory
494412 2021-12-15T12:05:17 Z asandikci Anagramistica (COCI21_anagramistica) C++17
10 / 110
 6 ms 11724 KB 
#include"iostream"
#include"vector"
// #include"queue"
// #include"deque"
// #include"set"
#include"map"
#include"algorithm"
#include"cstring"
#define int long long
using namespace std;

const int modn = 1e9+7;
const int maxn = 2005;


int add(int a,int b){
  return ((a+b)%modn+modn)%modn;
}
int mult(int a,int b){
  return (a*b)%modn;
}
int binpow(int a,int b){
  int res=1;
  while(b>0){
    if(b&1){res = mult(a,res);}
    b/=2;
    a = mult(a,a);
  }
  return res;
}
int comb(int a,int b){ //C(a,b)
  int res=1;
  for(int i=0;i<b;i++){
    res=mult(res,a-i);
    res/=i+1;
  }
  return res;
}

int c[maxn][maxn];
int dp[maxn][maxn];
int arr[maxn];
map<string,int> mp;
void solve(){
  int n,k;
  cin >> n >> k;
  string str[n+5];
  int num=1;
  for(int i=0;i<n;i++){
    cin >> str[i];
    sort(str[i].begin(),str[i].end());
    if(mp[str[i]]==0){
      mp[str[i]]=num;
      arr[num]=1;
      num++;
    }
    else{
      arr[mp[str[i]]]++;
    }
  }

  // for(int i=0;i<n;i++){
  //   cout << arr[i] << " ";
  // }cout << "\n\n";

  c[0][0]=1;
  for(int i=1;i<=n;i++){
    c[i][0]=1;
    for(int j=1;j<=i;j++){
      c[i][j]+= c[i-1][j-1]+c[i-1][j];
    }
  }

  // for(int i=0;i<=n;i++){
  //   for(int j=0;j<=i;j++){
  //     cout << c[i][j] << " "; 
  //   }cout << "\n";
  // }cout << "\n\n";


  int disct = mp.size();
  int ans=0;
  

  dp[0][0]=1;
  for(int i=1;i<=disct;i++){
    for(int j=0;j<=k;j++){
      for(int g=0;g<=arr[i];g++){
        dp[i][j] += c[arr[i]][g] * dp[i-1][j-c[g][2]];
      }
    }
  }


  // for(int i=0;i<=10;i++){
  //   for(int j=0;j<=10;j++){
  //     cout << dp[i][j] << " ";
  //   }cout << "\n";
  // }  
  cout << dp[disct][k];




  // cout << ans << "*\n";

  // for(auto it : mp){
  //   cout << it.first << " " << it.second << "\n";
  // }cout << "\n";

  // for(int i=0;i<n;i++){
  //   cout << str[i] << "\n";
  // }

}

signed main(){
  ios::sync_with_stdio(false); cin.tie(0);
  // freopen("","r",stdin);freopen("","w",stdout);
  int t=1;
  // cin >>t;
  for(int i=1;i<=t;i++){
    // cout << "Case " << i << ":\n";
    solve();
  }
}

Compilation message

anagramistica.cpp: In function 'void solve()':
anagramistica.cpp:82:7: warning: unused variable 'ans' [-Wunused-variable]
   82 |   int ans=0;
      |       ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 11724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Incorrect 6 ms 11724 KB Output isn't correct
7 Halted 0 ms 0 KB -