期望可加性：对于难以整体求解的拆分。
期望的代价、次数可以抽象为实际平均。
代价有可加性，因为E(a->c)=E(a->b)+E(b->c);
高斯消元是消除环的影响和期望经过次数的相互联系。
但是复杂度过高。n^3
所以在有可加性时要先想拆分，移项化柿子。
移项化柿子一般出现在具有拓扑结构。
定义两个柿子：fx表示自己走到父节点期望步数，gx表示父节点走到自己期望步数。
通过与父节点，子节点的关系即可写出转移。注意期望的转移狮子里很可能有自己的贡献。
f[x]=1/dux+sigma(1+fson+fx)/du;
g[x]=1/dufa+(1+gfa+gx)/dufa+sigma(1+fother+gx)/dufa;
再化简，发现是整数。所以不用逆元。
维护前缀和，可以求出lca后o(1)算。（倍增非常没必要）
#include<bits/stdc++.h> #define F(i,a,b) for(rg int i=a;i<=b;++i) #define rg register #define LL long long #define il inline #define pf(a) printf("%lld ",a) #define phn puts("") using namespace std; #define int LL int read(); /* 状态设计：成环使首尾相连 为何连成环？ 单纯链式地跑，状态是无限的。 但是因为状态是首位相接的，所以可以连成环，在环上可以无限地跑 最终状态是f(0,m),而不是f(0,0).(0,m)没开始,(0,0)已开始。 处理环：1、高斯消元。但是是取模意义下的，而且复杂度太大会T 2、系数递推。相当于手动高斯了。因为to(i,j)一定比当前多，可以先处理出来，就成了常量。 而环的问题可以写出a*f0+b=fm,fm=f0+1;手动解。 可行性在于每个状态转移来的未知量只有一个。 to(i，j)函数：s+(1<<x),而不是((s>>x)+1)<<x，这会消去后面的x位1; 写时仔细想想。写完把函数逐一测一测。 */ int n,m; int p[30],q[30]; int f[420010][70]; const int mod=2000000011,inv3=1333333341; il int qpow(int x,int k){int s=1;for(;k;k>>=1,x=x*x%mod)if(k&1)s=s*x%mod;return s;} il int cal(int s,int i){ return ((s>>((i-1)<<1))&3)*1333333341%mod; } il int to(int s,int i){ return s+(1<<((i-1)<<1)); } int a[70],b[70]; il int MO(int x){return x<mod?x:x-mod;} signed main(){ // freopen("ex_card2.in","r",stdin); n=read();m=read(); p[0]=q[0]=100*n;int bas=qpow(100*n,mod-2); F(i,1,n)p[0]-=(p[i]=read()),p[i]=p[i]*bas%mod; F(i,1,n)q[0]-=(q[i]=read()),q[i]=q[i]*bas%mod; p[0]=p[0]*bas%mod;q[0]=q[0]*bas%mod; int mx=(1<<n*2)-1; for(rg int s=mx-1;~s;--s){ F(k,0,m)a[k]=p[0],b[k]=0; a[m-1]=q[0];a[m]=0; F(i,1,n){ a[m-1]=MO(a[m-1]+q[i]*cal(s,i)%mod); if(1-cal(s,i)) b[m-1]=MO(b[m-1]+q[i]*(1-cal(s,i)+mod)%mod*f[to(s,i)][m]%mod); } for(rg int k=m-2;k>=0;--k){ F(i,1,n){ a[k]=MO(a[k]+p[i]*cal(s,i)%mod); if(1-cal(s,i)) b[k]=MO(b[k]+p[i]*(1-cal(s,i)+mod)%mod*f[to(s,i)][k+1]%mod); } b[k]=MO(a[k]*b[k+1]%mod+b[k]); a[k]=a[k]*a[k+1]%mod; } f[s][m]=(b[0]+1)*qpow((1ll-a[0]+mod)%mod,mod-2)%mod; for(rg int k=m-1;k>=0;--k){ f[s][k]=MO(a[k]*f[s][m]%mod+b[k]); } } // pf(f[6]); printf("%lld ",f[0][m]); } il int read(){ int s=0;char ch; while(ch=getchar(),!isdigit(ch)); for(;isdigit(ch);s=s*10+(ch^48),ch=getchar()); return s; } /* g++ 1.cpp -g time ./a.out 1 1 27 74 2 1 84 84 54 54 1 1 27 74 */ /* int pc=q[0],s=1; F(j,1,n){ pc=(pc+q[j]*cal(i,j)%mod)%mod; s=(s+(1ll-cal(i,j)+mod)*q[j]%mod*f[to(i,j)]%mod)%mod; } f[i]=s*qpow((1ll-pc+mod)%mod,mod-2)%mod; // pf(i);pf(f[i]);phn; */