【期待+数学的導出】hdu 6747 Rotate

3264 ワード

数学

http://acm.hdu.edu.cn/showproblem.php?pid=6747
Problem Description
私たちは輪を持っていて、内から外まで全部分けられています. n つのリングで、真ん中は空いています.私たちは外から内へ i そうループへいぶんかつ a[i] 分のうち a[i] 偶数です.私たちはこれを a[i] 部の白黒は染色して、奇数番目は黒に染めて、偶数番目は白色に染めます.各層を回転させ、各層が確率的に停止位置にランダムになるのを待っています.黒いユニオンブロックの数の期待を聞く.2つの黒い領域には交点があり、連結されています.層間の回転は互いに独立している.

Input
最初の行の正の整数 test(1≤test≤10) データ・グループの数を表します.データのセットごとに、最初の行の正の整数 n(1≤n≤10). 次の行 n 個の正の整数 a[i](2≤a[i]≤1000),a[i] 偶数、別途保証 a シーケンスが下がらない.

Output
各グループのデータに対して、1行1つの数が答えを表します.答えは A/B タブで行います. AB 大きいかもしれませんが、出力してください A/Bmod 109+7、仮定 A/B 最も単純なスコアで、A/Bmod 109+7=A∗B−1 mod 109+7、B−1 満たすために B−1∗Bmod109+7=1 の双曲線コサインを返します.

【分析】
観察された性質:黒い連結ブロックが森を構成している.
証明:シーケンスaは単調に下がらないため、外から内の各輪に分けられる分割された分割された部数はますます多くなり、すなわち内へ分割されるほど細くなり、外輪の1つの黒い塊は内へ複数の黒い塊を接続することができ、内輪のブロックは外へ最大1つの黒い塊を接続することができ、1つの木の構造であり、外輪は父ノードであり、内輪は子ノードである.
森林については,結合ブロックの個数=点数−辺数,期待をとり,E(結合ブロックの個数)=E(点数)−E(辺数)
第iループを考慮すると、第iループはa[i]を共有する /2つの黒点、E(点数)への貢献はai/2、
i+1周目(内向き)の辺の辺数を計算してE(i)を望むと、E(総辺数)=E[1]+E[2]+...+E[n-1]となる
第i+1周共有(a[i+1] /2)個の黒点について、ランダム変数X[i]を設定し、i+1周目i個目の黒点とi周目のいずれかの黒点が連通(すなわち1つの辺がある)すれば、X[i]=1、なければX[i]=0、
従ってE[i]=E(X[1]+X[2]+...+X[ a[i + 1] /2 ] ),
所望の線形性により:
E[i] = E( X[1] ) + E( X[2] ) + ... + E( X[ a[i + 1] /2 ] ) )
回転対称性
E( X[1] ) = E( X[2] ) = ... = E( X[ a[i + 1] /2 ] ) )
よってE[i]=E(X[1]) * a[i + 1] /2
内輪の1つの黒いブロックと外輪の辺の期待を計算するだけで
内輪の1つの黒ブロック(図中の赤ブロック)の片側が青の挟み角内で活動し、青の挟み角が2*Pi/(1/a[i]*2)であり、辺の臨界がある場合は図中の2つの赤部分であり、占める角度範囲は2*PI*(1/a[i]+1/a[i+1])であるため、辺の確率はP(X 1)=(2*PI*(1/a[i]+1/a[i+1])/(2*Pi(1/a[i]である*2))、E(X 1)=P(X 1)*1(1辺を表す)が望ましいので、E[i]=E(X[1]) * a[i + 1] /2 = ( a[i] + a[i + 1] )/4

最後の答えは(a[1]+a[n])/4

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define f(i,l,r) for(int i=(l);i<=(r);i++)
#define ff(i,r,l) for(int i=(r);i>=(l);i--)
#define fe(i,u) for(int i=h[u];~i;i=e[i].nxt)
#define ll long long
using namespace std;
const int MAXN = 1e6 + 5;
const int MAXM = 1200010;
const int MOD = 1e9 + 7;
const int Inv2 = 500000004;
int n;
int T;
const int Inv4 = 250000002;
ll Pow(ll a, ll b, int MOD)
{
    ll res = 1;
    while(b){
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
int main()
{
//    freopen("data.in", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> T;
    while(T --){
        cin >> n;
        ll a, b;
        cin >> a;
        if(n == 1){
            cout << a / 2 << endl;
            continue;
        }
        f(i, 2, n){
            cin >> b;
        }
        ll ans = (a + b) / 2;
        cout << ans * Inv2 % MOD << endl;

    }
    return 0;
}

XMPPプロトコルに基づくAndroid IM研究二

hbase javaプログラミングインスタンス