Submission #106720

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>
#include <cassert>
using namespace std;
 
//common
using i32=int;using i64=long long;using ll =i64;
#define BR "\n"
 
#define ALL(c) c.begin(),c.end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define EACH(it,list) for(auto it = list.begin(); it != list.end(); ++it)
#define IN(l,v,r) ((l)<=(v) && (v)<(r))
 
//config
#define MODE_DEBUG
//#define INF 1<<30
//#define EPS 1e-8
//const ll MOD =100000007;
 
//Mat
//template <typename T> using Mat = vector<vector<T>>;//H*W M*N
//template <typename T> using Mat3 = vector<Mat<T>>;
 
#define H(Map) Map.size()
#define W(Map) Map[0].size()
 
//debug
#ifdef MODE_DEBUG
#define  DUMP(x)  cerr << #x << " = "<< (x) <<endl
#define DEBUG(x) DUMP(x) << " (L" << __LINE__ << ")" << " " << __FILE__
#define CHECK(exp,act)  if(exp!=act){DUMP(exp);DEBUG(act);}
#define STOP(e)  CHECK(e);if(!(e)) exit(1);
#else
#define DUMP(x)
#define DEBUG(x)
#define CHECK(exp,act)
#define STOP(e)
#endif
 
 
//debug
template<class T> inline string toString(const vector<T>& x) {
	stringstream ss;
	REP(i,x.size()){
		if(i!=0)ss<<" ";
		ss<< x[i];
		//DUMP(v);
	}
	return ss.str();
}
template<class T> inline string toString(const vector<vector<T>>& map) {
	string res;stringstream ss;
	REP(i,map.size()){
		if(i!=0)ss<<BR;
		ss<< toString(map[i]);
	}
	return ss.str();
}
template<class K,class V>  string toString(map<K,V>& x) {
	string res;stringstream ss;
	for(auto& p:x)ss << p.first<<":" << p.second<<" ";
	return ss.str();
}
 
template<typename T,typename V> inline T mod(T v,V MOD){
	return v;
	//return (v%MOD+MOD)%MOD;
}

 
namespace Recursion{
	using V=double;

	const ll MOD=10000007;

	//O(m^2*log(n))
	// a[0]=ss[0],...,a[m-1]=ss[m-1]
	//a[n+m]=ms[0]*a[n]+...+ms[m-1]*a[n+m-1]+C
	// nth(n,初項,係数, 定数係数)
	V getnth(ll n,const vector<V> ss, const vector<V> ms,V C=0){
		const int K = ms.size(),M = K * 2 - 1;
		
		vector<bool> binary;
		for(int m=n;m!=0;m/=2)binary.push_back(m % 2==1);
		reverse(binary.begin(), binary.end());

		vector<V> as(M+1, 0),next(M+1, 0);
		as[0] =1;V Cs = 0;
		for(int i=0;i<(int)binary.size();i++){
			fill(ALL(next),0);
			{
				// *2
				// A_2n=ΣΣf_a*f_b*A_(a+b)=Σnext(a+b)*A_(a+b)
				// 係数
				V sum = 1,add = 0;
				for(int a=0;a<K;a++){
					for(int b=0;b<K;b++){
						next[a+b] = mod(next[a+b] + as[a] * as[b],MOD);
					}
					sum =mod(sum + as[a],MOD);
				}
				REP(i,M)as[i] = next[i];

				// M-1 ... K 
				for(int j=M-1;j>=K;j--){
					for(int k=1;k<=K;k++)as[j-k] = mod(as[j-k] + ms[K-k] * as[j] ,MOD) ;
					add = mod(add + as[j],MOD);
					as[j] = 0;
				}
				Cs = mod(Cs * sum+add, MOD);
			}
			if(binary[i]){
				DUMP(i);
				// A_(n+1)=Σf_a*A_(a+1)
				// +1
				vector<V> next(M+1, 0);
				DUMP(toString(as));
				for(int i=0;i<K;i++)next[i+1] = as[i];
				REP(i,M+1)as[i] = next[i];
			
				DUMP(toString(as));
				// K
				for(int k=1;k<=K;k++)as[K-k] = mod(as[K-k] + ms[K-k] * as[K],MOD);
				Cs = mod(Cs + as[K],MOD);

				DUMP(i);
				as[K] = 0;
			}
		}
		V res = 0;
		for(int i=0;i<K;i++)res =mod(res + as[i] * ss[i],MOD);
		res = mod(res + Cs * C ,MOD);DUMP(Cs);
		return res;
	}

}
using namespace Recursion;

int main(){

	double p,q,r;cin >> p >> q >> r;
	int N,K,M;cin >> N>> K >> M;
	vector<double> ss(N*K,0),ms(N*K,0);

	//a_i=r/(r+p+q)*a(i-NK)+p/(r+p+q)*a(i-N)+q/(r+p+q)*a_(i-1)+1/(p+q+r)
	//a_(i+NK)=r/(r+p+q)*a(i)+p/(r+p+q)*a(i+NK-N)+q/(r+p+q)*a_(i+NK-1)+1/(p+q+r)
	ms[0]+=r/(r+p+q);ms[N*K-N]+=p/(r+p+q);ms[N*K-1]+=q/(r+p+q);

	//   as[NK-1]=0;as[NK]=?
	//   as[0]=0;as[1]=?
	cout << getnth(N*M+N*K-1, ss, ms,1/(p+q+r))<<endl;
	return 0;
}

Submission Info

Judge Result