P4349 [CERC2015] Digit Division

Genius_Star · 2024-02-01 11:18:45 · 题解

思路：

简单题，考虑找到可以分割的点的个数 x，每一个点可以选择分割或者不分割，总方案数为 2^x。（运用快速幂）

注意到，每个区间都被 m 整除，则选几个区间合并起来也能被 m 整除，于是可以从左到右扫一遍，如果当前 1 \sim i 的数字能被 m 整除，则该点可以作为分割点。

但是如果最后一个点是分割点的话，分割或者不分割是一样的，所以不算这个答案；无解的话是整个数字都不被 m 整除的情况。

时间复杂度为 O(N + \log{p})。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=300300,mod=1e9+7; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n,m,sum,ans;
char c;
ll qpow(ll sum,ll b){
    ll ans=1;
    while(b){
        if(b&1ll)
          ans=(ans*sum)%mod;
        sum=(sum*sum)%mod;
        b>>=1ll;
    }
    return ans;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        scanf("%c",&c);
        sum=(sum*10%m+c-'0')%m;
        if(!sum)
          ans++;
    }
    write(sum?0:qpow(2ll,ans-1));
    return 0;
}