TopCoder SRM 772 : Div2 Hard AntiprimeNumbers

Div1Easyと全然関係ない問題が出るの結構久々な気がする。
https://community.topcoder.com/stat?c=problem_statement&pm=15782

問題

最大200000桁の整数Nが与えられる。
各桁1～Dで構成されるN桁の整数のうち、(不連続も含む)部分列として素数が登場しないものは何通りか。
mod (10^9+7)で求めよ。

解法

まず1桁で素数になる2,3,5,7は使えない。
そうすると使える候補は1,4,6,8である。
うち4,6,8だけで構成される整数は必ず合成数になる。
1に関しては、

• 1の前に1,4,6が来ると11,41,61が素数になるので不可。
• 881は素数なので不可。

となる。

よってあり得るのは

• 4,6,8だけで作られたN桁の整数
• 先頭が1で、以後4,6,8だけで作られたN桁の整数
• 先頭が81で、以後4,6,8だけで作られたN桁の整数

だけ。Dが8より小さい場合、さらに小さくなる。

D=8の時、例えば先頭のケースでは3^N % (10^9+7)を求めることになるが、N自体が大きいのでバイナリ法を用いても間に合わない。
0以外の整数でk^(10^9+6) mod (10^9+7) = 1なので、3^(N % (10^9+6)) % (10^9+7)を求めればよい。

ll mo=1000000007;

string decdec(string A) {
	for(int i=A.size()-1;i>=0;i--) {
		if(A[i]--!='0') break;
		A[i]='9';
	}
	A=A.substr(A[0]=='0');
	if(A.empty()) A="0";
	return A;
}

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}


class AntiprimeNumbers {
	public:
	ll po(string N,int D) {
		ll p=0;
		FORR(c,N) {
			p=(p*10+(c-'0'))%(mo-1);
		}
		return modpow(D,p);
	}
	
	int countAntiPrimes(string N, int D) {
		
		if(D>=8) D=3;
		else if(D>=6) D=2;
		else if(D>=4) D=1;
		else D=0;
		
		if(D==0) {
			if(N=="1") return 1;
			else return 0;
		}
		
		if(N=="1") {
			return D+1;
		}
		
		ll ret=po(N,D);
		N=decdec(N);
		ret+=po(N,D);
		if(D==3) {
			N=decdec(N);
			ret+=po(N,D);
		}
		
		return ret%mo;
		
	}
}

まとめ

Div1EasyとDiv2Hardは逆でもよかったかも。