ZOJ 3891 K-hash

K-hash

Time Limit: 2000ms

Memory Limit: 131072KB

This problem will be judged on ZJU. Original ID: 3891
64-bit integer IO format: %lld Java class name: Main

K-hash is a simple string hash function. It encodes a string Sconsist of digit characters into a K-dimensional vector (h0, h1, h2,... , hK-1). If a nonnegative number x occurs in S, then we call x is S-holded. And hi is the number of nonnegative numbers which are S-holded and congruent with i modulo K, for i from 0 to K-1.

For example, S is "22014" and K=3. There are 12 nonnegative numbers are "22014"-holded: 0, 1, 2, 4, 14, 20, 22, 201, 220, 2014, 2201 and 22014. And three of them, 0, 201 and 22014, are congruent with 0 modulo K, so h0=3. Similarly, h1=5 (1, 4, 22, 220 and 2014 are congruent with 1 modulo 3), h2=4(2, 14, 20 and 2201 are congruent with 2 modulo 3). So the 3-hash of "22014" is (3, 5, 4).

Please calculate the K-hash value of the given string S.

Input

There are multiple cases. Each case is a string S and a integer number K. (S is a string consist of '0', '1', '2', ... , '9' , 0< |S| ≤ 50000, 0< K≤ 32)

Output

For each case, print K numbers (h0, h1, h2,... , hK-1 ) in one line.

Sample Input

123456789 10

10203040506007 13

12345678987654321 2

112123123412345123456123456712345678123456789 17

3333333333333333333333333333 11

Sample Output

0 1 2 3 4 5 6 7 8 9

3 5 5 4 3 2 8 3 5 4 2 8 4

68 77

57 58 59 53 49 57 60 55 51 45 59 55 53 49 56 42 57

14 0 0 14 0 0 0 0 0 0 0

Source

ZOJ Monthly, July 2023

Author

ZHOU, Yuchen

解题：在SAM上dp

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 struct SAM {

     struct node {

         int son[],f,len;

         void init() {

             f = -;

             len = ;

             memset(son,-,sizeof son);

         }

     } s[maxn<<];

     int tot,last;

     void init() {

         tot = last = ;

         s[tot++].init();

     }

     int newnode() {

         s[tot].init();

         return tot++;

     }

     void extend(int c){

         int np = newnode(),p = last;

         s[np].len = s[p].len + ;

         while(p != - && s[p].son[c] == -){

             s[p].son[c] = np;

             p = s[p].f;

         }

         if(p == -) s[np].f = ;

         else{

             int q = s[p].son[c];

             if(s[p].len +  == s[q].len) s[np].f = q;

             else{

                 int nq = newnode();

                 s[nq] = s[q];

                 s[nq].len = s[p].len + ;

                 s[q].f = s[np].f = nq;

                 while(p != - && s[p].son[c] == q){

                     s[p].son[c] = nq;

                     p = s[p].f;

                 }

             }

         }

         last = np;

     }

 } sam;

 queue<int>q;

 int du[maxn],dp[maxn][],ans[maxn],k;

 char str[maxn];

 int main(){

     while(~scanf("%s%d",str,&k)) {

         memset(du,,sizeof du);

         memset(ans,,sizeof ans);

         sam.init();

         for(int i = ; str[i]; ++i) sam.extend(str[i] - '');

         for(int i = ; i < sam.tot; ++i) {

             memset(dp[i],,sizeof dp[i]);

             for(int j = ; j < ; ++j) if(sam.s[i].son[j] != -) ++du[sam.s[i].son[j]];

         }

         //cout<<du[0]<<endl;

         while(!q.empty());

         for(int i = ; i < sam.tot; ++i) if(!du[i]) q.push(i);

         dp[][] = ;

         while(!q.empty()) {

             int u = q.front();

             q.pop();

             for(int i = ; i < ; ++i) {

                 int v = sam.s[u].son[i];

                 if(v == -) continue;

                 if(--du[v] == ) q.push(v);

                 if(u ==  && i == ) continue;

                 for(int j = ; j < k; ++j)

                     dp[v][(j* + i)%k] += dp[u][j];

             }

             for(int i = ; i < k; ++i)

                 ans[i] += dp[u][i];

         }

         ans[]--;

         for(int i = ; str[i]; ++i)

             if(str[i] == '') {

                 ans[]++;

                 break;

             }

         for(int i = ; i < k-; ++i)

             printf("%d ",ans[i]);

         printf("%d\n",ans[k-]);

     }

     return ;

 }

巴特西