SDNU ICPC Wiki

Difference between revisions of "BreakFast:2021HDU暑期多校训练营1"

BreakFast:2021HDU暑期多校训练营1 (view source)

Revision as of 15:51, 30 July 2021

6,289 bytes added ,  15:51, 30 July 2021
→‎bitset 优化: update D
(update C)
(→‎bitset 优化: update D)
 
(One intermediate revision by the same user not shown)
Line 240: Line 240:
}</syntaxhighlight>
}</syntaxhighlight>


[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop]
=== bitset 优化 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e6;
const int N = (int)17;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;
 
int n, m;
char s[N + 5][N + 5];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int row, col;
bitset<614> a[2 * (N + 1) * (N + 1) + 5];
 
inline int id(int x1, int y1, int x2, int y2)
{
    if(x1 > x2) swap(x1, x2);
    if(y1 > y2) swap(y1, y2);
    if(x1 == x2) return (x1 - 1) * m + y1;
    else        return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
}
 
void build()
{
    row = 0, col = (n + 1) * m + n * (m + 1);
    for(int i = 1; i <= n + 1; ++i)
    {
        for(int j = 1; j <= m + 1; ++j)
        {
            ++row;
            a[row].reset();
            for(int k = 0, x, y; k < 4; ++k)
            {
                x = i + dx[k], y = j + dy[k];
                if(x < 1 || x > n + 1 || y < 1 || y > m + 1)    continue;
                a[row].set(id(x, y, i, j));
            }
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= m; ++j)
        {
            if(s[i][j] == '.') continue;
            ++row;
            a[row].reset();
            a[row].set(id(i, j, i, j + 1));
            a[row].set(id(i, j, i + 1, j));
            a[row].set(id(i, j + 1, i + 1, j + 1));
            a[row].set(id(i + 1, j, i + 1, j + 1));
            a[row].set(col + 1, s[i][j] - '0');
        }
    }
//    for(int i = 1; i <= row; ++i)
//    {
//        bool f = 0;
//        for(int j = 1; j <= col; ++j)
//        {
//            if(!a[i][j])    continue;
//            if(f) printf(" ^ ");
//            printf("x(%d)", j);
//            f = 1;
//        }
//        printf(" = 0\n");
//    }
}
 
int gauss(int n, int m)
{
    int c, r;
    for(c = 1, r = 1; c <= m; ++c)
    {
        int t = r;
        for(int i = r; i <= n; ++i)
        {
            if(a[i][c])  t = i;
        }
        if(!a[t][c]) continue;
        swap(a[t], a[r]);
        for(int i = 1; i <= n; ++i)
        {
            if(i == r)  continue;
            if(a[i][c]) a[i] ^= a[r];
        }
        ++r;
    }
    for(int i = r; i <= n; ++i)
    {
        if(a[i][m + 1])  return -1;//无解
    }
    return m - r + 1;//自由元个数
}
 
ll quick(ll a, ll b, ll p = mod)
{
    ll s = 1;
    while(b)
    {
        if(b & 1) s = s * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return s;
}
 
void work()
{
    scanf("%d %d", &n, &m);
    --n, --m;
    for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    build();
    int r = gauss(row, col);
    if(r == -1) printf("0\n");
    else        printf("%lld\n", quick(2, r));
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>
 
== [https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] ==
 
=== 题目大意 ===
 
<math display="inline">T</math> 组输入，每组给 <math display="inline">n</math> 和 <math display="inline">k</math>.
 
有 <math display="inline">n</math> 个物品，价值分别为 <math display="inline">a[1], a[2], \cdots, a[n]</math>，每件物品有无穷多件.
 
求拼凑出总价值为 <math display="inline">k</math> 的方案数.
 
<math display="inline">1 \leq T \leq 100, 1 \leq n \leq 100, 1 \leq k \leq 10^{18}, 1 \leq a[i] \leq 10</math>.
 
=== 分析 ===
 
设 <math display="inline">f[i][j]</math> 表示考虑了前 <math display="inline">i</math> 个物品，总价值为 <math display="inline">j</math> 的方案数.
 
则有状态转移方程 <math display="inline">\begin{aligned} f[i][j] = \sum_{l = 0}^{\lfloor \frac{j}{a[i]} \rfloor}{f[i - 1][j - l \times a[i]]} \end{aligned}</math>.
 
接下来这一步被题解惊艳到了，拉格朗日插值！！！
 
但体会一下也就明白了，还是很妙的感觉.
 
=== 代码实现 ===
 
<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int M = (int)1e2;
const int N = (int)5e5;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)1e9 + 7;
 
int n; ll k;
int a[M + 5];
int f[N + 5];
int y[M + 5];
int pre[M + 5];
int suf[M + 5];
int fac[M + 5];
int inv[M + 5];
int invfac[M + 5];
 
void init()
{
    fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
    for(int i = 2; i <= M; ++i)
    {
        fac[i] = 1ll * fac[i - 1] * i % mod;
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
        invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;
    }
}
 
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
 
int Lagrange(int n, ll k)
{
    if(k <= n + 1) return y[k];
    pre[0] = 1;    for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod;
    suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod;
    int ans = 0, cur;
    for(int i = 1; i <= n + 1; ++i)
    {
        cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod;
        if(n + 1 - i & 1) cur *= -1;
        cur = 1ll * cur * y[i] % mod;
        ans = (ans + cur) % mod;
    }
    ans = (ans % mod + mod) % mod;
    return ans;
}
 
void work()
{
    scanf("%d %lld", &n, &k);
    int lcm = 1;
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i];
    memset(f, 0, sizeof(f)); f[0] = 1;
    int r = lcm * n;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod;
    }
    for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i];
    printf("%d\n", Lagrange(n - 1, k / lcm + 1));
}
 
int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
    init();
    int T; scanf("%d", &T);
    for(int ca = 1; ca <= T; ++ca)
    {
//        printf("Case #%d:\n", ca);
        work();
    }
//    work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
    return 0;
}</syntaxhighlight>


== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] ==
== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] ==
Retrieved from "https://wiki.soullan.com/index.php/Special:MobileDiff/217...220"