kmjp's blog

競技プログラミング参加記です

yukicoder : No.315 世界のなんとか3.5

一応解けはしたけれど。
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;
}

まとめ

まーた変数名ミスって大幅タイムロスしてる…。
アホですね…。