2020-2021:teams:wangzai_milk:cf2100-2800泛做1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/04 19:43] zars19 [1388E - Uncle Bogdan and Projections] |
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:24] (当前版本) zars19 [1332E - Height All the Same] |
||
|---|---|---|---|
| 行 643: | 行 643: | ||
| } | } | ||
| </code></hidden> | </code></hidden> | ||
| - | // | + | \\ |
| + | |||
| + | ====== 1332E - Height All the Same ====== | ||
| + | |||
| + | $n\times m$ 的网格，位置 $(i,j)$ 上有 $a_{i,j}$ 个方块，每次操作可以在某位置加两个方块，或者在两个相邻位置各加一个方块，目标是使得所有位置高度一致。问在 $a_{i,j}\in[l,r]$ 的条件下，能达成目标的方案有多少。 | ||
| + | |||
| + | 一个观察是重要的只是所有位置上方块数量的奇偶性，同一个位置加两个方块这一操作不改变奇偶性，而使得所有位置奇偶性一致后必能用这个操作达成目标。 | ||
| + | |||
| + | 另一个观察是，我们必能改变且仅改变任意一对格子的奇偶性（这是因为两个位置间必有一条路径，沿路径每次翻转相邻两个就好）。 | ||
| + | |||
| + | 当有偶数个奇数或偶数个偶数个时，可以把它们两两配对改变奇偶性达成目标，否则不可以。 | ||
| + | |||
| + | * 当 $n\times m$ 为奇数时，必然是偶数个奇数奇数个偶数/偶数个偶数奇数个奇数，答案是总数 $\mathrm{total}=(r-l+1)^{nm}$ 。 | ||
| + | * 当 $n\times m$ 为偶数时，奇偶都是偶数个可以，奇偶都是奇数个不行。pikmike提供了一个直觉法： | ||
| + | |||
| + | * 当 $r-l+1$ 为偶数时，答案是 $\frac{\mathrm{total}}2$ | ||
| + | * 当 $r-l+1$ 为奇数时，可行将会比不可行多 $1$ 。这是因为 $[l,r]$ 中必定有 $k\in[l,r]且 k\oplus1\notin[l,r]$ 。每一种方案，我们可以选第一个不为 $k$ 的位置给 $a_{i,j}$ 异或 $1$ ，这样可以使可行方案与不可行方案两两配对，除了全部为 $k$ 的一个方案可行。答案 $\frac{\mathrm{total}+1}{2}$ | ||
| + | |||
| + | <hidden><code cpp> | ||
| + | #include<bits/stdc++.h> | ||
| + | #define ll long long | ||
| + | #define fi first | ||
| + | #define se second | ||
| + | #define mp make_pair | ||
| + | #define pb push_back | ||
| + | #define pii pair<int,int> | ||
| + | using namespace std; | ||
| + | const ll mod=998244353; | ||
| + | ll n,m,l,r; | ||
| + | ll qpow(ll a,ll b) | ||
| + | { | ||
| + | ll res=1; | ||
| + | while(b) | ||
| + | { | ||
| + | if(b&1)res=res*a%mod; | ||
| + | a=a*a%mod,b>>=1; | ||
| + | } | ||
| + | return res; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | scanf("%lld%lld%lld%lld",&n,&m,&l,&r); | ||
| + | ll tot=qpow(r-l+1,n*m); | ||
| + | if((n*m)&1)printf("%lld\n",tot); | ||
| + | else if((r-l+1)&1)printf("%lld\n",(tot+1)%mod*qpow(2,mod-2)%mod); | ||
| + | else printf("%lld\n",tot*qpow(2,mod-2)%mod); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | \\ | ||
2020-2021/teams/wangzai_milk/cf2100-2800泛做1.1596541387.txt.gz · 最后更改: 2020/08/04 19:43 由 zars19
