fork(4) download
copy 
  1. import java.awt.Point;
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. import javax.print.attribute.standard.Compression;
  6.  
  7.  
  8.  
  9.  
  10.   class TestClass {
  11. 	  static long mod;
  12. 	  static Batman Root;
  13.  static class Batman{
  14.  
  15. 	    int value;
  16. 	    Batman[] next = new Batman[26];
  17.  
  18. 	    public Batman(int value){
  19. 	    	this.value = value;
  20. 	    	}
  21.  
  22.  
  23.  
  24.  }
  25.  
  26.  public static void  Insert(String S,int[] F , int start){
  27.  
  28.  
  29.  
  30.  
  31. 	 Batman temp = Root;
  32. 	 for(int i=start;i<S.length();i++){
  33. 		 int index = S.charAt(i)-'a';
  34.  
  35. 		 if(temp.next[index]==null){
  36. 			 temp.next[index] = new Batman(1);
  37. 			 F[1]+=1;
  38.  
  39. 		 }else{
  40. 			 temp.next[index].value+=1;
  41. 			 int xx = temp.next[index].value;
  42. 			 F[xx-1]-=1;
  43. 			 F[xx]+=1;
  44.  
  45. 			// System.out.println(xx+" "+temp.next[index].value);
  46. 		 }
  47. 		 temp = temp.next[index];
  48. 	 }
  49.  
  50.  }
  51.  
  52.  
  53. public static void main(String args[] ) throws  java.lang.Exception  {
  54.  
  55.  
  56.  
  57. 	InputStream inputStream = System.in;
  58.    InputReader in = new InputReader(inputStream);
  59.  
  60.  // BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  61. //  BufferedReader in = new BufferedReader(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  62.    //Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  63.   // PrintWriter pw = new PrintWriter(new FileWriter("C:\\Users\\Sompathak\\Desktop\\output.txt"));
  64.     //InputStream inputStream = System.in;
  65.     //InputReader in = new InputReader(inputStream);
  66.  // Scanner in = new Scanner(new InputStreamReader(System.in));
  67. //Scanner in = new Scanner(new FileReader("C:\\Users\\Sompathak\\Desktop\\yes.txt"));
  68.     //we can we will ??? !!!!!! SOM     RISES
  69. int t = in.nextInt();
  70. mod = 1000000007;
  71. long[][] C =  new long[5001][5001];
  72.  
  73. while(t>0){
  74. 	t--;
  75. 	Root = new Batman(0);
  76. int n = in.nextInt();
  77. int Q = in.nextInt();
  78. String S = in.next();
  79. int[] F = new int[n+1];
  80. for(int i=0;i<=n;i++)
  81. 	for(int j=0;j<=Math.min(i,n);j++){
  82. 		if(j==0|| j==i)
  83. 		{
  84. 			C[i][j]=1;
  85. 			continue;
  86.  
  87. 		}
  88.  
  89. 		C[i][j] = C[i-1][j-1] + C[i-1][j];
  90. 		C[i][j]%=mod;
  91. 	}
  92. for(int i=0;i<n;i++)
  93. 	Insert(S,F,i);
  94.  
  95.  
  96. long[] ans = new long[n+1];
  97.  
  98.  
  99. for(int i=1;i<=n;i++){
  100. 	for(int j=i;j<=n;j++){
  101. 		ans[i]+= F[j]*C[j][i];
  102. 		ans[i]%=mod;
  103. 	}
  104. }
  105.  
  106.  
  107.  while(Q>0){
  108. 	 Q--;
  109. 	int cc = in.nextInt();
  110. 	long o =0;
  111. 	if(cc<=n) o=ans[cc];
  112. 	 System.out.println(o);
  113.  }
  114. }
  115.  
  116.  
  117.  
  118.  
  119. }public static class InputReader
  120. {
  121.     private InputStream stream;
  122.     private byte[] buf = new byte[1024];
  123.     private int curChar;
  124.     private int numChars;
  125.     private SpaceCharFilter filter;
  126.  
  127.     public InputReader(InputStream stream)
  128.     {
  129.         this.stream = stream;
  130.     }
  131.  
  132.     public int read()
  133.     {
  134.         if (numChars == -1)
  135.             throw new InputMismatchException();
  136.         if (curChar >= numChars)
  137.         {
  138.             curChar = 0;
  139.             try
  140.             {
  141.                 numChars = stream.read(buf);
  142.             } catch (IOException e)
  143.             {
  144.                 throw new InputMismatchException();
  145.             }
  146.             if (numChars <= 0)
  147.                 return -1;
  148.         }
  149.         return buf[curChar++];
  150.     }
  151.  
  152.     public int nextInt()
  153.     {
  154.         int c = read();
  155.         while (isSpaceChar(c))
  156.             c = read();
  157.         int sgn = 1;
  158.         if (c == '-')
  159.         {
  160.             sgn = -1;
  161.             c = read();
  162.         }
  163.         int res = 0;
  164.         do
  165.         {
  166.             if (c < '0' || c > '9')
  167.                 throw new InputMismatchException();
  168.             res *= 10;
  169.             res += c - '0';
  170.             c = read();
  171.         } while (!isSpaceChar(c));
  172.         return res * sgn;
  173.     }
  174.  
  175.     public String readString()
  176.     {
  177.         int c = read();
  178.         while (isSpaceChar(c))
  179.             c = read();
  180.         StringBuilder res = new StringBuilder();
  181.         do
  182.         {
  183.             res.appendCodePoint(c);
  184.             c = read();
  185.         } while (!isSpaceChar(c));
  186.         return res.toString();
  187.     }
  188.     public double readDouble() {
  189.         int c = read();
  190.         while (isSpaceChar(c))
  191.             c = read();
  192.         int sgn = 1;
  193.         if (c == '-') {
  194.             sgn = -1;
  195.             c = read();
  196.         }
  197.         double res = 0;
  198.         while (!isSpaceChar(c) && c != '.') {
  199.             if (c == 'e' || c == 'E')
  200.                 return res * Math.pow(10, nextInt());
  201.             if (c < '0' || c > '9')
  202.                 throw new InputMismatchException();
  203.             res *= 10;
  204.             res += c - '0';
  205.             c = read();
  206.         }
  207.         if (c == '.') {
  208.             c = read();
  209.             double m = 1;
  210.             while (!isSpaceChar(c)) {
  211.                 if (c == 'e' || c == 'E')
  212.                     return res * Math.pow(10, nextInt());
  213.                 if (c < '0' || c > '9')
  214.                     throw new InputMismatchException();
  215.                 m /= 10;
  216.                 res += (c - '0') * m;
  217.                 c = read();
  218.             }
  219.         }
  220.         return res * sgn;
  221.     }
  222.     public long readLong() {
  223.         int c = read();
  224.         while (isSpaceChar(c))
  225.             c = read();
  226.         int sgn = 1;
  227.         if (c == '-') {
  228.             sgn = -1;
  229.             c = read();
  230.         }
  231.         long res = 0;
  232.         do {
  233.             if (c < '0' || c > '9')
  234.                 throw new InputMismatchException();
  235.             res *= 10;
  236.             res += c - '0';
  237.             c = read();
  238.         } while (!isSpaceChar(c));
  239.         return res * sgn;
  240.     }
  241.     public boolean isSpaceChar(int c)
  242.     {
  243.         if (filter != null)
  244.             return filter.isSpaceChar(c);
  245.         return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  246.     }
  247.  
  248.     public String next()
  249.     {
  250.         return readString();
  251.     }
  252.  
  253.     public interface SpaceCharFilter
  254.     {
  255.         public boolean isSpaceChar(int ch);
  256.     }
  257. }
  258.  }
Success #stdin #stdout 0.45s 380160KB
comments ()
stdin
copy 
1
5 4
ababa
2
1
3
4
stdout
copy 
7
15
1
0
https://ideone.com/zUiTLL
language:
Java (12.0.1)
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!