fork download
copy 
  1. import java.math.*;
  2. import java.util.*;
  3.  
  4. class BigNumbers 
  5. {
  6.  public static void main(String args[])
  7.  {
  8.   Scanner sc=new Scanner(System.in); 
  9.  
  10.   int n, A;
  11.   String str;
  12.   char[] s;
  13.   int[] pi, cnt;
  14.   BigInteger[] a, b;
  15.   BigInteger ans;
  16.   int[][] classes;
  17.  
  18.   A=sc.nextInt();
  19.   str = sc.nextLine();
  20.   str = sc.nextLine();
  21.  
  22.   n=str.length();
  23.  
  24.   classes=new int[A+1][];
  25.   cnt=new int[A+1];
  26.   for(int i=1;i<=A;i++) cnt[i]=0;
  27.  
  28.   pi=new int[n];
  29.   s=new char[n];
  30.  
  31.   for(int i=0;i<n;i++)
  32.   {
  33.      s[i]=str.charAt(i);
  34.      cnt[(int)s[i]-(int)'a'+1]++;
  35.      if(i==0) pi[0]=0;
  36.      else
  37.      {
  38.         int j = pi[i-1];
  39. 		  while(j > 0 && s[i] != s[j]) j = pi[j-1];
  40. 		  if (s[i] == s[j])  j++;
  41. 		  pi[i] = j;
  42.      }
  43.   }
  44.  
  45.   for(int i=1;i<=A;i++)
  46.   {
  47.      if(cnt[i]>0) classes[i]=new int[cnt[i]];
  48.      cnt[i]=0;
  49.   }
  50.  
  51.  
  52.   for(int i=0;i<n;i++)
  53.   {
  54.      int cl=(int)s[i]-(int)'a'+1;
  55.      classes[cl][cnt[cl]]=i+1;
  56.      cnt[cl]++;
  57.   }
  58.  
  59.   a=new BigInteger[n+1];
  60.   b=new BigInteger[n+1];
  61.  
  62.   a[0]=BigInteger.ONE;
  63.   b[0]=BigInteger.ZERO;
  64.  
  65.  
  66.   for(int i=0; i<n; i++) 
  67.   {
  68.       a[i+1]=a[i].multiply(BigInteger.valueOf(A));
  69.       b[i+1]=b[i].multiply(BigInteger.valueOf(A)).subtract(BigInteger.valueOf(A));
  70.       for(int k=1;k<=A;k++)
  71.       {
  72.          char x=(char)(k-1 + 'a');
  73.          if(x==s[i]) continue;
  74.          int j=0, L, R, m;
  75.          if(classes[k]!=null)
  76.          {
  77.             L=0;
  78.             R=cnt[k]-1;
  79.             while(R-L>1)
  80.             {
  81.                m=(L+R)/2;
  82.                if(classes[k][m]<=pi[i]+1) L=m;
  83.                else R=m;
  84.             }
  85.             if(classes[k][L]<=pi[i]+1) j=classes[k][L];
  86.             if(classes[k][R]<=pi[i]+1) j=classes[k][R];
  87.          }
  88. 		   a[i+1]=a[i+1].subtract(a[j]);
  89. 		   b[i+1]=b[i+1].subtract(b[j]);
  90.       }
  91. 	}
  92.  
  93.    ans=BigInteger.valueOf(-1).multiply(b[n]).divide(a[n]);
  94.    System.out.println(ans.toString());
  95.  }
  96. }
Runtime error #stdin #stdout #stderr 0.12s 29444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.NoSuchElementException
	at java.util.Scanner.throwFor(Scanner.java:862)
	at java.util.Scanner.next(Scanner.java:1485)
	at java.util.Scanner.nextInt(Scanner.java:2117)
	at java.util.Scanner.nextInt(Scanner.java:2076)
	at BigNumbers.main(Main.java:18)
https://ideone.com/41LFtk
language:
Java (HotSpot 12)
created:
6 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!