srm 555

发表于   |   分类于   |  

255

Description

问能将一个$0/1$串最少分成几个串使得每个串都是$5$的整数次幂，且没有前导零

Solution

dp即可，$dp[i]$表示前$i$个字符分割的结果，枚举一个分割点$j$，$check$即可

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 55;
int dp[N];
struct CuttingBitString {
    bool ok(LL x) {
        while (x && x % 5 == 0) x /= 5;
        return x == 1;
    }
    int getmin(string S) {
        string s = "0" + S + "1";
        int n = s.size();
        for (int i = 1; i <= n; ++i)    dp[i] = 10000;
        for (int i = 1; i < n; ++i) {
            if (s[i] == '1') {
                for (int j = 0; j < i - 1; ++j) {
                    if (dp[j] == 10000 || s[j + 1] == '0')  continue;
                    LL now = 0;
                    for (int k = j + 1; k <= i - 1; ++k)    now = now * 2 + (s[k] == '1' ? 1 : 0);
                    if (ok(now))    dp[i - 1] = min(dp[i - 1], dp[j] + 1);
                }
            }
        }
        return dp[n - 2] == 10000 ? -1 : dp[n - 2];
    }
};

555

Description

有一个$H*W$的全$0$矩阵，给定对行列操作数，每次操作将行列$0/1$翻转，使得最后矩阵$1$的个数为$S$,求方案数
两个方案不同当且仅当有一行或列操作数不同

Solution

很容易想到操作两次相当于没操作，枚举行列分别操作$1$次的个数，剩下的相当于$n$个物品(n对操作两次)放到$m$个不同盒子的方案数，即$\binom{n+m-1}{n}$，统计即可

Code

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
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> pii;
const int N = 1600, M = 555555555;
int c[N << 1][N << 1];
struct XorBoard {
    int count(int H, int W, int Rcount, int Ccount, int S) {
        for (int i = 0; i <= 1555 * 2; ++i) {
            c[i][0] = 1;
            for (int j = 1; j <= i; ++j)    c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % M;
        }
        int ans = 0;
        for (int i = 0; i <= Rcount && i <= H; ++i)
            for (int j = 0; j <= Ccount && j <= W; ++j) {
                if (i * W + j * H - 2 * i * j != S) continue;
                if ((Rcount - i) & 1 || (Ccount - j) & 1)   continue;
                int rl = (Rcount - i) / 2, cl = (Ccount - j) / 2;
                (ans += (LL)c[rl + H - 1][rl] * c[H][i] % M * c[cl + W - 1][cl] % M * c[W][j] % M) %= M;
            }
        return ans;
    }
};