首页 > 其他分享 >「解题报告」ARC134E Modulo Nim

「解题报告」ARC134E Modulo Nim

时间:2023-03-12 10:55:58浏览次数:44  
标签:12 return Nim int bmod ARC134E add vector Modulo

真的不想写这题,感觉这种题出的很怪。

但是今天模拟赛出了,所以我还是写一下吧。

首先我们只关心当前所有数的集合,有多少我们不关心。设这个集合为 \(S\)。

观察样例,感觉可以猜测先手必败的情况很少,那么我们分类讨论一下。

  1. \(S = \{1\} / \{2\}\):显然先手必败;
  2. \(S\) 中存在奇数:那么先手可以选择一个 \(2\),此时 \(S = \{1\}\),那么先手必胜;
  3. \(S\) 中存在 \(a_i \bmod 4 = 2\):先手可以选择一个 \(4\),此时 \(S = \{2\}\),那么先手必胜;
  4. \(S\) 中同时存在 \(a_i \bmod 3 = 1\) 和 \(a_i \bmod 3 = 2\):首先这样的数在 \([1, 12]\) 内只有 \(4, 8\),分别对应 \(1\) 和 \(2\)。对于 \(S = \{4, 8\}\) 来说,先手必败。枚举所有情况可知。那么对于其它情况来说,先手选取一个 \(12\) 必定能够使 \(S = \{4, 8\}\),于是先手必胜;
  5. \(S\) 中只存在 \(a_i \bmod 3 = 1\) 或 只存在 \(a_i \bmod 3 = 2\)(可以有 \(a_i \bmod 3 = 0\)):先手选取 \(3\) 即可使得 \(S = \{1\} / \{2\}\),则先手必胜;
  6. \(S\) 中的所有数都是 \(12\) 的倍数:由于 \(a_i \le 200\),这样的数只有 \(\lfloor\frac{200}{12}\rfloor = 16\) 个,我们可以直接枚举每一种 \(S\) 暴力计算胜负情况。

那么我们发现这里面先手必败的情况只有:

  1. \(S = \{1\} / \{2\}\);
  2. \(S = \{4, 8\}\);
  3. \(S \subseteq \{12k \mid k \in \mathbf N_+\}\) 中的部分情况。

后两者可以通过状压 DP 求出方案数。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205, P = 998244353;
int n, a[MAXN];
bool f[1 << 16], g[1 << 16];
vector<int> mod(vector<int> s, int m) {
    vector<int> t;
    for (int i : s) if (i % m) {
        t.push_back(i % m);
    }
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    return t;
}
bool dfs(vector<int> S) {
    if (S.empty()) return true;
    if (S == vector<int>{ 1 }) return false;
    if (S == vector<int>{ 2 }) return false;
    if (S == vector<int>{ 4, 8 }) return false;
    for (int i : S) if (i % 12) {
        return true;
    }
    int T = 0;
    for (int i : S) T |= 1 << (i / 12 - 1);
    if (g[T]) return f[T];
    g[T] = 1;
    for (int i = 1; i <= S.back(); i++) {
        if (!dfs(mod(S, i))) {
            f[T] = 1;
            break;
        }
    }
    return f[T];
}
int h[MAXN][1 << 16];
void add(int &a, int b) {
    a += b;
    if (a >= P) a -= P;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    // precompute all boards
    f[0] = 1;
    for (int s = 0; s < (1 << 16); s++) {
        vector<int> S;
        for (int i = 0; i < 16; i++) if (s >> i & 1) {
            S.push_back((i + 1) * 12);
        }
        dfs(S);
    }
    // case 1: {1} or {2}
    int ans = 0, tot = 1;
    int mn = INT_MAX;
    for (int i = 1; i <= n; i++) mn = min(mn, a[i]);
    ans++;
    if (mn >= 2) ans++;
    // case 2: {4, 8}
    memset(h, 0, sizeof h);
    h[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 4; j++) if (h[i - 1][j]) {
            if (a[i] >= 4) add(h[i][j | 0b01], h[i - 1][j]);
            if (a[i] >= 8) add(h[i][j | 0b10], h[i - 1][j]);
        }
    }
    add(ans, h[n][0b11]);
    // case 3: { 12k }
    memset(h, 0, sizeof h);
    h[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int s = 0; s < (1 << 16); s++) if (h[i - 1][s]) {
            for (int j = 0; j < 16; j++) if (a[i] >= (j + 1) * 12) {
                add(h[i][s | (1 << j)], h[i - 1][s]);
            }
        }
    }
    for (int s = 0; s < (1 << 16); s++) if (!f[s]) {
        add(ans, h[n][s]);
    }
    for (int i = 1; i <= n; i++) {
        tot = 1ll * tot * a[i] % P;
    }
    ans = (tot - ans + P) % P;
    printf("%d\n", ans);
    return 0;
}

标签:12,return,Nim,int,bmod,ARC134E,add,vector,Modulo
From: https://www.cnblogs.com/apjifengc/p/17207755.html

相关文章

  • LayoutAnimationController,补间动画,属性动画,值动画,自定义动画,帧动画
    最好的代码永远是自己写出来的布局<?xmlversion="1.0"encoding="utf-8"?><LinearLayoutxmlns:android="http://schemas.android.com/apk/res/android"xmlns:tools......
  • 滚动到指定位置(requestAnimationFrame)
    1.运动的效果1//Tween运动算法2Mover.prototype.Tween={3/*44个參数5t:currenttime(当前时间)6b:beginningvalue(初始值......
  • Use MVC, Razor Pages, Blazor, API Controllers, And Minimal APIs In A Single ASP.
    博客原文地址:http://www.binaryintellect.net/articles/55355722-96b6-4bbc-a110-999e5e61235e.aspxAfewyearsagoI wroteanarticle explaininghowASP.NETCore......
  • Manim-空间与变换
    所有常量都可以在constants.py中找到屏幕空间屏幕中心为原点(0,0,0),遵循右手坐标系,向右为x轴正方向,向上为y轴正方向,向前为z轴负方向,旋转时正方向为顺时针方向。相关常量......
  • 209. Minimum Size Subarray Sum
    #题目Givenanarrayofnpositiveintegersandapositiveintegers,findtheminimallengthofacontiguoussubarrayofwhichthesum≥s.Ifthereisn’t......
  • 76. Minimum Window Substring
    76.MinimumWindowSubstring标签(空格分隔):leetcodehard题目GivenastringSandastringT,findtheminimumwindowinSwhichwillcontainallthec......
  • 使用requestAnimationFrame遍历图片实现动画效果
    关于MDN的描述参考https://developer.mozilla.org/zh-CN/docs/Web/API/window/requestAnimationFrame背景:ui提供了名称compress_00001一直到 compress_00039共40张......
  • nim游戏
    推荐阅读:\(nim\)\(SG\)\(OI-wiki\)公平组合游戏模板:P2197【模板】nim游戏点击查看代码#include<bits/stdc++.h>#definecsconst#defineriregisterusingna......
  • [ABC231E] Minimal payments
    [ABC231E]Minimalpayments-洛谷|计算机科学教育新生态(luogu.com.cn)题目关键信息,a[i]是a[i-1]的倍数,a[1]=1;举例一组数据:3129110100显然可以有,2*100找......
  • poj-1704 nim变形
    #include<stdio.h>#include<iostream>#include<math.h>#include<stdlib.h>#include<ctype.h>#include<algorithm>#include<vector>#include<string.h>#include<q......