K-hash

Time Limit: 2000ms

Memory Limit: 131072KB

This problem will be judged on 

ZJU. Original ID: 

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 1010203040506007 1312345678987654321 2112123123412345123456123456712345678123456789 173333333333333333333333333333 11

Sample Output

0 1 2 3 4 5 6 7 8 93 5 5 4 3 2 8 3 5 4 2 8 468 7757 58 59 53 49 57 60 55 51 45 59 55 53 49 56 42 5714 0 0 14 0 0 0 0 0 0 0

Source

Author

ZHOU, Yuchen

 

解题：在SAM上dp

 

1 #include 
        
          2 using namespace std; 3 const int maxn = 351000; 4 struct SAM { 5     struct node { 6         int son[26],f,len; 7         void init() { 8             f = -1; 9             len = 0;10             memset(son,-1,sizeof son);11         }12     } s[maxn<<1];13     int tot,last;14     void init() {15         tot = last = 0;16         s[tot++].init();17     }18     int newnode() {19         s[tot].init();20         return tot++;21     }22     void extend(int c){23         int np = newnode(),p = last;24         s[np].len = s[p].len + 1;25         while(p != -1 && s[p].son[c] == -1){26             s[p].son[c] = np;27             p = s[p].f;28         }29         if(p == -1) s[np].f = 0;30         else{31             int q = s[p].son[c];32             if(s[p].len + 1 == s[q].len) s[np].f = q;33             else{34                 int nq = newnode();35                 s[nq] = s[q];36                 s[nq].len = s[p].len + 1;37                 s[q].f = s[np].f = nq;38                 while(p != -1 && s[p].son[c] == q){39                     s[p].son[c] = nq;40                     p = s[p].f;41                 }42             }43         }44         last = np;45     }46 } sam;47 queue
         
          q;48 int du[maxn],dp[maxn][32],ans[maxn],k;49 char str[maxn];50 int main(){51     while(~scanf("%s%d",str,&k)) {52         memset(du,0,sizeof du);53         memset(ans,0,sizeof ans);54         sam.init();55         for(int i = 0; str[i]; ++i) sam.extend(str[i] - '0');56         for(int i = 0; i < sam.tot; ++i) {57             memset(dp[i],0,sizeof dp[i]);58             for(int j = 0; j < 10; ++j) if(sam.s[i].son[j] != -1) ++du[sam.s[i].son[j]];59         }60         //cout<
          
           <