結果
| 問題 |
No.75 回数の期待値の問題
|
| ユーザー |
 kopricky
|
| 提出日時 | 2017-07-23 17:56:48 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,600 bytes |
| コンパイル時間 | 1,490 ms |
| コンパイル使用メモリ | 166,960 KB |
| 実行使用メモリ | 6,824 KB |
| 最終ジャッジ日時 | 2024-10-09 11:01:52 |
| 合計ジャッジ時間 | 2,264 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 3 WA * 13 |
ソースコード
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl
using namespace std;
typedef pair<int,int>P;
const int MAX_N = 100005;
template<typename T> class mat : public vector<vector<T> > {
private:
int r,c; //行,列
int mat_rank;
T mat_det;
public:
int row() const {
return r;
}
int column() const {
return c;
}
mat(int n,int m,T val = 0){
mat_rank = INF,mat_det = INF;
this->r = n,this->c = m;
rep(i,n){
this->push_back(vector<T>(m,val));
}
}
mat operator+(const mat& another){
if(this->r != another.r && this->c != another.c){
cout << "足し算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] + another[i][j];
}
}
return X;
}
mat operator+(const T val){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] + val;
}
}
return X;
}
mat operator-(const mat& another){
if(this->r != another.r && this->c != another.c){
cout << "引き算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] - another[i][j];
}
}
return X;
}
mat operator-(const T val){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] - val;
}
}
return X;
}
vector<T> operator*(const vector<T>& another){
if(this->c != another.size()){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
vector<T> vec(this->r,0);
rep(i,this->r){
rep(j,this->c){
vec[i] += (*this)[i][j] * another[j];
}
}
return vec;
}
mat operator*(const mat& another){
if(this->c != another.r){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,another.c);
rep(i,this->r){
rep(k,this->c){
rep(j,another.c){
X[i][j] += (*this)[i][k]*another[k][j];
}
}
}
return X;
}
mat operator-(){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = -(*this)[i][j];
}
}
return X;
}
int rank(){
if(this->mat_rank <= min(this->r,this->c)){
return this->mat_rank;
}
int n = this->r;
T D = 1;
mat B(n,n);
rep(i,n){
rep(j,n){
B[i][j] = (*this)[i][j];
}
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
this->mat_rank = i;
this->mat_det = 0;
return i;
}
swap(B[i],B[pivot]);
D *= B[i][i];
for(int j=i+1;j<n;j++){
B[i][j] /= B[i][i];
}
for(int j=i+1;j<n;j++){
for(int k=i+1;k<n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
}
this->mat_rank = n;
this->mat_det = D;
return n;
}
T det(){
if(this->r != this->c){
cout << "正方行列でない(行列式定義不可)" << endl;
exit(1);
}
if(this->mat_rank <= this->r){
return this->mat_det;
}
int res = rank();
return this->mat_det;
}
mat inverse(){
if(this->r != this->c){
cout << "正方行列でない(逆行列定義不可)" << endl;
exit(1);
}
if(this->mat_rank < this->r){
cout << "ランク落ち(逆行列が存在しない)" << endl;
exit(1);
}
int n = this->r;
T D = 1;
mat B(n,2*n);
rep(i,n){
rep(j,n){
B[i][j] = (*this)[i][j];
}
}
rep(i,n){
B[i][n+i] = 1;
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
cout << "解なしor不定" << endl;
exit(1);
}
swap(B[i],B[pivot]);
D *= B[i][i];
for(int j=i+1;j<=2*n;j++){
B[i][j] /= B[i][i];
}
rep(j,n){
if(i != j){
for(int k=i+1;k<=2*n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
}
}
this->mat_rank = n;
this->mat_det = D;
mat res(n,n);
rep(i,n){
rep(j,n){
res[i][j] = B[i][n+j];
}
}
return res;
}
void print(){
rep(i,this->r){
rep(j,(this->c)-1){
cout << (*this)[i][j] << ",";
}
cout << (*this)[i][(this->c)-1] << endl;
}
}
};
template<typename T> vector<T> eq_solve(const mat<T>& A,const vector<T>& b){
if(A.row() != A.column()){
cout << "正方行列でない(解なしor不定)" << endl;
exit(1);
}
int n = A.row();
mat<T> B(n,n+1);
rep(i,n){
rep(j,n){
B[i][j] = A[i][j];
}
}
rep(i,n){
B[i][n] = b[i];
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
cout << "解なしor不定" << endl;
exit(1);
}
swap(B[i],B[pivot]);
for(int j=i+1;j<=n;j++){
B[i][j] /= B[i][i];
}
rep(j,n){
if(i != j){
for(int k=i+1;k<=n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
}
}
vector<T> res(n);
rep(i,n){
res[i] = B[i][n];
}
return res;
}
template<typename T> mat<T> pow(mat<T> A,ll cnt)
{
if(A.row() != A.column()){
cout << "累乗不可" << endl;
}
int n = A.row();
mat<T> B(n,n);
rep(i,n){
B[i][i] = 1;
}
while(cnt>0){
if(cnt & 1){
B = B*A;
}
A = A*A;
cnt >>= 1;
}
return B;
}
template<typename T> mat<T> mod_mul(mat<T>& A,mat<T>& B,ll mod)
{
if(A.column() != B.row()){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(A.row(),B.column());
rep(i,A.row()){
rep(k,A.column()){
rep(j,B.column()){
X[i][j] = (X[i][j] + A[i][k]*B[k][j]) % mod;
}
}
}
return X;
}
template<typename T> mat<T> pow(mat<T> A,ll cnt,ll mod)
{
if(A.row() != A.column()){
cout << "累乗不可" << endl;
}
int n = A.row();
mat<T> B(n,n);
rep(i,n){
B[i][i] = 1;
}
while(cnt>0){
if(cnt & 1){
B = mod_mul(B,A,mod);
}
A = mod_mul(A,A,mod);
cnt >>= 1;
}
return B;
}
int main()
{
int K;
cin >> K;
mat<double> ex(K+1,K+1);
rep(i,K){
ex[i][i] += 1;
for(int j=1;i+j<=K;j++){
ex[i][i+j] -= 1 / 6.0;
}
}
for(int i=max(K-5,0);i<K;i++){
ex[i][0] -= (6-K+i) / 6.0;
}
ex[K][K] += 1;
vector<double> b(K+1,1);
b[K] = 0;
vector<double> res = eq_solve(ex,b);
printf("%.10f\n",res[0]);
return 0;
}