题意:Michael has a telecontrol robot. One day he put the robot on a loop with n cells. The cells are numbered from 1 to n clockwise.
At
first the robot is in cell 1. Then Michael uses a remote control to
send m commands to the robot. A command will make the robot walk some
distance. Unfortunately the direction part on the remote control is
broken, so for every command the robot will chose a direction(clockwise
or anticlockwise) randomly with equal possibility, and then walk w cells
forward.
Michael wants to know the possibility of the robot stopping in the cell that cell number >= l and <= r after m commands.
链接:点我
时间上卡的有点紧
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("***** "); 15 const int MAXN=220; 16 int n,m,tt; 17 double dp[2][MAXN]; 18 int a[MAXN]; 19 int main() 20 { 21 int i,j,k; 22 #ifndef ONLINE_JUDGE 23 freopen("1.in","r",stdin); 24 #endif 25 int x,l,r; 26 while(scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF) 27 { 28 if(n==0&&m==0&&l==0&&r==0)break; 29 dp[0][0]=1; 30 for(i=1;i<=n;i++) dp[0][i]=0; 31 int now=0; 32 while(m--) 33 { 34 scanf("%d",&x); 35 for(i=0;i<n;i++) 36 { 37 dp[now^1][i]=0; 38 } 39 for(i=0;i<n;i++) 40 { 41 if(dp[now][i]==0) continue; 42 dp[now^1][((i-x)%n+n)%n]+=0.5*dp[now][i]; 43 dp[now^1][(i+x)%n]+=0.5*dp[now][i]; 44 } 45 now^=1; 46 } 47 double ans=0; 48 for(i=l-1;i<r;i++) 49 { 50 ans+=dp[now][i]; 51 } 52 printf("%.4lf ",ans); 53 } 54 }