Typical DP Contest D:サイコロ
解法
1~6の自然数をそれぞれ素因数分解すると、2と3と5だけが現れます。つまり、Dが2,3,5以外の素数を約数に含んでいたらアウトです。
Dが2,3,5の積の形で表せるときは、
dp[i][a][b][c]:i回サイコロを振って、素因数分解すると2がa回、3がb回,5がc回現れるような数になる確率
としました。
初めて解く感じの問題でした。
コード
#include<bits/stdc++.h> using namespace std; #define int long long // 2 3 5 double dp[2][100][50][50]; int N,D; signed main(){ cin>>N>>D; int c2=0,c3=0,c5=0; while(D%2==0){D/=2;c2++;} while(D%3==0){D/=3;c3++;} while(D%5==0){D/=5;c5++;} if(D!=1){ printf("%.10lf",0); return 0; } dp[0][0][0][0]=1; for(int i=0;i<N;i++){ for(int pc2=0;pc2<=c2;pc2++)for(int pc3=0;pc3<=c3;pc3++)for(int pc5=0;pc5<=c5;pc5++){ for(int j=1;j<=6;j++){ int nc2=min(c2,(j==2||j==6?pc2+1:(j==4?pc2+2:pc2))); int nc3=min(c3,(j%3==0?pc3+1:pc3)); int nc5=min(c5,(j%5==0?pc5+1:pc5)); dp[(i+1)&1][nc2][nc3][nc5]+=dp[i&1][pc2][pc3][pc5]/6.0; } dp[i&1][pc2][pc3][pc5]=0; } } printf("%.10lf\n",dp[N&1][c2][c3][c5]); return 0; }