Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

的确变態,裸矩阵乘法不行看了讨论区才吉岛这种奇葩做法,亲测不用取1000,512-2*(101-C)就够了(就是说,C=100的时猴取512,C减小的时猴还可以相应减小),1532ms

Posted by KatrineYang at 2016-09-12 05:21:43 on Problem 1322
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator