fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF 1000000007
  5.  
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. typedef vector<int> vi;
  9. typedef vector<vector<int> > vvi;
  10. typedef pair<int,int> ii;
  11. typedef vector<pair<int,int> > vii;
  12. typedef vector<vector<pair<int,int> > > vvii;
  13.  
  14. #define all(x) x.begin(), x.end()
  15. #define tr(x,it) for(auto it = x.begin();it!=x.end();++it)
  16. #define sz(a) int((a).size()) 
  17. #define pb push_back 
  18. #define MP make_pair
  19. #define fpresent(c,x) ((c).find(x) != (c).end())  // set,map
  20. #define present(c,x) (find(all(c),x) != (c).end())  //vector
  21. #define X first
  22. #define Y second
  23. #define FOR(i,a,b) for(int i=a;i<=b;++i)
  24. #define NFOR(i,a,b) for(int i=a;i>=b;--i)
  25. ll expo(int base, int exp, int MOD=INF) {
  26.     ll res=1;
  27.     while(exp>0) {
  28.        if(exp&1) res=(res*base)%MOD;
  29.        base=((ll)base*base)%MOD;
  30.        exp=exp>>1;
  31.     }
  32.     return res;
  33. }
  34. struct node
  35. {
  36.     char c;
  37.     node *next[26];
  38.     int no;
  39.     void reset(char ch)
  40.     {
  41.         c=ch;
  42.         FOR(i,0,25)next[i]=NULL;
  43.         no=1;
  44.     }
  45. };
  46. int fac[5001];
  47. int invf[5001];
  48. int f[5001];
  49. int ans[5001];
  50. node *root;
  51. char s[5001];
  52. int main()
  53. {
  54.     ios_base::sync_with_stdio(false);cin.tie(0);
  55.     fac[0]=1;invf[0]=1;
  56.     FOR(i,1,5000)
  57.     {
  58.         fac[i]=((ll)fac[i-1]*i)%INF;
  59.         invf[i]=expo(fac[i],INF-2);
  60.     }
  61.     int T;
  62.     cin>>T;
  63.     while(T--)
  64.     {
  65.         memset(f,0,sizeof(f));
  66.         int n,q;
  67.         cin>>n>>q;
  68.         cin>>s;
  69.         root=(node *)malloc(sizeof(node));
  70.         root->reset('$');
  71.         node *curr;
  72.         FOR(i,0,n-1)
  73.         {
  74.             curr=root;
  75.             FOR(j,i,n-1)
  76.             {
  77.  
  78.                 if(curr->next[s[j]-'a']==NULL)
  79.                 {
  80.                     curr->next[s[j]-'a']=(node *)malloc(sizeof(node));
  81.                     curr=curr->next[s[j]-'a'];
  82.                     curr->reset(s[j]);
  83.                     ++f[1];
  84.                 }
  85.                 else {curr=curr->next[s[j]-'a'];--f[curr->no];(curr->no)+=1;++f[curr->no];}
  86.             }
  87.         }
  88.         ll temp=0;
  89.         memset(ans,0,sizeof(ans));
  90.         FOR(i,1,n)
  91.         {
  92.             if(f[i])
  93.             FOR(j,1,i)
  94.             {
  95.              //=((((((ll)fac[i]*(ll)invf[j])%INF)*(ll)invf[i-j])%INF)*(ll)f[i])%INF;
  96.              temp=(ll)fac[i]*invf[j];
  97.              if(temp>=INF)temp%=INF;
  98.              temp*=invf[i-j];
  99.              if(temp>=INF)temp%=INF;
  100.              temp*=f[i];
  101.              if(temp>=INF)temp%=INF;
  102.              ans[j]+=temp;
  103.              if(ans[j]>=INF)ans[j]-=INF;
  104.             }
  105.         }
  106.         int x;
  107.         while(q--)
  108.         {
  109.             cin>>x;
  110.             if(x<=n)cout<<ans[x]<<"\n";else cout<<"0\n";
  111.         }
  112.     }
  113. 	return 0;
  114. }
Success #stdin #stdout 0.01s 3316KB
comments ()
stdin
copy 
1
5 4
ababa
2
1
3
4
stdout
copy 
7
15
1
0
https://ideone.com/RKRiZX
language:
C++14 (gcc 8.3)
created:
9 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!