网易笔试第三题

给一个数字字符串S,一个数字m, 你需要计算出S有多少个划分,讲他划分为S1,S2,S3,。。 且每个数都是m的倍数,答案对1e9+7取模 例如 123456 2 可以划分为 123456 1234|56 12|3456 12|34|56

最近发现这题不对劲,有新想法,先上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
string s;
int m;
cin>>s>>m;
const int mod = 1e9+7;
int cnt=0;
int cur=0;
for(char ch:s){
cur = (cur*10ll+ch-'0')%m;
if(cur==0) cnt++;
}
int ans=0;
if(cur=0) ans=0;
else ans=1;
for(int i=1;i<cnt;i++) ans=(ans*2)%mod;
cout<<ans<<endl;

  • 约定S下标从1开始到n结束,即S=S[1,n]
  • 定义一个大数S的子串为S[l,r] 代表从l开始,到r结束,包含l和r,
  • 定义一个大数S的划分序列为数组\[\{k_1,k_2,...k_i\}\], 表示S被划分为了\(S[k_1,k_2-1],S[k_2,k_3-1]...\) ,显然这里有\[1=k_1\lt k_2\lt k_3...\]
  • 我们不难贪心,每次都找靠左最短的序列,即在\[S[1,n]\]中找最短前缀\[S[1,k_2-1]\],然后再到\[S[k_1,n]\]中找第二个前缀,于是我们找到了cnt个
  • 于是我们可以在序列\[\{k_1,k_2,...k_i\}\]中任意取一个子序列,他们都是合法的划分,
  • 假设某个划分序列\[\{t_1,t_2,...t_j\}\]不是\[\{k_1,k_2,...k_i\}\]的子序列,我们先在t中找到一个最小的\[t_u\], 他没有出现在k中,我们考虑他左边的是\[t_{u-1}\],我们在k中找到最大的小于\[t_u\]的数\[k_v\]
  • 现在\[t_{u-1}\lt k_v\lt t_u\lt k_{v+1}\]
  • 现在我们来推翻这个假设,t说\[S[t_{u-1},t_u-1]\%m=0\],k说\[S[t_{u-1},k_v-1]\%m=0\], 那么我们可以推出\[S[k_v,t_u-1]\%m=0\],这个结论显然不成立,因为\[k_{v+1}\ne t_u\]