fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <map>
  4. #include <iterator>
  5. #include <string.h>
  6. #include <algorithm>
  7. using namespace std;
  8. typedef long long  int ll;
  9. ll mod = 1000000007;
  10. ll hmaxii=100000000;
  11. vector<ll>storage;
  12. ll arr[5000][5000];
  13. //ll answer[1000001];
  14. ll upMax=0,downMin=0;
  15. ll ans=0;
  16. ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; }
  17.  
  18. ll power(ll a,ll b){
  19.     if(b==0){
  20.         return 1;
  21.     }
  22.     ll temp = power(a,b/2);
  23.     temp = (temp*temp)%mod;
  24.     if(b%2==1){
  25.         temp = (temp*a)%mod;
  26.     }
  27.     return temp%mod;
  28. }
  29.  
  30. bool sorting(const pair<ll,ll>&a,const pair<ll,ll>&b){
  31.     if(a.first==b.first){
  32.         return (a.second>b.second);
  33.     }
  34.     else{
  35.         return (a.first<b.first);
  36.     }
  37. }
  38.  
  39. void solution(){
  40.     string ss;ll p;
  41.     ll fact[21];fact[0]=1;
  42.     map<char,int>counter;
  43.     cin>>ss;cin>>p;
  44.     for(int i=1;i<21;i++){
  45.         fact[i] = (i*fact[i-1])%mod;
  46.     }
  47.     set<char>distinct;
  48.     for(int i=0;i<ss.length();i++){
  49.         distinct.insert(ss[i]);counter[ss[i]]++;
  50.     }
  51.     ll n = distinct.size();auto it = distinct.begin();
  52.     ll arr[n+1][ss.length()+1][p];//arr[0][0][0]=1;
  53.     memset(arr,0,sizeof(arr));arr[0][0][0]=1;
  54.     for(ll i=1;i<=n;i++){
  55.         ll x = counter[*it];
  56.         for(ll len = 0;len<=x;len++){
  57.             ll add = power(fact[len],mod-2);
  58.             ll ascii = int(*it);
  59.             for(ll j=len;j<=ss.length();j++){
  60.                 for(ll k=0;k<p;k++){
  61.                     arr[i][j][(k+ascii*len)%p] = (arr[i][j][(k+ascii*len)%p] + (arr[i-1][j-len][k]*(power(fact[len],mod-2)))%mod)%mod;
  62.                 }
  63.             }
  64.         }
  65.         it++;
  66.     }
  67.  
  68.     ll ans=0;
  69.     for(ll i=1;i<=ss.length();i++){
  70.         ll mul = fact[i];
  71.         //cout<<(arr[n][i][0]*(fact[i]))%mod<<endl;
  72.         ans = (ans + (arr[n][i][0]*mul)%mod)%mod;
  73.     }
  74.     cout<<ans<<endl;
  75. }
  76.  
  77.  
  78. int main()
  79. {
  80.     ios_base::sync_with_stdio(false);
  81.     cin.tie(NULL);
  82.     //sieve();
  83.     //vector<ll>temp = getFactorization(24);
  84.     //cout<<temp.size()<<endl;
  85.     /*ll powe[64];
  86.     powe[0]=1;
  87.     ll i=1;
  88.     while(i<64){
  89.         powe[i] = powe[i-1]*2;
  90.         i++;
  91.     }*/
  92.     ll times;
  93.     //cin>>times;
  94.     times=1;
  95.     for(ll i=0;i<times;i++){
  96.         solution();
  97.     }
  98.     return 0;
  99. }
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
ab
2
stdout
copy 
1
https://ideone.com/i0REHm
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!