一応解けはしたけれど。
http://yukicoder.me/problems/766
問題
A以上B以下の整数のうち、3の倍数または3をどこかに含む整数で、かつPで割り切れないものの数を(10^9+7)で割った剰余を求めよ。
Pは8,80,800のいずれかであり、A,Bは最大200000桁である。
解法
v以下のうち題意を満たす整数の数をF(v)とすると、解はF(B)-F(A-1)である。
あとはF(v)の求め方を考えよう。
vが小さい(6桁位)の場合は愚直に全整数チェックすればよい。
以下はvが6桁以上の場合を考える。
100,000は8,80,800いずれでも割り切れるので、整数が8,80,800で割り切れるかどうかは下5桁の整数だけ見ればわかる。
よってv = xxx...xxxyyyyy (下5桁をyyyyy、残りの上の桁をxxx...xxx)と表すとする。
0~vの整数のうち、下5桁がzzzzzになるような整数は
- zzzzz≦yyyyyなものは0~(xxx...xxx)の(xxx...xxx+1)通り
- zzzzz>yyyyyなものは0~(xxx...xxx-1)の(xxx...xxx)通り
zzzzzを00000~99999まで総当たりし、うちzzzzzがPで割り切れないものについて
- zzzzzが3を含むなら上の桁の分(xxx...xxx)または(xxx...xxx+1)通りを答えにカウント
- zzzzzが3を含まないなら上の桁が0~(xxx...xxx-1)または(xxx...xxx)となるもののうち、3を含むまたは3で割り切れるものの答えをカウント。
- この際、上の桁を3で割った余りに加え、zzzzz%3も考慮して割り切れるものを数える。
上の桁について、3を含むまたは3で割り切れるものの答えをカウントするのはNo.260でとった手順の通り。
上の桁は(xxx...xxx)の場合と(xxx...xxx-1)の場合2通り、また上の桁の余りが0~2になる3通りについて、数を数え上げればよい。
kmjp.hatenablog.jp
あとはzzzzzのループは途中桁に3を含むか判定するだけなので軽い。
string A,B; ll P; ll mo=1000000007; ll p10[202020]; ll memo[202020][3][2]; ll dfs(string& S,int d,int m,int lead) { if(d>=S.size()) return (m==0); if(memo[d][m][lead]>=0) return memo[d][m][lead]; ll ret=0; int i; if(lead==1) { FOR(i,S[d]-'0') { if(i==3) ret+=p10[S.size()-1-d]; else ret += dfs(S,d+1,(m+i)%3,0); } if(S[d]=='3') { ll pat=0; for(i=d+1;i<=S.size()-1;i++) pat=(pat*10+(S[i]-'0'))%mo; ret += pat+1; } else { ret += dfs(S,d+1,(m+S[d]-'0')%3,1); } } else { FOR(i,10) { if(i==3) ret += p10[S.size()-1-d]; else ret += dfs(S,d+1,(m+i)%3,0); } } return memo[d][m][lead]=ret%mo; } string decdec(string A) { reverse(A.begin(),A.end()); FORR(r,A) { if(r--!='0') break; r='9'; } if(A.back()=='0') A.resize(A.size()-1); reverse(A.begin(),A.end()); return A; } int greed(int v,int p) { int ret=0; for(int i=1;i<=v;i++) { if(i%p==0) continue; int j=i; while(j) { if(j%10==3) break; j/=10; } if(j||(i%3==0)) ret++; } return ret; } ll hoge(string S,ll P) { ll dp[2][3]={},t[2]={}; if(S.size()<=5) return greed(atol(S.c_str()),P); ll ret=0; int low=atol(S.substr(S.size()-5).c_str()); int i,j; S=S.substr(0,S.size()-5); FOR(j,2) { MINUS(memo); FOR(i,3) dp[j][i]=dfs(S,0,i,1); FORR(r,S) t[j]=(t[j]*10+r-'0')%mo; t[j]++; S=decdec(S); } FOR(i,100000) { int v=i; if(i%P==0) continue; while(v) { if(v%10==3) break; v/=10; } if(v) ret+=t[(i>low)]; else ret += dp[(i>low)][i%3]; } return ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; p10[0]=1; FOR(i,202000) p10[i+1]=p10[i]*10%mo; cin>>A>>B>>P; A=decdec(A); cout<<((hoge(B,P)+mo-hoge(A,P))%mo)<<endl; }
まとめ
まーた変数名ミスって大幅タイムロスしてる…。
アホですね…。