読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.372 It's automatic

問題はこちら
No.372 It's automatic - yukicoder

dp[i][j]を「i文字目までを使って作れる数の内、mod Mでjであり、先頭が0(0のみを含む)でなく、空文字列でもないものの個数」として配るDPを考える
(i+1)文字目の数をcとすると、dp[i+1]は次のように作られる
・dp[i][j]の遷移先
cを末尾に使うか使わないかで2通りがある
dp[i+1][(j*10+c)%M]+=dp[i][j]
dp[i+1][j]+=dp[i][j]
・cのみ
上では、cのみ(=空文字列の末尾にcをつけたもの)がカウントされていないのでその分として
cが0でないときは、dp[i+1][c%M]+=1
cが0のときは、dpの中にカウント出来ないのでzero+=1
とする

このとき求める答えはdp[|S|][0]+zeroとなる。

ただし、|S|*Mのサイズの配列を取ると当然MLEになる。
dp[i+1]はdp[i]のみによって決まるので2*Mをとれば十分。

char s[10000];
long dp[2][20000];
int mod=1e9+7,M,zero,i,j;
int main(){
	scanf("%s%d",s,&M);
	for(i=0;s[i];i++){
		for(j=0;j<M;j++)dp[~i&1][j]=dp[i&1][j];
		for(j=0;j<M;j++){
			dp[~i&1][(10*j+s[i]-48)%M]+=dp[i&1][j];
			dp[~i&1][j]%=mod;
			//%modと加算の順序が前後する場合があるが
			//高々mod*3にしかならないので気にしない
		}
		(s[i]-=48)?dp[~i&1][s[i]%M]++:zero++;
	}
	printf("%d",(dp[i&1][0]+zero)%mod);
	return 0;
}

縮める
内側の1つ目のfor文、はmemcpy(d[~i&1],d[i&1],2e5)とまとめられる(配列サイズを25000以上にする必要がある)
またi&1が大量に出てくるのでこれを適当な文字でおくことにして

char s['~~'];
long dp[2]['~~'];
mod=1e9+7,zero,i,j,M;
main(f){
	for(scanf("%s%d",s,&M);s[i];i++,f^=1){
		memcpy(dp[f],dp[f^1],2e5);
		for(j=0;j<M;j++)dp[f][(10*j+s[i]-48)%M]+=dp[f^1][j],dp[f][j]%=mod;
		(s[i]-=48)?dp[f][s[i]%M]++:zero++;
	}
	M=!printf("%d",(dp[f^1][0]+zero)%mod);
}

ポインタを使ってループを回せばiが要らなくなる
さらにループ圧縮をして、変数名を縮めると

char s['~~'],*p=s;
long d[2]['~~'];
m=1e9+7,z,j,M;
main(f){
	for(scanf("%s%d",s,&M);j<M?d[f][(10*j+*p-48)%M]+=d[f^1][j],d[f][j]%=m,++j:
		((*p-=48)?d[f][*p%M]++:z++,f^=1,j=!memcpy(d[f],d[f^1],2e5),*++p););
	M=!printf("%d",(**d+z)%m);
	//memcpyの順序の関係でd[0]とd[1]は常に同じ内容になっている
}

さらにsは別にchar型で無くてもよいことから、charの後ろの空白が省略できて1B短縮

long d[2]['~~'];
s[2000],m=1e9+7,z,j,M;
char*p=s;
main(f){
	for(scanf("%s%d",s,&M);j<M?d[f][(10*j+*p-48)%M]+=d[f^1][j],d[f][j]%=m,++j:
		((*p-=48)?d[f][*p%M]++:z++,f^=1,j=!memcpy(d[f],d[f^1],2e5),*++p););
	M=!printf("%d",(**d+z)%m);
	//memcpyの順序の関係でd[0]とd[1]は常に同じ内容になっている
}


ちなみにmemcpyのタイミングに気をつければ、*p-=48が早いタイミングでできることから圧縮なしでも同じ長さとなる

long d[2]['~~'];
s[2000],m=1e9+7,z,j,M;
char*p=s;
main(f){
	for(scanf("%s%d",s,&M);*p;*p?d[f][*p%M]++:z++,j=!memcpy(d[f^1],d[f],2e5),p++)
		for(*p-=48,f^=1;j<M;j++)d[f][(10*j+*p)%M]+=d[f^1][j],d[f][j]%=m;
	M=!printf("%d",(**d+z)%m);
}

223B