Atcoder Coddi2018 F.Square
题目描述
有一个n*n的网格,有一些位置已经填好,问有多少种填法使对于每个1<i<j<n,(i,i)到(j,j)间的网格数的和是偶数。
题解
先假设对角线下一半的数都是0,令x_i=a_{i,i}。
– 考虑每个2*2的正方形,发现a_{i,i+1}=x_i+x_{i+1}。
– 考虑每个3*3的正方形,发现a_{i,i+2}=x_{i+1}。
– 更大的正方形只能是0.(用容斥的方法可以得到上述结论)。
那我们可以逆推:
– 如果a_{i,i}填入一个数,那么x_i=a_{i,i}。
– 如果a_{i,i+1}填入一个数,那么x_i+x_{i+1}=a_{i,i+1}。
– 如果a_{i,i+2}填入一个数,那么x_{i+1}=a_{i,i+2}。
– 其他位置都是0。
所以我们只需要决定对角线的数,其他位置都是固定的。
这是个简单的dp问题。
那么如果下面不是0呢?
可以转化成0!定义a_{i,j}和a_{j,i}为对应位置,只要让对应位置的数相等就可以随意转化。
– 如果两个位置上都填了数,就把下一半的数设置成0,上一半变成它们的和。
– 如果有一个位置填了数,就把下一半设置成0,上一半变成无限制。(如果是1就相当于下面的数也填1,不影响结果)
– 如果没有位置填数,就把下一半设置成0,上一半变成无限制。并把结果*2(都是0或都是1)。
细节处理很烦。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<map> #define ll long long #define pii pair<int,int> using namespace std; map<pii,int> mp; int read() { char ch=getchar();int f=0,x=1; while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();} while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();} return f*x; } int n,m,a[200005],b[200005],c[200005]; ll f[200005][3],ans;bool vis[200005]; int g[200005],h[200005]; const int mod=998244353; ll quick_mod(ll x,ll y) { ll ret=1; while(y) { if(y&1LL) ret=ret*x%mod; x=x*x%mod; y>>=1; } return ret; } void mo(ll &x) { if(x>=mod) x-=mod; } int main() { n=read();m=read(); memset(g,-1,sizeof(g)); memset(h,-1,sizeof(h)); for(int i=1;i<=m;i++) { a[i]=read();b[i]=read();c[i]=read(); mp[pii(a[i],b[i])]=i; } int cou=0; for(int i=1;i<=m;i++) { if(!vis[i]) { if(a[i]==b[i]) { c[i]=c[i]; //vis[i]=1; } else if(mp[pii(b[i],a[i])]) { int num=mp[pii(b[i],a[i])]; vis[num]=1; c[i]=(c[i]+c[num])%2; } else { vis[i]=1; } if(a[i]!=b[i]) cou++; //else //{ if(abs(a[i]-b[i])>=3&&!vis[i]&&c[i]!=0) { puts("0"); return 0; } //} } } ans=quick_mod(2,1LL*n*(n-1)/2-cou); for(int i=1;i<=m;i++) { if(!vis[i]) { if(a[i]<b[i]) swap(a[i],b[i]); if(a[i]==b[i]) { if(g[a[i]]!=-1&&g[a[i]]!=c[i]) { puts("0"); return 0; } g[a[i]]=c[i]; } else if(a[i]-b[i]==2) { if(g[a[i]-1]!=-1&&g[a[i]-1]!=c[i]) { puts("0"); return 0; }g[a[i]-1]=c[i]; } else if(a[i]-b[i]==1) { if(h[a[i]]!=-1&&h[a[i]]!=c[i]) { puts("0"); return 0; } h[a[i]]=c[i]; } } } f[0][0]=1; for(int i=1;i<=n;i++) { if(g[i]!=1) { if(h[i]!=1) mo(f[i][0]+=f[i-1][0]); if(h[i]!=0) mo(f[i][0]+=f[i-1][1]); } if(g[i]!=0) { if(h[i]!=1) mo(f[i][1]+=f[i-1][1]); if(h[i]!=0) mo(f[i][1]+=f[i-1][0]); } //cout<<f[i][0]<<" "<<f[i][1]<<endl; } cout<<1LL*ans*(f[n][0]+f[n][1])%mod; } |