Description

小w 偶然間見到了一個DAG。
這個DAG 有m 層，第一層只有一個源點，最后一層只有一個匯點，剩下的每一層都有k 個節點。
現在小w 每次可以取反第i(1 < i < n - 1) 層和第i + 1 層之間的連邊。也就是把原本從(i， k1) 連到(i + 1， k2) 的邊，變成從(i， k2) 連到(i + 1， k1)。
請問他有多少種取反的方案，把從源點到匯點的路徑數變成偶數條？
答案對998244353 取模。

Input

一行兩個整數m, k。
接下來m - 1 行, 第一行和最后一行有k 個整數0 或1，剩下每行有k2 個整數0 或1，第(j- 1)* k + t 個整數表示(i， j) 到(i + 1， t)有沒有邊。

Output

一行一個整數表示答案。

Sample Input

5 3
1 0 1
0 1 0 1 1 0 0 0 1
0 1 1 1 0 0 0 1 1
0 1 1

Sample Output

4

Data Constraint

20% 的數據滿足n <= 10, k <= 2
40% 的數據滿足n <= 10^3, k <= 2。
60% 的數據滿足m <= 10^3, k <= 5。
100% 的數據滿足4 <= m <= 10^4, k <= 10。

Solution

• 考慮狀壓每?層的?案數奇偶性做 DP 。

• 設 F[i][j] 表示做到第 i 層、此時狀態為 j 的方案數。

• 設 G[j] 表示狀態 j 的二進制中“1”的個數的奇偶性（偶數為0，奇數為1）。則：G[j]=G[j>>1] xor (j and 1)

• 即用之前 少一位的狀態 異或上 這一位的奇偶性 推出 這個狀態。

• 設初始層狀態為 s1 ，結束層狀態為 s2。

• 則顯然初始狀態即為 F[1][s1]=1 。

• 若一個狀態 i 滿足 G[i and s2]=0 （即為偶數條路徑），則 F[N][i] 可加入答案。

• 至于層與層之間的轉移，設出這一層（單層）的狀態 a,b （交換前和交換后），

• a,b 都可以根據本層的連邊處理出來。

• 至于轉移的話，只需轉移狀態是奇數的情況，因為偶數不影響奇偶性（偶+偶=偶，偶+奇=奇）。

• 時間復雜度 O(N?K?2K) 。

Code

#include<cstdio> #include<cstring> #define clr(a) memset(a,0,sizeof(a)) using namespace std; const int mo=998244353; int roll,s1,s2; long long ans; int f[2][1<<10],g[1<<10]; int a[11],b[11]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {int n=read(),k=read(),s=1<<k;for(int i=0;i<k;i++) s1|=read()<<i;for(int i=0;i<s;i++) g[i]=g[i>>1]^i&1;f[0][s1]=1;for(int i=2;i<n-1;i++){clr(f[roll^=1]),clr(a),clr(b);for(int j=0;j<k;j++)for(int l=0;l<k;l++){int x=read();a[j]|=x<<l;b[l]|=x<<j;}for(int j=0;j<s;j++)if(f[roll^1][j]){for(int l=s1=s2=0;l<k;l++){s1|=g[j&a[l]]<<l;s2|=g[j&b[l]]<<l;}f[roll][s1]=(f[roll][s1]+f[roll^1][j])%mo;f[roll][s2]=(f[roll][s2]+f[roll^1][j])%mo;}}for(int i=s2=0;i<k;i++) s2|=read()<<i;for(int i=0;i<s;i++)if(!g[s2&i]) ans=(ans+f[roll][i])%mo;printf("%lld",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5398. 【NOIP2017提高A组模拟10.7】Adore的全部內容，希望文章能夠幫你解決所遇到的問題。

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