Submission #338813

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>

long long int min_nico_count = 0;

long long int count_nico( const std::string& s )
{
	long long int total_nico_count = 0;
	
	char expected_char = '2';
	long long int nico_count = 0;
	
	for ( int n = 0; n < s.size(); n++ )
	{
		if ( s[ n ] == expected_char )
		{
			if ( s[ n ] == '5' )
			{
				nico_count++;
			}
		}
		else
		{
			total_nico_count += ( nico_count * ( nico_count + 1 ) ) / 2;
			nico_count = 0;
		}
		
		if ( s[ n ] == '2' )
		{
			expected_char = '5';
		}
		else
		{
			expected_char = '2';
		}
	}
	
	total_nico_count += ( nico_count * ( nico_count + 1 ) ) / 2;
	nico_count = 0;
	
	// std::cout << s << " : " << total_nico_count << std::endl;
	
	return total_nico_count;
}

bool is_correct_password( const std::string& s )
{
	return count_nico( s ) >= min_nico_count;
}

long long int count_recursive( const std::string& s )
{
	std::string::size_type i = s.find( '?' );
	
	if ( i == std::string::npos )
	{
		return ( int ) is_correct_password( s );
	}
	
	long long int count = 0;
	
	for ( int n = 0; n < 10; n++ )
	{
		std::string s2 = s.substr( 0, i ) + static_cast< char >( '0' + n ) + s.substr( i + 1 );
		count += count_recursive( s2 );
		count %= 1000000007;
	}
	
	return count;
}

int main( int argc, char** argv )
{
	long long int length = 0;
	
	std::string s;
	
	std::cin >> length >> min_nico_count;
	std::cin >> s;
	
	std::cout << count_recursive( s ) << std::endl;
	
	/*
	long long int a = 0;
	long long int q_count = std::count( s.begin(), s.end(), '?' );
	
	for ( int n = 0; n < q_count; n++ )
	{
		a *= 10;
	}
	
	a %= 1000000007;
	*/
	
	// std::cout << q_count << " " << a << std::endl;
	
    return 0;
}

Submission Info

Judge Result