標簽：its 自己 getchar turn -- clu color return 移動
這裏提供一個不同的思路
我們考慮對于每對相鄰的位置，單獨地計算它的貢獻
先只考慮橫著的情況
我們發現只有當欽定的方格兩旁紅色格子數同偶時才會計入答案，貢獻1(\((RR)\underline{(RR)}(RR)\))
而異奇偶時貢獻1/2（\((O\underline{(RR)}(RR)\)與\((R\underline{R)O}(RR)\)同樣爲最大答案）
而同奇時不計入答案(\((R\underline{R)(R}R)\))
所以設此對格子\((x,y)(x,y+1)\)左右能延伸到的最長空位(含自己)分別爲\(L,R\)
對于每種情況單獨維護，先考慮同偶時貢獻(設總空位數爲\(cnt\)):
\(\sum_{i=2k+1,i\in[1,L]}\sum_{j=2t+1,j\in[1,R]}2^{cnt-i-j-[i\not= L]-[j\not =R]}\)
爲什麽呢？因爲我們相當于枚舉了這段紅塊的長度，而紅塊的兩旁需要爲空或者藍色
直接操作發現是\(O((nm)^3)\)的，考慮優化
這裏已經是\(O(nm(n+m))\)了,因爲發現遍曆過程中每次只會\(++L,--R\)以及在每一空段的開頭\(O(len)\)地处理，所以每次移動只会更改\(sigma\)內2項的值，可以動態維護括號內的累和
這樣時間複雜度\(O(nm)\),這裏由于賽時敲傻了，所以打的比較複雜，實際上可以非常簡單的
#include<bits/stdc++.h>
using namespace std;
# define ll long long
# define read read1<ll>()
# define Type template<typename T>
Type T read1(){
T t=0;
char k;
bool vis=0;
do (k=getchar())==‘-‘&&(vis=1);while(‘0‘>k||k>‘9‘);
while(‘0‘<=k&&k<=‘9‘)t=(t<<3)+(t<<1)+(k^‘0‘),k=getchar();
return vis?-t:t;
}
# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)
# define mod 998244353
# define inv2 499122177ll
char *str[300005];
int n,m;
ll qkpow(ll n,int m){
ll t=1;
for(;m;m>>=1,n=n*n%mod)
if(m&1)t=t*n%mod;
return t;
}ll Invp[300010];
ll Qkpow(int x){return Invp[-x];}
int main(){
n=read,m=read;*str=new char[m+5]();
str[n+1]=new char[m+5]();
for(int i=1;i<=n;++i){
str[i]=new char[m+5]();
scanf("%s",str[i]+1);
}int cnt=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(str[i][j]==‘o‘)
++cnt;
Invp[0]=1;
for(int i=1;i<=n+m+5;++i)Invp[i]=Invp[i-1]*inv2%mod;
ll ans=0,t1,t2,t3,t4,va=qkpow(2,cnt);
for(int i=1;i<=n;++i)
for(int j=1,l=0,r=0;j<m;++j,++l,--r)
if(str[i][j]==‘o‘&&str[i][j+1]==‘o‘){
if(r<=0){
l=r=0;
for(int k=j;str[i][k]==‘o‘;--k)++l;
for(int k=j+1;str[i][k]==‘o‘;++k)++r;
t1=0,t2=0,t3=0,t4=0;
for(int o=1;o<=l;o+=2)
(t1+=Qkpow(-o-(l!=o)))%=mod;
for(int p=1;p<=r;p+=2)
(t2+=Qkpow(-p-(r!=p)))%=mod;
for(int o=2;o<=l;o+=2)
(t3+=Qkpow(-o-(l!=o)))%=mod;
for(int p=2;p<=r;p+=2)
(t4+=Qkpow(-p-(r!=p)))%=mod;
}else{
int o=l-1;if(~o&1)--o;
t1=(t1-Qkpow(-o-(l-1!=o))+Qkpow(-o-(l!=o)))%mod;
o=l-1;if(o&1)--o;
t3=(t3-Qkpow(-o-(l-1!=o))+Qkpow(-o-(l!=o)))%mod;
if(l&1)t1=(t1+Qkpow(-l))%mod;
else t3=(t3+Qkpow(-l))%mod;
int p=r-1;if(~p&1)++p;
t2=(t2-Qkpow(-p-(r+1!=p))+Qkpow(-p-(r!=p)))%mod;
p=r-1;if(p&1)++p;
t4=(t4-Qkpow(-p-(r+1!=p))+Qkpow(-p-(r!=p)))%mod;
if(r&1)t4=(t4-Qkpow(-r-1))%mod;
else t2=(t2-Qkpow(-r-1))%mod;
}
ans=(ans+(t1*t2+t1*t4%mod*inv2+t2*t3%mod*inv2)%mod*va)%mod;
}
for(int j=1;j<=m;++j)
for(int i=1,l=0,r=0;i<n;++i,++l,--r)
if(str[i][j]==‘o‘&&str[i+1][j]==‘o‘){
if(r<=0){
l=r=0;
for(int k=i;str[k][j]==‘o‘;--k)++l;
for(int k=i+1;str[k][j]==‘o‘;++k)++r;
t1=0,t2=0,t3=0,t4=0;
for(int o=1;o<=l;o+=2)
(t1+=Qkpow(-o-(l!=o)))%=mod;
for(int p=1;p<=r;p+=2)
(t2+=Qkpow(-p-(r!=p)))%=mod;
for(int o=2;o<=l;o+=2)
(t3+=Qkpow(-o-(l!=o)))%=mod;
for(int p=2;p<=r;p+=2)
(t4+=Qkpow(-p-(r!=p)))%=mod;
}else{
int o=l-1;if(~o&1)--o;
t1=(t1-Qkpow(-o-(l-1!=o))+Qkpow(-o-(l!=o)))%mod;
o=l-1;if(o&1)--o;
t3=(t3-Qkpow(-o-(l-1!=o))+Qkpow(-o-(l!=o)))%mod;
if(l&1)t1=(t1+Qkpow(-l))%mod;
else t3=(t3+Qkpow(-l))%mod;
int p=r-1;if(~p&1)++p;
t2=(t2-Qkpow(-p-(r+1!=p))+Qkpow(-p-(r!=p)))%mod;
p=r-1;if(p&1)++p;
t4=(t4-Qkpow(-p-(r+1!=p))+Qkpow(-p-(r!=p)))%mod;
if(r&1)t4=(t4-Qkpow(-r-1))%mod;
else t2=(t2-Qkpow(-r-1))%mod;
}
ans=(ans+(t1*t2+t1*t4%mod*inv2+t2*t3%mod*inv2)%mod*va)%mod;
}cout<<(ans+mod)%mod;
return 0;
}
CF1511E Colorings and Dominoes
標簽：its 自己 getchar turn -- clu color return 移動
原文地址：https://www.cnblogs.com/SYDevil/p/15012930.html
