超級結論題。。。

首先建出原圖的補圖，再考慮縮點。

縮完點后是一個有向無環圖。
這個圖的每個點代表一個強聯通分量。
考慮一個大小大于\(1\)的強聯通分量中的一個點\(i\)，那么\(i\)永遠不可能開槍。

因為\(i\)開槍需要假設自己的狗沒病，然后枚舉自己看不到的狗的狀態，然而由于有他的轉移依賴的狀態 依賴他，那么就會循環轉移。
導致他一直到inf都不會開槍。

那么任何可以到達大于1的強聯通分量的強聯通分量都廢了（包括本身），因為他們中所有點都只能不是病狗。

現在每個強聯通分量都是單點強聯通分量。

考慮一個狀態，每個病狗的主人都非常聰明但也非常謹慎，它從他的狗沒病，并且他不知道的狗狀態隨便的狀態 中 開槍時間最大 的一種 轉移過來。
然后所有主人的答案取\(min\)。
這樣一次最多在 可到達點集 中去掉一個點，且肯定可以去掉一個點，因為拓撲序最小的點肯定去掉后再也不能被染黑了。
那么可以容易得出，狀態的貢獻就是它可以到的點集大小。再計算點的貢獻。

考慮只有凸集上的點才能貢獻答案（因為你取min的時候只能選凸集上的點)，第二問也可以用點的貢獻做。

#include <bits/stdc++.h>using namespace std; const int N=3010; typedef long long ll; int dfn[N],low[N],clk; int isc[N],sz[N],nscc; stack<int> st; vector<int> e[N],g[N]; void Tajan(int x){//cerr<<"Tajan"<<x<<endl;dfn[x]=low[x]=++clk;st.push(x);for (auto i:e[x]){if (!dfn[i]) Tajan(i);if (!isc[i]) low[x]=min(low[x],low[i]);}if (dfn[x]==low[x]){++nscc;while (1){int u=st.top(); st.pop();isc[u]=nscc;++sz[nscc];//cerr<<"pop"<<nscc<<" "<<u<<endl;if (u==x) break;}} } bitset<N> b[N];const int M=998244353;int add(int x,int y){return (x+=y)>=M?x-M:x; } int sub(int x,int y){return (x-=y)<0?x+M:x; } int fp(int x,int y){int ret=1;for (; y; y>>=1,x=(ll)x*x%M) if (y&1) ret=(ll)ret*x%M;return ret; } char s[N]; int n; int fc[N]; vector<int> ups[N]; int f[N]; int main(){scanf("%d",&n);for (int i=1; i<=n; ++i){scanf("%s",s+1);for (int j=1; j<=n; ++j)if (j!=i&&s[j]=='0'){//cerr<<i<<" "<<j<<endl;e[i].push_back(j);}}for (int i=1; i<=n; ++i){//cerr<<"????"<<i<<endl;if (!dfn[i]) Tajan(i);}//cerr<<nscc<<endl;for (int i=1; i<=n; ++i){for (auto j:e[i]){int x=isc[i];int y=isc[j];ups[y].push_back(x);if (sz[x]>1||sz[y]>1) continue;g[x].push_back(y);}}queue<int> q;for (int i=1; i<=nscc; ++i)if (sz[i]>1) q.push(i),f[i]=0; else f[i]=1000000;while (!q.empty()){int x=q.front(); q.pop();for (auto j:ups[x])if (f[j]==1000000){f[j]=f[x]+1;q.push(j);}}int tot=0,ans1=0,ans2=0;for (int i=1; i<=nscc; ++i) tot+=(sz[i]==1&&f[i]==1000000);for (int i=1; i<=n; ++i) fc[isc[i]]=i;for (int i=nscc; i>=1; --i)if (sz[i]==1&&f[i]==1000000){//cerr<<fc[i]<<endl;//cerr<<i<<" "<<fc[i]<<endl;b[i].set(fc[i]);for (auto j:g[i]) b[j]|=b[i];ans1=add(ans1,(ll)sub(fp(2,b[i].count()),1)*fp(2,tot-b[i].count())%M);ans2=add(ans2,fp(2,tot-b[i].count()));}cout<<ans1<<" "<<ans2<<endl; }

轉載于:https://www.cnblogs.com/Yuhuger/p/10560512.html

總結

以上是生活随笔為你收集整理的UR#6 懒癌的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。