PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Author: Ashis Ghosh
Tester: Tejas Pandey
Editorialist: Daanish Mahajan
DIFFICULTY:
Easy Medium
PREREQUISITES:
Binary-Exponentiation, Solving linear equations using matrices
PROBLEM:
Given a string S of length N and an integer K, in each step we do the following:
- Initialise an empty string S'. Iterate over the characters of S in increasing order and append the string K \cdot S_i to S'.
- S = S'.
Find the length of string S modulo 1'000'000'007 after M steps.
EXPLANATION:
Hint 1
Try writing cnt_{i + 1, j} in terms of cnt_{i, j} where cnt_{i, j} represent the count of character j in S after we have done i operations.
Hint 2
Write the linear equations you got in matrix form and try finding a relationship between cnt_M and cnt_0.
Solution
Let cnt_{i, j} represent the count of character j in S after we have done i operations.
Let F_{c, j} represent the count of character j in the string c \cdot K.
So the following equations hold:
cnt_{i + 1, j} = \sum_{c = 0}^{9} cnt_{i, c} \cdot F_{c, j}, \forall j \in [0, 9]
Writing in the form of matrices:
cnt_{i + 1} = cnt_i \cdot F where \cdot represents matrix multiplication.
Here cnt matrix is of size 1 \times 10 and F matrix is of the size 10 \times 10.
Similarly,
cnt_{i + 2} = cnt_{i + 1} \cdot F = (cnt_i \cdot F) \cdot F = cnt_i \cdot (F \cdot F) = cnt_i \cdot F^2
Therefore we can also write:
cnt_M = cnt_0 \cdot F^M
Finally answer = \sum_{j = 0}^{9} cnt_{M, j}
COMPLEXITY ANALYSIS:
We calculate cnt_0 matrix in \mathcal{O}(N) and F matrix in \mathcal{O}(\sum_{c = 0}^{9} length of string(c \cdot K)) = \mathcal{O}(1).
Next we calculate F ^ M with binary exponentiation in \mathcal{O}(10^3 \cdot \log_2 M) time and multiply cnt_0 and F ^ M in \mathcal{O}(1) time.
So final complexity is \mathcal{O}((10^3 \cdot \log_2 M) + N) for a single test case.
SOLUTIONS:
Setter's Solution
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mod=1000000007;
bool test = 1;
int n,k,m;
void multiply(int a[][10],int b[][10]){
int x[10][10] = {0};
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
for(int k = 0; k < 10; ++k){
x[i][j] += (a[i][k]*b[k][j])%mod;
x[i][j] %= mod;
}
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
a[i][j] = x[i][j];
}
void power(int F[][10],int n){
int res[10][10] = {0};
for(int i = 0; i < 10; ++i)
res[i][i] = 1;
while(n){
if(n&1)
multiply(res,F);
n >>= 1;
multiply(F,F);
}
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j)
F[i][j] = res[i][j];
}
void solve(int tc = 0)
{
cin >> n >>k >> m;
assert(1<=n<=1e3);
assert(1<=k<=1e9);
assert(1<=m<=1e9);
string s;
cin >>s;
int F[10][10] = {0};
for(int i = 0; i < 10; ++i){
int p = i*k;
if(p==0){
F[0][i]++;
continue;
}
while(p){
F[p%10][i]++;
p/=10;
}
}
power(F,m);
int ans = 0;
int cnt[10] = {0};
for(int i = 0; i < n; ++i)
cnt[s[i]-'0']+=1;
for(int i = 0; i < 10; ++i)
for(int j = 0; j < 10; ++j){
ans += (cnt[j]*F[i][j])%mod;
ans %= mod;
}
cout<<ans<<"\n";
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("input.out", "w", stdout);
#endif
int t=1;
if(test)
cin>>t;
for(int i = 1; i <= t; ++i){
solve(i);
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define MOD 1000000007
#define SZ 10
using namespace std;
int add(int a, int b)
{
int res = a + b;
if(res >= MOD)
return res - MOD;
return res;
}
int mult(int a, int b)
{
long long res = a;
res *= b;
if(res >= MOD)
return res % MOD;
return res;
}
struct matrix
{
int arr[SZ][SZ];
void reset()
{
memset(arr, 0, sizeof(arr));
}
void makeiden()
{
reset();
for(int i=0;i<SZ;i++)
{
arr[i][i] = 1;
}
}
matrix operator + (const matrix &o) const
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
res.arr[i][j] = add(arr[i][j], o.arr[i][j]);
}
}
return res;
}
matrix operator * (const matrix &o) const
{
matrix res;
for(int i=0;i<SZ;i++)
{
for(int j=0;j<SZ;j++)
{
res.arr[i][j] = 0;
for(int k=0;k<SZ;k++)
{
res.arr[i][j] = add(res.arr[i][j] , mult(arr[i][k] , o.arr[k][j]));
}
}
}
return res;
}
};
matrix power(matrix a, int b)
{
matrix res;
res.makeiden();
while(b)
{
if(b & 1)
{
res = res * a;
}
a = a * a;
b >>= 1;
}
return res;
}
int main() {
int t;
cin >> t;
while(t--) {
int n, k, m;
cin >> n >> k >> m;
string s;
cin >> s;
matrix mat;
mat.reset();
mat.arr[0][0] = 1;
if(k == 0) for(int i = 0; i < 10; i++) mat.arr[0][i] = 1;
for(int i = 1; i < 10; i++) {
long long int now = (long long)i*k;
while(now) {
mat.arr[now%10][i]++;
now /= 10;
}
}
matrix expo = power(mat, m);
int ans = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < 10; j++)
ans = add(ans, expo.arr[j][s[i] - '0']);
}
cout << ans << "\n";
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int mod = 1e9 + 7;
class Matrix {
public:
int col, row, mod;
typedef vector<ll> Row;
vector<Row> data;
Matrix(int r, int c): row(r), col(c), data(r, vector<ll>(c, 0)) {}
void initialiseIdentity(){
assert(row == col);
for(int i = 0; i < row; i++){
for(int j = 0; j < row; j++){
data[i][j] = i == j;
}
}
}
void initialiseZero(){
for(int i = 0; i < row; i++){
for(int j = 0; j < row; j++){
data[i][j] = 0;
}
}
}
};
Matrix mul(Matrix const &a, Matrix const &b){
assert(a.col == b.row);
Matrix c(a.row, b.col);
for(int i = 0; i < a.row; i++){
for(int j = 0; j < b.col; j++){
for(int k = 0; k < a.col; k++){
c.data[i][j] += a.data[i][k] * b.data[k][j] % mod;
c.data[i][j] %= mod;
}
}
}
return c;
}
Matrix mat(10, 10);
Matrix rpe(int b){
Matrix ans(10, 10);
ans.initialiseIdentity();
while(b != 0){
if(b & 1)ans = mul(ans, mat);
mat = mul(mat, mat); b >>= 1;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
int n, k, m;
string s;
while(t--){
mat.initialiseZero();
cin >> n >> k >> m;
cin >> s;
Matrix cnt(10, 1);
for(char c : s){
cnt.data[c - '0'][0]++;
}
for(int i = 0; i < 10; i++){
string s1 = to_string((ll)i * k);
for(char c : s1){
mat.data[c - '0'][i]++;
mat.data[c - '0'][i] %= mod;
}
}
Matrix ans = mul(rpe(m), cnt);
ll sum = 0;
for(vector<ll> v : ans.data)for(ll x : v)sum = (sum + x) % mod;
cout << sum << endl;
}
return 0;
}