[NOIP 시 뮬 레이 션] 아기 코끼리 색칠 (확률 + 기대 + 전달)

수학
사실 상자 마다 k 번 을 내 놓 은 후의 색깔 이 i 일 확률 만 있 으 면 기 대 를 계산 할 수 있다.
구간 [l, r] 의 상 자 는 임의의 색깔 이 고 임의로 취하 기 때문에 확률 은 각각 1 / c 와 1 / 2 이 며 전체 확률 은 이 두 개의 곱 이다.전 확률 공식 에 따 르 면 뒤의 상태 에 대해 우 리 는 누적 하면 된다.
확률 을 구 한 후에 기 대 는 바로 색상 번호 * 확률 입 니 다...................................................
폭력 40 점.O(k*n*c^2)。。。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const double eps=1e-10;

double e[55][105][55];

int c, K, n, L[55], R[55];



int main() {

	int cs=getint();

	while(cs--) {

		read(n); read(c); read(K);

		for1(i, 1, K) read(L[i]), read(R[i]);

		for1(k, 1, K+1) rep(i, c) for1(j, 1, n) e[k][i][j]=0;

		for1(i, 1, n) e[1][1][i]=1.0;

		for1(k, 1, K) {

			rep(i, c) for1(j, 1, L[k]-1) e[k+1][i][j]=e[k][i][j];

			rep(i, c) for1(j, R[k]+1, n) e[k+1][i][j]=e[k][i][j];

			rep(b, c) rep(i, c) for1(j, L[k], R[k]) e[k+1][(i*b)%c][j]+=e[k][i][j]/2/c;

			rep(i, c) for1(j, L[k], R[k]) e[k+1][i][j]+=e[k][i][j]/2;

		}

		double ans=0;

		rep(i, c) for1(j, 1, n) ans+=i*e[K+1][i][j];

		printf("%.9f
", ans);

	}

	return 0;

}

그리고 최 적 화 를 고려한다.
우 리 는 상자 가 모두 같 고 구간 에 덮 인 횟수 에 따라 결 정 될 확률 을 발견 했다.
그래서 우 리 는 구간 커버 횟수 에 따라 확률 을 계산 해 야 한다.
한 상자 가 덮 인 횟수 가 x 라면 x 번 의 확률 로 계산한다.
이렇게 시간 복잡 도 를 O (k * c ^ 2) 로 최적화 합 니 다.

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }



const double eps=1e-10;

double e[55][105][55];

int c, K, n, L[55], R[55];



int main() {

	int cs=getint();

	while(cs--) {

		read(n); read(c); read(K);

		for1(i, 1, K) read(L[i]), read(R[i]);

		for1(k, 1, K+1) rep(i, c) for1(j, 1, n) e[k][i][j]=0;

		for1(i, 1, n) e[1][1][i]=1.0;

		for1(k, 1, K) {

			rep(i, c) for1(j, 1, L[k]-1) e[k+1][i][j]=e[k][i][j];

			rep(i, c) for1(j, R[k]+1, n) e[k+1][i][j]=e[k][i][j];

			rep(b, c) rep(i, c) for1(j, L[k], R[k]) e[k+1][(i*b)%c][j]+=e[k][i][j]/2/c;

			rep(i, c) for1(j, L[k], R[k]) e[k+1][i][j]+=e[k][i][j]/2;

		}

		double ans=0;

		rep(i, c) for1(j, 1, n) ans+=i*e[K+1][i][j];

		printf("%.9f
", ans);

	}

	return 0;

}

　　
 
 
 
 
제목 설명:
아기 코끼리 는 상자 에 색칠 하 는 것 을 좋아한다.아기 코끼리 는 현재 c 가지 색상 이 있 습 니 다. 번 호 는 0 ~ c - 1 입 니 다.그리고 n 개의 상자 가 있 습 니 다. 번 호 는 1 ~ n 이 고 처음에 상자 마다 색깔 은 1 입 니 다.아기 코끼리 는 색칠 을 할 때 영감 을 따 르 는 것 을 좋아한다. 상 자 를 번호 에 따라 한 줄 로 배열 하고 색칠 을 할 때마다 [L, R] 구간 의 일부 상자 (0 개 로 보지 않 음) 를 무 작위 로 선택 하여 무 작위 로 색 을 칠 한다.a 색 의 상자 에 b 색 을 칠 하면 이 상자 의 색 은 (a * b) mod 로 변 합 니 다. c。k 회 색칠 후 모든 상자 색상 의 번호 와 기 대 는 얼마 입 니까?
입력 설명:
첫 번 째 행동 T 는 T 조 테스트 데이터 가 있 음 을 나타 낸다.
각 그룹의 데이터 에 대해 첫 번 째 행 위 는 세 개의 정수 n, c, k 이다.
다음 k 줄 은 줄 마다 두 개의 정수 Li, Ri 로 i 번 째 작업 의 L 과 R 을 표시 합 니 다.
출력 설명:
각 그룹의 테스트 데이터 에 대해 모든 상자 의 색상 번호 와 기대 치 를 출력 한 결과 9 비트 소 수 를 유지 합 니 다.
샘플 입력:
3
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4
샘플 출력:
2.062500000
1.000000000