| ||||||||||
| 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