题目描述

There is a train with n rows, and there are m seats per row. All seats are occupied. For some passengers, we know they are being infected with COVID-19 or not. However, for other passengers, we are not sure about their status, and we assume each of them has 1/2 chance being infected with COVID-19, independent from each other.
All infected passengers need to be quarantined for d0 days. All passengers that are not infected,but edge-adjacent to any infected passenger, need to be quarantined for d1 days. All passengers that are not infected, not edge-adjacent to any infected passenger, but corner-adjacent to any infected passenger, need to be quarantined for d2 days.
The passengers need to stay in the hotel during quarantine. According to the regulations, the government needs to pay for the hotel. As an accountant of the government, you are asked to evaluate the expected total number of days the passengers need to be quarantined, which indicates the expected total cost on paying for the hotel.
For example, suppose n = 4 , m = 4 , d0 = 15 , d1 = 7 , d2 = 3 . The third passenger in the third row is infected, and we don’t know whether the second passenger in the first row is infected or not. Other 14 passengers are not infected.
If the second passenger in the first row is infected, then the total number of days of quarantine is 91 :
7 15 7 0
3 7 7 3
0 7 15 7
0 3 7 3
If that passenger is not infected, then the total number of days of quarantine is 55 :
0 0 0 0
0 3 7 3
0 7 15 7
0 3 7 3
So the expected total number of days of quarantine is (91+55)/2 = 73 .

输入

The first line contains five integers n , m , d0 , d1 and d2 . The following n lines contain m characters each. The j -th character of the i -th line represents the passenger occupying the j-th seat of the i -th row. Each character is one of ‘V’, ‘.’, or ‘?’. ‘V’ means an infected passenger, ‘.’ means a not infected passenger, and ‘?’ means a assenger that has 1/2 chance being infected.

输出

The expected total number of days the passengers need to be quarantined, modulo $10^9+7$ .
It can be proved that the answer can be represented by a rational number p/q where q is not a multiple of $10^9+7$ . Then you need to print p × $q^{-1}$ modulo $10^9+7$ , where $q^{-1}$ means the multiplicative inverse of q modulo $10^9+7$ .
Note: If x × q ≡ 1 mod $10^9+7$ , then x is the multiplicative inverse of q modulo $10^9+7$ .

样例输入

【样例1】

4 4 15 7 3
.?..
....
..V.
....

【样例2】

2 2 1 1 1
??
??

样例输出

【样例1】
73
【样例2】
750000009

提示

Technical Specification
• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• 0 ≤ d2 ≤ d1 ≤ d0 ≤ 100

思路分析

本题最终目的是求所有乘客需要被隔离的期望总天数——可以拆解为求每位乘客需要被隔离的天数，然后再相加。至于怎么求每位乘客需要被隔离的期望天数，需要求取每种情况的概率，乘上该种情况对应的天数，再求和。
在求概率的时候用到了逆元。

逆元

利用费马小定理求乘法逆元
$b\cdot b_{inv}\equiv 1(mod\ p)$
费马小定理：若p为质数，则 $a^{p-1}\equiv 1(mod\ p)$
#define ll long long
ll fast_power(ll a,ll b,ll mod){if(a==0){if(b==0)return 1;else return 0;}ll ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=(a*a)%mod;b>>=1;}return ans;
}
ll get_inv(ll x,ll p){return fast_power(x,p-2,p);
}
利用扩展欧几里得算法
扩展欧几里得算法：求ax+by=gcd(a,b)的一组x,y
求a在模p意义下的乘法逆元： $a\cdot a_{inv}\equiv 1(mod\ p)$
void exgcd(int a,int b,int&x,int&y){if(b==0){x=1;y=0;}int gcd=exgcd(b,a%b,y,x);y-=(a/b)*x;
}
int get_inv(int a,int p){int x=1,y=0;exgcd(a,p,x,y);return (x%p+p)%p;
}

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int n,m,d0,d1,d2;
ll ans=0;
char a[110][110];
ll v[110][110],p1[110][110],p2[110][110];
ll fast_power(ll a,ll b){if(a==0){if(b==0)return 1;else return 0;}ll ans=1;while(b){if(b&1){ans=(ans*a)%mod;}a=(a*a)%mod;b>>=1;}return ans;
}
ll get_p(char c){if(c=='V')return 1;else if(c=='.')return 0;else{return fast_power(2,mod-2);}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m>>d0>>d1>>d2;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];v[i][j]=get_p(a[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ll np1=1;np1=np1*(mod+1-v[i-1][j])%mod;np1=np1*(mod+1-v[i][j-1])%mod;np1=np1*(mod+1-v[i+1][j])%mod;np1=np1*(mod+1-v[i][j+1])%mod;p1[i][j]=(mod+1-np1)%mod;ll np2=1;np2=np2*(mod+1-v[i-1][j-1])%mod;np2=np2*(mod+1-v[i+1][j-1])%mod;np2=np2*(mod+1-v[i+1][j+1])%mod;np2=np2*(mod+1-v[i-1][j+1])%mod;p2[i][j]=(mod+1-np2)%mod;}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ll part1=d0*v[i][j]%mod;ll part2=d1*(mod+1-v[i][j])%mod*p1[i][j]%mod;ll part3=d2*(mod+1-v[i][j])%mod*(mod+1-p1[i][j])%mod*p2[i][j]%mod;ans=(ans+part1+part2+part3)%mod;}}ans=(ans%mod+mod)%mod;cout<<ans;return 0;
}