1332E - Height All the Same

发表于 | 阅读数

$n\times m$的方格，每个可以放$[L,R]$个方块。有两种操作

  • 给某个$+2$
  • 给相邻$+1,+1$

求无限次操作完可以同高度的小木块的放置方案数

比赛时脑抽。每个小方块$+2$，其实最后相差$0,1$。可以用$1,0$表示所有高度小方块。$10\rightarrow 01,00\rightarrow 11$。

  • 如果$n*m\%2==1$ ，一定有个$1$或$0$的个数为偶数，随便放即可。
  • 如果$nm\%2==0$ ，$1$和$0$的个数必须为偶数，(奇数参考$01$)，随便放即可。即$C_{nm}^{2*k}(x0)^{2k}(x1)^{n-2k}=\frac{(x1+x0)^n-(x1-x0)^n}{2}$
  • 快速幂还是用$long long$，被卡常再换回来吧。
代码 
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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 998244353;

ll qpow(ll a, ll x, ll mo)
{
    ll res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        a = 1ll * a * a % mo;
        x >>= 1;
    }
    return res;
}
ll n, m, R, L;
int main()
{
    cin >> n >> m >> L >> R;
    if (L == R)
    {
        puts("1");
        return 0;
    }
    ll k = R - L;
    ll p = n * m;
    ll x = (R - L + 1);
    ll inv2 = qpow(2, mod - 2, mod);
    ll ans;
    if ((n * m) % 2)

        ans = 1ll * qpow(x, p, mod) % mod;
    else if (x % 2 == 0)
        ans = 1ll * qpow(x, p, mod) * inv2 % mod;
    else
        ans = 1ll * (qpow(x, p, mod) + 1) * inv2 % mod;
    cout << ans << endl;
}