Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
的确变態,裸矩阵乘法不行看了讨论区才吉岛这种奇葩做法,亲测不用取1000,512-2*(101-C)就够了(就是说,C=100的时猴取512,C减小的时猴还可以相应减小),1532ms#include <iostream> #include <stdio.h> using namespace std; double mtx[2][102][102]; double mtxOrg[102][102]; int tar, C; void getPower(int N){ tar = 0; int cur = 0, next; int mc = 0; int prod = 1; while(prod <= N){ mc++; prod *= 2; } //cout << mc << endl; for(int j = mc-2; j >= 0; j--){ int jo = ((N & (1<<j)) != 0); if(jo == 0){ //cout << 0 << endl; next = (cur+1)%2; for(int p = 0; p <= C; p++){ for(int q = 0; q <= C; q++){ double temp = 0; for(int r = 0; r <= C; r++){ temp += mtx[cur][p][r] * mtx[cur][r][q]; } mtx[next][p][q] = temp; } } cur = next; tar = cur; } else{ //cout << 1 << endl; next = (cur+1)%2; for(int p = 0; p <= C; p++){ for(int q = 0; q <= C; q++){ double temp = 0; for(int r = 0; r <= C; r++){ temp += mtx[cur][p][r] * mtx[cur][r][q]; } mtx[next][p][q] = temp; } } cur = next; next = (next+1)%2; for(int p = 0; p <= C; p++){ for(int q = 0; q <= C; q++){ double temp = 0; for(int r = 0; r <= C; r++){ temp += mtx[cur][p][r] * mtxOrg[r][q]; } mtx[next][p][q] = temp; } } cur = next; tar = cur; } } } int main() { while(1){ int N, M; scanf("%d", &C); if(C == 0) break; scanf("%d%d", &N, &M); if(M > C || M < 0 || M > N || (N-M)%2 != 0) { printf("0.000\n"); continue; } if(N == 0){ if(M > 0) printf("0.000\n"); else printf("1.000\n"); continue; } int thres = 512-2*(101-C); if(N > thres){ N = thres - (N-thres)%2; } double yichuc = 1.0/C; for(int i = 0; i <= C; i++) for(int j = 0; j <= C; j++) mtx[0][i][j] = 0; for(int i = 0; i <= C; i++) for(int j = 0; j <= C; j++) mtxOrg[i][j] = 0; mtx[0][0][1] = yichuc, mtx[0][C][C-1] = yichuc; mtxOrg[0][1] = yichuc, mtxOrg[C][C-1] = yichuc; for(int i = 1; i <= C-1; i++){ mtx[0][i][i-1] = (C+1-i)*yichuc; mtx[0][i][i+1] = (i+1)*yichuc; mtxOrg[i][i-1] = mtx[0][i][i-1]; mtxOrg[i][i+1] = mtx[0][i][i+1]; } getPower(N); printf("%.3lf\n", mtx[tar][M][0]); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator