Pinely Round 4

發表於 2024-07-28 更新於 2024-10-23 分類於 Codeforces ， Div1+2 Disqus：文章字數： 4.4k 所需閱讀時間 ≈ 15 分鐘

G(构造,贪心,状态机)H(博弈论,FFT)I()

https://codeforces.com/contest/1991

G Grid Reset

给定n,m,k

n * m 的白色矩阵

给定长度q的序列 H/V

如果H需要放入 1 * k的黑色横条

如果V需要放入 k * 1的黑色竖条

每次放入后，一行或一列全黑，则同时删除对应行或列（变回白色）

问有没有方法完成序列q,

如果有给出具体的方案，每次输出放置的左上角坐标

n,m 100, q 1000

256mb

我的思路

想完美的消除 a个横和 b个列，那么形状是类似

三川川川川
三
三
三
川

那么对于多行消除，需要 k个横和 m-k竖

那么对于多列消除，需要 k个竖和 n-k横

想的是画二维(横个数，竖个数) 的坐标图，找边界

其实可以切割成横(k,n-k,n),竖(k,m-k,m), 其中 n-k,m-k和k的大小关系不一定

然后这里其实是离线的，也就是我们可以知道最先达到哪个状态，但对于9宫格每个里面应该怎么摆，还没有具体的尝试

题解

hint1: 考虑行只在最左k列放，竖只在最上k行放, 和我想的方向是一样的

hint2: Prioritize operations that will lead to a reset.

k*k A.....
B
.
.

分成3部分，放置规则

横的B有空放B

竖的A有空放A

横的B放满了：
- 如果A中有满的列对应的行则放对应行进行消除，否则k * k中随便放一行

竖的A放满了：
- 如果B中有满的行对应的列则放对应列进行消除，否则k * k中随便放一列

首先如果 k=n=m, 那么随便放直接消除

如果k=n or k=m, 那么行列其中一个随便放直接消除，另一个负责k * k

所以下面讨论是 k < n 且 k < m

就这样放，那么我们[k*k,A,B]有初始状态

[空,有剩余,有剩余]

那么因为只要有剩余就不会放k * k, 所以下一个状态只可能是

[空,放满,有剩余] or [空,有剩余,放满]

因为行列对称，考虑[空,放满,有剩余] 往后

如果放行那么 [放了部分行未满,放满,有剩余]

如果放列那么 [空,放满,放满]

状态感觉乱起来了

根据对称性，考虑第二项是满的情况

那么对于 A/B 再定义更细的状态 未满(放置进度x[0,n-k)个), 已满(消除进度x[0~k)个)

k * k区域状态 空, 行[i~j], 列[i~j]

[空, 满(x), 未(x)] + 行 = [行[1~1], 满(x), 未(x)]

[空, 满(x),未(x)] + 列 = [空,满(x),未(x+1)] 如果这时列放满状态会是 [空,满(x),满(0)]

[行[a~b], 满(x), 未(x)] + 行 = [行[a~b+1], 满(x), 未(x)] (如果这时k * k 全放满则所有行消除 [空,未(0),未(x)] —–！！！！！！！！！！！！！

[行(a~b),满(x),未(x)] + 列 = [行(a~b),满(x),未(x+1)] 如果这时列放满状态会是 [空,满(x),满(b)]

[空, 满(x), 满(x)] + 行 = [空, 满(x), 满(x+1) 这里全消除则变成未(0)]

[空, 满(x), 满(x)] + 列 = [空, 满(x+1) 这里全消除则变成未(0), 满(x)]

看起来很美好

但还是有一个（上面很多惊叹号的！！！）需要仔细处理的情况

[空,未(0),未(0)] -> [空,未(0),满(0)] -> [+列(1-2),满(0),满(0)]=[空,满(2),满(0)] -> [+行,满(2),满(0)] = [空, 满(2), 未(0)] -> [+行, 满(2), 未(0)] = [列(1-2), 满(！！！！！！所以满的状态还需要2个元素), 未(0)] （这里有神奇的变化）

代码

https://codeforces.com/contest/1991/submission/276109968

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(int)(n);i++)
int read(){int r;scanf("%d",&r);return r;}

const int NOTF = 0; // NOTF,放置个数
const int ROW = 1;
const int COL = 2;
const int FULL = 3; // <FULL, 未消除start,end>, start,end 永远记录的是有东西的
using state = array<int,3>;
char op[1010];
int k;
array<int,2> calc(state &A,state &B,int n,state &kk,int row,int col){
  array<int,2> ret = {-1,-1};
  if(B[0] == NOTF) {
    ret = {(++B[1])+k,1};
    if(B[1] == n-k) {
      B={FULL,1,k};
      if(kk[0] == col) { // kk[1] ~ kk[2]
        if(kk[1] == 1) {
          B={FULL,kk[2]+1,k};
        }else{
          B={FULL,1,kk[1]-1};
        }
        kk={NOTF,0,0};
      }
    }
  }else{ // B[0] == FULL
    // 需要放kk
    if(A[0] == NOTF){
      if(kk[0] == NOTF) {
        ret = {1,1};
        kk = {row,1,1};
      }else{ // kk[0] == row
        ret = {kk[2] == k ? --kk[1]:++kk[2],1}; // 必定 一边是贴着边的, kk[1] = 1 or kk[2] = k
        if(kk[2] - kk[1] + 1 == k) {
          assert(B[1] == 1 or B[2] == k); // 必定贴边
          if(B[1] == 1 and B[2] == k){
            kk={NOTF,0,0};
          }else if(B[1] == 1){ // [B[1]..B[2]] [
            kk={col,B[2]+1,k};
          }else if(B[2] == k){
            kk={col,1,B[1]-1};
          }
          B={NOTF,0,0};
        }
      }
    }else{ // A[0] == FULL
      ret = {A[1]==1?A[2]--:A[1]++,1};
      if(A[1] > A[2]) A={NOTF,0,0};
    }
  }
  return ret;
}

void w(){
  int n=read();
  int m=read();
  k=read();
  int q=read();
  scanf("%s",op);
  if(n==m and n == k){
    rep(i,0,q) printf("1 1\n");
    return ;
  }else if(n==k) {
    int p = 0;
    rep(i,0,q) {
      if(op[i] == 'H'){
        printf("%d 1\n",++(p%=k));
      }else{
        printf("1 %d\n",k+1);
      }
    }
    return ;
  }else if(m==k) {
    int p = 0;
    rep(i,0,q) {
      if(op[i] == 'V'){
        printf("1 %d\n",++(p%=k));
      }else{
        printf("%d 1\n",k+1);
      }
    }
    return ;
  }else if(k==1){
    rep(i,0,q) printf("%d 1\n",(i%n)+1);
    return ;
  }
  // 2 <= k, k < n, k < m
  // kk A
  // B
  state kk = {NOTF,0,0}; // 左上角状态
  state A = {NOTF,0,0}; // A状态
  state B = {NOTF,0,0}; // B状态
  rep(i,0,q) {
    if(op[i] == 'H') {
      auto pos = calc(A,B,n,kk,ROW,COL);
      printf("%d %d\n",pos[0],pos[1]);
    }else{ // V
      auto pos = calc(B,A,m,kk,COL,ROW);
      printf("%d %d\n",pos[1],pos[0]);
    }
  }
}

int main(){
  int t = read();
  while(t--) w();
  return 0;
}

H Prime Split Game

A,B 玩游戏,n堆石头, 第i堆$a_i$个

A先B后，每次操作:

选$k\in[1,\frac{n}{2}]$
删除其中$k$堆
剩余的$n-k$堆中选$k$堆，把每个选中的都分割成2堆要求分割后的$2k$堆石头个数都是质数

无法移动的人输掉

n 2e5

ai 2e5

256mb

我的思路

首先如果一堆石头被选，要被分割，那么

<= 3不能被分割
=4的偶数，根据有限范围内的1+1=2定理，一定可以分割
奇数，那么只可能尝试 v-2, 2

因此奇数被切割的次数是唯一的，而偶数被切割的次数,取决于，首次的选择

所以 f(奇数) = 它的切割次数，那么“分割”操作其实变成选一些数，让它们的次数减1

f(偶数) = 1 + vector<pair<int,int>> ~= [f(),f()] 也就是可切割的方案对

而这个问题是n = 2e5 切割方案数感觉需要n^2? 才能找到所有吗？这个可以预计算吗，这个方案个数到底多还是少？

没啥想法

先不考虑偶数，或者激进一点，假设第一轮结束后只剩下奇数

那么如何最优策略

而例如1,2,3 这种不可拆分的数，虽然对于操作的第二步没有用，但是对于第一步还是很有用的，也就是

如果上一步是 [k个删除] [n-2k没动] [k个奇拆分]

因为总数还是 n, 所以可以拆分的在没动，和奇拆分出来的 v-2中

如果当前 2 * 只可拆分1次的数个数 >= 可拆分的数,

那么只需要令k = min(n/2,只可拆分1次的数个数), 然后就能胜利

所以其实如果看成剩余次数的数组 arr=[...]

那么其实选择 k个数变成0(原来也可以是0), 和选择k个大于0的数减去1, 操作后全0则胜利

所以 1的个数 >= 其它非0的个数？

质数-2链应该很短，因为对于大于5的末位是5一定不是， x7,x9,(x+1)1,(x+1)3,！？

而注意到 x7是质数 mod3 = 1 or 2

x9=x7+2 也是质数那么 x7 mod 3 = 2, x9 mod 3 = 1

那么(x+1)1 一定不是质数

所以长度会更短！？只能是1或者2？

题解

官方hint

Hint 1. 考虑奇数如何切分，偶数呢？这里我想到了奇数只能x-2,2

后来细想发现

这样一个数x mod 3 = 0 可能切割2次, x,x-2,x-4

这样一个数x mod 3 = 1 可能切割1次 x, x-2

这样一个数x mod 3 = 2 可能切割0次 x

那么一个偶数切割是不可行,或者 (0~~1,0~~1) 不多于4种方案，

因为如果切割出的是 mod 3那么只有3是质数，而3可切割0次，

Hint 2, 考虑简单版游戏：2堆石头，第一堆x个，第二堆1个. 判断所有必胜态

x是奇数 => (x,1)->(x-2,0)->(x-4,0), 所以判断它的最长质数链

-2 不是质数输
-2是质数，-4 不是质数赢
-2,-4是质数，-6 一定不是质数输

x是偶数 =>

x mod3 = 0,
- =6 => (0,0) 赢
- 6, 拆成 (mod 3 = 1(最多1次), mod 3 = 2(0次))
  - (0,0) 赢
  - (1,0)输
x mod3=1
- 3+(x-3)
  - (0,0)赢
  - (0,1)输
- (mod3=2,mod3=2)赢
x mod3=2
- 3+(x-3) = (0,0) 赢
- (mod3=1,mod3=1)
  - (0,0) 赢
  - (0,1) 输
  - (1,1) 输

换句说，要赢需要拆成两个不可再-2拆分的

Hint3 先计算奇数的结果，然后FFT计算出偶数的结果！！！！！

哦好有道理，但这个性质需要先观察出前面的只会是1,0

那么只需要建立 a[i] = int(bool(i是质数且无法拆分)), i 是奇数

那么对a[i]自身卷积aa=a*a

aa如果可行那么对应的值 [1,2e5], 如果不可行则是0

Hint 4,对于“大多数情况”可以根据输入的位置有多少是简化游戏中的获胜的状态，从而判断输赢

根据而上面的分析的结果还剩些什么

[0次奇败（2也属于这个），1次奇胜，2次奇败，0次偶败，1次偶胜，(0,1)偶败，(1,1)偶败]

奇数的话获胜态有1次，偶数的话切割了就是两个不可操作的奇数

n=奇如果 1次奇数和偶胜的个数>=一半。有一个不可操作的，那么必胜。

n=偶如果 1次奇数和偶胜的个数>=一半。那么必胜。

因为这两种都是只需要一次操作，对手就无法操作了

Hint5 对于hint4无法判断的，可以计算有多少ai能切割成两个胜利奇数来判断

感觉hint4 我的判断的都还不完全。找ai能切割一样fft就能搞

官方solution

奇x只能切割成x-2,2 ✅
4可以切割成2,2,其它的都是奇,奇 ✅
(x,1)，称为 lose/win position
1. 奇数与能-2的次数有关
2. 偶数
  1. 能切割成两个lose 则是win, 所以这里是 (lose+质数) 做卷积
  2. 用fft算
    1. 2014 ICPC SWERC Problem C
    2. https://archive.algo.is/icpc/swerc/2014/discussion.pdf
结论：
1. lose position: 不可切割或者切割中会产生一个win position !!!!!!!!!!!!!!!!!!!!!!!! 好有道理
2. win position: 能切割成2个 lose position
3. ！？这里连长度很短都还没有用???
如果所有位置都是losing position 那么后手胜利，因为不论先手如何操作，[A删][B拆][C不动]，那么 B拆就会有至少k个不多于 2k个win position,那么始终可以变化回全losing position
因此先手如果能把所有变成 losing position 那么就是先手胜利
1. 这样如果是偶数长度
  1. 1 <= win position <= n/2,那么k=win position个数
  2. win position > n/2, k= n/2
2. 如果是奇数长度
  1. 1 <= win position <= n/2 那么k=win position个数
  2. n > win position > n/2, k=n/2 因为至少一个bad position,而上面的操作可以覆盖完覆盖
  3. 全部都是 win position，那么无法一次全部变成 bad position
    1. 所以拆分后一定没有bad,如果一个win能拆成2个win，那么显然原来的是偶，拆后是奇（不可再拆成2个win）
    2. 如果所有win在一次操作后都会产生一个lose,那么先手输
    3. 如果有[1,n-1]个win在一次操作后会产生2个win, 那么选一些拆，选一些删除，让所有都是win,且所有win都不能拆成2个win
    4. 如果有n个都能拆成2个win,那么操作后要么有lose,要么全win,但是存在[1,n-1]个能拆成2个win, 所以是输
综上
1. 计算所有奇数的 win/lose
2. fft 计算所有偶数的win/lose
3. all lose => lose
4. len = 偶 => win
5. not all win => win
6. fft 计算所有偶可以拆 2win
7. [1,n-1] 个 2win win
8. 0 or n 个2win lose

代码

https://codeforces.com/contest/1991/submission/279951917

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for(ll i=(a);i<(ll)(n);i++)

ll read(){ll r;scanf("%lld",&r);return r;}

namespace CMM{
  const int _mod = 998244353;
  class modint{
    private:
      long long _v;
    public:
      modint() :_v(0) {  }
      modint(long long _a) {
        _v = (_a < 0)? _mod - ((-_a) % _mod) : (_a % _mod);
      }

      int val()const { return _v; }
      modint operator+()const { return *this; }
      modint operator-()const { return { _mod - _v }; }
      modint operator+(const modint& rhs) const { return modint(*this) += rhs; }
      modint operator-(const modint& rhs) const { return modint(*this) -= rhs; }
      modint operator*(const modint& rhs) const { return modint(*this) *= rhs; }
      modint operator/(const modint& rhs) const { return modint(*this) /= rhs; }

      bool operator==(const modint& rhs)const { return _v == rhs._v; }
      bool operator!=(const modint& rhs)const { return _v != rhs._v; }
      bool operator> (const modint& rhs)const { return _v >  rhs._v; }
      bool operator>=(const modint& rhs)const { return _v >= rhs._v; }
      bool operator<=(const modint& rhs)const { return _v <= rhs._v; }
      bool operator< (const modint& rhs)const { return _v <  rhs._v; }

      modint& operator+=(const modint& rhs) {
        (_v += rhs._v) %= _mod;
        return *this;
      }
      modint& operator-=(const modint& rhs) {
        (_v += _mod - rhs._v) %= _mod;
        return *this;
      }
      modint& operator*=(const modint& rhs) {
        _v = _v * rhs.val() % _mod;
        return *this;
      }
      modint& operator/=(const modint& rhs) { // 费马小定理
        _v = _v * rhs.inv().val() % _mod ;
        return *this;
      }
      modint pow(long long pwr) const {
        long long res(1);
        long long _b(_v);
        while (pwr) {
          if (pwr & 1) (res *= _b) %= _mod;
          (_b *= _b) %= _mod;
          pwr /= 2;
        }
        return res;
      }
      modint inv() const {
        assert(_v != 0);
        return pow(_mod - 2);
      }
  };

  namespace NTT{
    const int MAXPWR = 22; // 随着MOD改变, 2的幂次, 对应复平面单位向量的N = 2 && MAXPWR;
    const int g = 3;// 原根 随着MOD改变
    const int invg = 332748118;// 原根模逆元 随着MOD 和 g 改变

    // bit 翻转
    int rev(int x, int len) {
      int ans = 0;
      while(len -- ){
        ans <<= 1;
        ans |= x & 1;
        x >>= 1;
      }
      return ans;
    }

    inline int getlog2(int n){ return 31 - __builtin_clz(n);}

    template<class T>
      T mypow(T a, long long k) { //快速幂，a**k
        T res = 1;
        while (k) {
          if (k & 1) (res *= a); // modint %= MOD;
          (a *= a); // modint %= MOD;
          k >>= 1;
        }
        return res;
      }

    template<class mint>
      void NTT(std::vector<mint> &A, int flag = 1 /* 1: NTT, -1: INTT*/ ) {
        int n = A.size();
        if(n == 1) return ;
        // assert((n & (n-1)) == 0); // 2 的幂次
        int lgn = getlog2(n);
        // assert(lgn <= MAXPWR);
        for(int i=0;i<n;i++) { // 同FFT
          int j = rev(i, lgn);
          if (j > i) std::swap(A[i], A[j]);
        }
        for(int pwr=0;pwr<lgn;pwr++){
          int m = 1 << pwr;
          // assert((MOD - 1) % (m<<1) == 0);
          mint gn = mypow<mint>(flag == 1 ? g : invg, (MOD - 1) / (m << 1)); // 单位原根g_n
          for (int k = 0; k < n; k += (m<<1)) {
            mint gi = 1;
            for(int j=0;j<m;j++){
              mint U = A[k + j];
              mint T = A[k + j + m] * gi;
              A[k + j] = (U + T);
              A[k + j + m] = (U - T);
              gi *= gn;
            }
          }
        }
        if(flag == -1){ // 内置 / N
          const mint INVSIZE = mint(n).inv(); //  mypow(n, MOD-2);
          for(int i=0;i<n;i++) (A[i] *= INVSIZE) ; // modint %= MOD;
        }
      }

    template<class T>
      void INTT(std::vector<T> &A){ NTT<T>(A,-1);}

    // 卷积
    template<class T>
      std::vector<T> convolution(std::vector<T> v0, std::vector<T> v1){
        assert(v0.size() < (1<<MAXPWR));
        assert(v1.size() < (1<<MAXPWR));
        int sz = v0.size() + v1.size();
        if(sz == 0)return {};
        sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
        v0.resize(sz,0);
        v1.resize(sz,0);
        NTT<T>(v0);
        NTT<T>(v1);
        std::vector<T> v2(sz,0);
        for(int i=0;i<sz;i++) v2[i] = v0[i] * v1[i]; // modint % MOD;
        INTT<T>(v2);
        return v2;
      }

    // 平方 少一次 NTT
    template<class T>
      std::vector<T> poly_sq(std::vector<T> v0) {
        int sz = v0.size() * 2;
        if(sz == 0)return {};
        sz = 1 << (getlog2(sz) + !!(sz & (sz-1))); // 非2的幂次
        v0.resize(sz,0);
        NTT<T>(v0);
        std::vector<T> v2(sz,0);
        for(int i=0;i<sz;i++) v2[i] = v0[i] * v0[i]; // modint % MOD;
        INTT<T>(v2);
        return v2;
      }
  }
};

// ------------------------------------------------------------------------

using mint = CMM::modint;

int n;
const int N=200000;

bool prime[N+10];
int a[N+10];
int win[N+10];
int winwin[N+10]; // 偶win能拆成2win

void o(int idx){ printf("%s\n",idx==0?"Alice":"Bob"); }

void w(){
  n = read();
  rep(i,0,n) a[i]=read();
  int win_cnt = 0;
  rep(i,0,n) win_cnt+=win[a[i]];
  if(win_cnt == 0) return o(1); // all lose
  if(n%2==0) return o(0); // len 偶 win
  if(win_cnt != n) return o(0); // not all win => win
  int win2cnt = 0;
  rep(i,0,n) win2cnt+=winwin[a[i]];
  if(win2cnt== 0 or win2cnt== n) return o(1);
  return o(0);
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  rep(i,2,N+1) prime[i]=true;
  rep(i,2,N+1) if(prime[i]) for(ll j=i*i;j<=N;j+=i) prime[j]=false;

  for(int i=3;i<=N;i+=2) if(prime[i-2] and !win[i-2]) win[i]=true;
  {
    vector<mint> tmp(N+1,0);
    rep(i,2,N+1) if(prime[i] and !win[i]) tmp[i] = 1;
    auto res = CMM::NTT::convolution(tmp,tmp);
    for(int i=4;i<=N;i+=2) win[i] = (res[i] != 0);
  }
  {
    vector<mint> tmp(N+1,0);
    rep(i,2,N+1) if(prime[i] and win[i]) tmp[i] = 1;
    auto res = CMM::NTT::convolution(tmp,tmp);
    for(int i=4;i<=N;i+=2) winwin[i] = (res[i] != 0);
  }

  int t = read();
  while(t--) w();
  return 0;
}

总结

赛时做完f只有40min了，没想出G/H

G: 评分2700

不过其构造有难度 + 实现有难度是我觉得再练习两年半也不一定能当场做出来的，赛后在有答案情况下，编写+调试也是花了一些时间

H: 评分3300

想了半天才发现mod3带来的奇数长度性质，不过题解其实没有用到

而是通过的博弈论原理完成的，不过这个退化成(x,1)的问题是如何想到的？?????????

不过博弈论，我的思路有点太过于使用这个长度的，反而没用，而通过 [胜利状态]->[必定失败状态]->[总能胜利状态] 的反复才是博弈论的常见

然后第一次见到这种中间状态配合fft 来计算另一半的，虽然事后看很自然，但反过来想也是一种结果导向的反推方向