分类 拖延症 下的文章

E. Inverse Coloring

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--E. Inverse Coloring

题解

高档题,题意大概是构造一个n*n的矩阵,要求满足相邻行与相邻列之间要么完全相同,要么完全相反。且不存在面积大于等于k的子矩阵颜色完全相同。
首先我们可以发现,只要确定了首行和首列即可得到整个矩阵,且最大颜色相同的矩阵为行最大连续颜色乘以列最大连续颜色。则我们dp行最大连续颜色与列最大连续颜色的数量,再分别枚举即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 505;
const int mod = 998244353;
ll dp[maxn][maxn][2];//λ�ã�������������ɫ��
ll num[maxn];

int main() {
    ios::sync_with_stdio(0);    cin.tie(0);    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int k = 1; k <= n; k++) {
        memset(dp, 0, sizeof(dp));
        dp[1][1][0] = dp[1][1][1] = 1;
        for (int i = 2; i <= n; i++) {//�
            for (int j = 1; j <= min(i,k); j++) {//��������
                dp[i][1][1] += dp[i - 1][j][0];
                dp[i][1][0] += dp[i - 1][j][1];
                dp[i][j][1] += dp[i - 1][j - 1][1];
                dp[i][j][0] += dp[i - 1][j - 1][0];
                dp[i][1][0] %= mod;
                dp[i][1][1] %= mod;
                dp[i][j][0] %= mod;
                dp[i][j][1] %= mod;
            }
        }
        for (int i = 1; i <= k; i++) {
            num[k] += dp[n][i][0] + dp[n][i][1];
            num[k] %= mod;
        }
    }
    for (int i = n; i >= 2; i--) {
        num[i] = num[i] - num[i - 1] + mod;
        num[i] %= mod;
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i*j >= k)break;
            ans += num[i] * num[j];
            ans %= mod;
        }
    }
    if (ans % 2 == 1)ans = (ans + mod) / 2;
    else ans /= 2;
    cout << ans << endl;
}

[BZOJ 3930] [CQOI 2015] 选数

题目链接

[BZOJ 3930] [CQOI 2015] 选数

题解

中档题。题意大概是求从L到H中取N个数使它们的最大公约数为K的选区方案数。
考虑原题让你求l-r中gcd(i,j)=k的个数。
等价于求l/k-r/k中gcd(i,j)=1的个数.
我们设d[i]表示l/k-r/k中gcd(i,j)=i的个数,
容斥一下即可.注意特判所有数都相等的情况。

代码

Time: 220ms
Memory: 2068kB
#include<iostream>
using namespace std;

const long long  MOD = 1e9 + 7;
const int  MAXN = 100050;

long long a[MAXN], N, K, L, H, l, r;

long long quick_power(long long a, long long b) {
    long long ans = 1;
    while (b) {
        if (b & 1)ans = ans * a%MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

int main() {
    cin >> N >> K >> L >> H;
    l = L / K, r = H / K;
    if (L % K)l++;
    for (int i = H - L; i; i--) {
        int ll = l / i, rr = r / i;
        if (l % i)ll++;
        if (l <= r) {
            a[i] = (quick_power(rr - ll + 1, N) - (rr - ll + 1)) % MOD;
            for (int j = i * 2; j <= H - L; j += i)a[i] = (a[i] - a[j]) % MOD;
        }
    }
    if (l == 1)a[1]++;
    cout << (a[1] + MOD) % MOD << endl;
    return 0;
}