題目描述

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? .
It can be proved that the answer can be represented by a rational number p/q where q is not a multiple of ?. Then you need to print p × ?modulo ??, where ?means the multiplicative inverse of q modulo? .
Note: If x × q ≡ 1 mod? , then x is the multiplicative inverse of q modulo ?.

樣例輸入

【樣例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

思路分析

本題最終目的是求所有乘客需要被隔離的期望總天數——可以拆解為求每位乘客需要被隔離的天數，然后再相加。至于怎么求每位乘客需要被隔離的期望天數，需要求取每種情況的概率，乘上該種情況對應的天數，再求和。

在求概率的時候用到了逆元。

逆元

利用費馬小定理求乘法逆元

費馬小定理：若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意義下的乘法逆元：

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;
}