Typical DP Contest : D - サイコロ、E - 数

ここらへんはまだそこまで難しくない。
http://tdpc.contest.atcoder.jp/tasks/tdpc_dice
http://tdpc.contest.atcoder.jp/tasks/tdpc_number

D - サイコロ

サイコロをN回振った目の積がDの倍数となる確率を答える。
6以下の素数は2,3,5なので、2,3,5が何回出たか、という値を元にDPする。
D<10^18なので、各値は61回以上はカウントしなくて良い。

ll N,D;
int num[6];
double dpdp[2][70][70][70];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N>>D;
	while(D%2==0) num[2]++,D/=2;
	while(D%3==0) num[3]++,D/=3;
	while(D%5==0) num[5]++,D/=5;
	if(D>1) return _P("%lf\n",0.0);
	
	dpdp[0][0][0][0]=1.0f;
	FOR(i,N) {
		int cur=i%2;
		int tar=1^cur;
		ZERO(dpdp[tar]);
		
		FOR(x,70) FOR(y,50) FOR(z,40) {
			if(dpdp[cur][x][y][z]==0) continue;
			dpdp[tar][x][y][z]                     += dpdp[cur][x][y][z]/6.0; //1
			dpdp[tar][min(69,x+1)][y][z]           += dpdp[cur][x][y][z]/6.0; //2
			dpdp[tar][x][min(49,y+1)][z]           += dpdp[cur][x][y][z]/6.0; //3
			dpdp[tar][min(69,x+2)][y][z]           += dpdp[cur][x][y][z]/6.0; //4
			dpdp[tar][x][y][min(39,z+1)]           += dpdp[cur][x][y][z]/6.0; //5
			dpdp[tar][min(69,x+1)][min(49,y+1)][z] += dpdp[cur][x][y][z]/6.0; //6
		}
	}
	
	double ret=0;
	for(x=num[2];x<70;x++) for(y=num[3];y<50;y++) for(z=num[5];z<40;z++) ret += dpdp[N%2][x][y][z];
	_P("%.12lf\n",ret);
	
	return;
}

E - 数

N以下の自然数で、各桁の和がDの倍数になるものの個数を答えよ。
今見ている数値がa******の形とする。

先頭の値が0～(a-1)の場合、残りの桁は0～9のどれでも取れる。
M桁が0～9の任意の数値を取れるとき、その和がどうなるかは単に各桁を0～9にした場合をDPすればよい。
先頭の値がaの場合、残り桁の******について、再帰的に先頭桁の値を見ていけばよい。

注意点は、この方式だと0をDの倍数とカウントしてしまう点。全部の桁が0の場合をカウントしてしまうからね。
そこで最後に答えから1引いている。

ll D;
int L;
string N;
ll dpdp[2][100];
ll mo=1000000007;
int nd[10001][110];

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>D>>N;
	L=N.size();
	
	nd[0][0]=1;
	FOR(i,10000) {
		FOR(x,D) {
			if(nd[i][x]==0) continue;
			FOR(y,10) nd[i+1][(x+y)%D] = (nd[i+1][(x+y)%D] + nd[i][x]) % mo;
		}
	}
	
	dpdp[0][0]=1;
	FOR(i,L) {
		int cur=i%2;
		int tar=1^cur;
		ZERO(dpdp[tar]);
		x=N[L-1-i]-'0';
		FOR(y,D) {
			dpdp[tar][(x+y)%D] += dpdp[cur][y];
			dpdp[tar][(x+y)%D] %= mo;
		}
		
		FOR(x,N[L-1-i]-'0') {
			FOR(y,D) {
				dpdp[tar][(x+y)%D] += nd[i][y];
				dpdp[tar][(x+y)%D] %= mo;
			}
		}
	}
	
	// 0の分
	dpdp[L%2][0] += (mo-1);
	dpdp[L%2][0] %= mo;
	cout << dpdp[L%2][0] << endl;
	return;
}

まとめ

ここらへんまではミスもなく速度も良く調子が良かった…。