Codeforces ECR #068 : G. Another Meme Problem

シンプルながら面倒な問題。
https://codeforces.com/contest/1194/problem/G

問題

ある分数x/yがgoodであるとは、約分すると1桁分の1桁になるケースとする。
x,yが1以上N以下の場合、goodな(x,y)の組を求めよ。

解法

x/y=1の時はx,yの値はN通り考えられるし、x/y＞1の時はx/y＜1の時と同数考えられる。
よって以下x/y＜1のケースを考える。
約分してx/y=p/qになるケースを、既約なp/qに対し総当たりしよう。

下の桁から順に、x,yにおけるキャリー、mod p,mod qの値と、あとyがN以下確定かどうか、を状態として持ちながらDPしていく。

string S;
int N;
ll mo=998244353;
int X,Y,ma;

ll dp[102][2][10][10][16][16];

ll hoge(int d,int mor,int c1,int c2,int m1,int m2) {
	if(d==N) {
		
		if(mor==0 && c1==0 && c2==0 && (m1&m2)) return 1;
		return 0;
	}
	ll& ret=dp[d][mor][c1][c2][m1][m2];
	if(ret>=0) return ret;
	ret=0;
	
	int a;
	FOR(a,10) {
		int p=a*X+c1;
		int q=a*Y+c2;
		
		int mo2=mor;
		if(q%10>S[d]) mo2=1;
		if(q%10<S[d]) mo2=0;
		
		int nm1=m1;
		int nm2=m2;
		if(p%10>0 && p%10%X==0 && p%10/X<=ma) nm1 |= 1<<(p%10/X-1);
		if(q%10>0 && q%10%Y==0 && q%10/Y<=ma) nm2 |= 1<<(q%10/Y-1);
		ret+=hoge(d+1,mo2,p/10,q/10,nm1,nm2)%mo;
	}
	ret%=mo;
	return ret;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	ll ret=0;
	// add 1/1
	FORR(c,S) {
		c-='0';
		ret=(ret*10+c)%mo;
	}
	reverse(ALL(S));
	
	
	for(X=1;X<=9;X++) {
		for(Y=X+1;Y<=9;Y++) {
			ma=9/Y;
			if(__gcd(X,Y)==1) {
				MINUS(dp);
				ret+=2*hoge(0,0,0,0,0,0);
			}
		}
	}
	cout<<ret%mo<<endl;
	
}

まとめ

言われてみると素直な解法なんだけど、割と面倒だね。