SRM 403 500pt: TheLuckySequence

TopCoder

問題概要

数列Bが与えられる。あなたは次のような長さL(<10^9)の数列Aを作りたい。作り方が何通りあるかMOD 1234567891で求める問題。数列Aの各要素は10進で4と7のみからなる。数列Aの要素はBに含まれなくてはならない。A[i]の最後の数字(10進表記時)とA[i+1]の最初の数字は同じでなければならない。

考えたこと

  • factor 1234567891でちゃんと素数になっていることを確認。
  • これ最後の数字を覚えておくだけでよいのではないだろうか。
  • 4.*7とか4.*4とかの個数を数えておけば、ごくごく簡単な漸化式になる。
  • これは行列累乗の匂い。というか入力の制約から明らかにそう。
  • ひどいやるだけ問題だ。こんなん今のSRMに出したらブーイングしか出ないだろう。
  • ひっかけっぽい数列のユニークをちゃんとほどこした上で実装。何事もなく通った。

practiceで通ったコード

計算量だいたいO(log L)。

#include <vector>
#include <sstream>
#include <string>
#include <cassert>
#include <algorithm>
using namespace std;

typedef long long int64;

const int64 MOD = 1234567891;

typedef int64 mat_t;

struct matrix{

	vector< vector<mat_t> > val;
	int height, width;

	matrix(){}
	matrix(int height_, int width_):height(height_), width(width_){
		val.assign(height, vector<mat_t>(width, 0));
	}
};

matrix get_identity(int size){
	matrix ret(size, size);
	for(int i=0; i<size; i++){
		ret.val[i][i] = 1;
	}
	return ret;
}

matrix operator+(const matrix& lhs, const matrix& rhs){
	assert(lhs.height == rhs.height && lhs.width == rhs.width);

	matrix ret(lhs.height, lhs.width);

	for(int i=0; i<lhs.height; i++){
		for(int j=0; j<lhs.width; j++){
			ret.val[i][j] = (lhs.val[i][j] + rhs.val[i][j]) % MOD;
		}
	}

	return ret;
}

matrix operator-(const matrix& lhs, const matrix& rhs){
	assert(lhs.height == rhs.height && lhs.width == rhs.width);

	matrix ret(lhs.height, lhs.width);

	for(int i=0; i<lhs.height; i++){
		for(int j=0; j<lhs.width; j++){
			ret.val[i][j] = (lhs.val[i][j] - rhs.val[i][j] + MOD ) % MOD;
		}
	}

	return ret;
}

matrix operator*(const matrix& lhs, const matrix& rhs){
	assert(lhs.width == rhs.height);

	matrix ret(lhs.height, rhs.width);

	for(int i=0; i<lhs.height; i++){
		for(int k=0; k<lhs.width; k++){
			for(int j=0; j<rhs.width; j++){
				ret.val[i][j] = ((ret.val[i][j] + lhs.val[i][k] * rhs.val[k][j] ) % MOD + MOD) % MOD;
			}
		}
	}

	return ret;
}

matrix pow(const matrix& x, int k){

	matrix ret = get_identity(x.width), base = x;

	for(; k; k>>=1){
		if(k&1){
			ret = ret * base;
		}
		base = base * base;
	}


	return ret;
}


string to_str(int x){
	stringstream ss;
	ss << x;
	return ss.str();
}

bool is_lucky(string str){
	for(int i=0; i<(int)str.length(); i++){
		if(str[i] != '4' && str[i] != '7'){
			return false;
		}
	}
	return true;
}

struct TheLuckySequence {

	int count(vector <int> numbers, int length) {
		sort(numbers.begin(), numbers.end());
		numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());

		int a44=0, a47=0, a74=0, a77=0;

		for(int i=0; i<(int)numbers.size(); i++){
			string str = to_str(numbers[i]);
			if(is_lucky(str)){
				if(str[0] == '4' && str[(int)str.length() - 1] == '4'){
					a44++;
				}
				if(str[0] == '4' && str[(int)str.length() - 1] == '7'){
					a47++;
				}
				if(str[0] == '7' && str[(int)str.length() - 1] == '4'){
					a74++;
				}
				if(str[0] == '7' && str[(int)str.length() - 1] == '7'){
					a77++;
				}
			}
		}

		matrix mat(2, 2);
		mat.val[0][0] = a44;
		mat.val[0][1] = a74;
		mat.val[1][0] = a47;
		mat.val[1][1] = a77;

		mat = pow(mat, length - 1);

		int64 ans = 0;
		int64 x4 = a44 + a74, x7 = a47 + a77;

		ans = ((ans + x4 * mat.val[0][0] + x7 * mat.val[0][1])% MOD + MOD ) % MOD;
		ans = ((ans + x4 * mat.val[1][0] + x7 * mat.val[1][1])% MOD + MOD ) % MOD;

		return (int)ans;
	}

};