Beautiful Trees Cutting

NC15695. Beautiful Trees Cutting

描述

It’s universally acknowledged that there’re innumerable trees in the campus of HUST.

One day Xiao Ming is walking on a straight road and sees many trees line up in the right side. Heights of each tree which is denoted by a non-negative integer from 0 to 9 can form a tree string. It's very surprising to find that the tree string can be represent as an initial string repeating K times. Now he wants to remove some trees to make the rest of the tree string looks beautiful. A string is beautiful if and only if the integer it represents is divisible by five. Now he wonders how many ways there are that he could make it.

Note that when we transfer the string to a integer, we ignore the leading zeros. For example, the string “00055” will be seen as 55. And also pay attention that two ways are considered different if the removed trees are different. The result can be very large, so printing the answer (mod 1000000007) is enough. And additionally, Xiao Ming can't cut down all trees.

输入描述

The first line contains a single integer K, which indicates that the tree string is the initial string repeating K times.
The second line is the initial string S.

输出描述

A single integer, the number of ways to remove trees mod 1000000007.

示例1

输入:

1
100

输出:

说明:

Initially, the sequence is ‘100’. There are
6 ways:
100
1_0
10_
_00
__0
_0_

示例2

输入:

3
125390

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 21ms, 内存消耗: 672K, 提交时间: 2022-02-11 14:05:43

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll k,ans,len;
string s;
ll pw(ll x,ll y){
	if(y==0) return 1;
	ll z=pw(x,y/2);
	return y&1?z*z%mod*x%mod:z*z%mod;
}
ll inv(ll x){
	return pw(x,mod-2);
}
int main(){
	cin>>k;
	cin>>s;
	len=s.size();
	ll q=pw(2,len);
	for(ll i=0;i<len;i++){
		if(s[i]=='0'||s[i]=='5'){
			ans+=pw(2,i)*(pw(q,k)-1)%mod*inv(q-1)%mod;
			ans=(ans%mod+mod)%mod;
		}
	}
	cout<<ans;
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 136ms, 内存消耗: 3816K, 提交时间: 2018-04-29 15:27:41

ha = 10 ** 9 + 7
def f(a1, q, n):
    if n == 1:
        return a1
    if n & 1:
        return f(a1, q, n - 1) + a1 * pow(q, n - 1, ha) % ha
    else:
        return f(a1, q, n // 2) * (pow(q, n // 2, ha) + 1) % ha

k = int(input())
s = input()
r = 0
q = f(1, pow(2, len(s), ha), k)

for i in range(len(s)):
    if s[i] == '0' or s[i] == '5':
        r += pow(2, i, ha) * q % ha
        r %= ha
print( r )