[Iroha 2019 Day1 K] ルーレット 题解

· · 题解

简单期望题。

考虑从 n\sim 1 倒序确定每个转盘转到了什么数：假设第 i 个转盘转到了整数 x，n\sim i+1 这些转盘中转到的整数位数之和为 k，那么这个转盘的贡献就是 10^kx。

于是在扫的过程中维护两个变量，一个是当前 10^k 的期望值（注意不能维护 k 的期望值！因为 10^k 与 k 的关系并不是线性的），还有一个是当前的答案。

精细实现似乎可以避免逆元运算的，不过为了方便实现就直接借用逆元爆算答案，之后乘上 \prod M。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int p=1e9+7;
inline int qpow(int a,int b=p-2){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%p;
    a=1ll*a*a%p,b>>=1;
  }
  return r;
}
inline void chadd(int &x,int y){
  if((x+=y)>=p)x-=p;
}
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<vector<int> > v(n);
  for(auto &i:v){
    int x; cin>>x,i.resize(x);
    for(auto &j:i)cin>>j;
  }
  reverse(v.begin(),v.end());
  int ed=1,e=0; // 前者为 10^k 期望值，后者为答案
  for(int i=0;i<n;i++){
    int c=0,iv=qpow(v[i].size());
    for(int j:v[i]){
      chadd(c,qpow(10,(int)log10l(j)+1));
      chadd(e,1ll*j*ed%p*iv%p);
    }
    ed=1ll*ed*c%p*iv%p;
  }
  for(auto i:v)e=1ll*e*i.size()%p;
  cout<<e<<endl;
  return 0;
}