石子の游戏：博弈论、dfs枚举

题意简述

输入 $N$ 和 $M$ 表示石子的数量和最多拿取的石子数，输出必胜方和可能出现的拿取方案。

赢家分析

这是一个经典的巴什博弈问题。根据其结论可得：

• 当 $N \bmod (M+1) = 0$ 时，先手必赢。
• 当 $N \bmod (M+1) \neq 0$ 时，后手必赢。

由于当先手必胜时，一定会出 $N\bmod (M+1)$，使得剩下的石子数量为 $M+1$ 的倍数。

if(n % (m + 1) == 0) cout << "second\n";
else{
  cout << "first\n";
  for(int i = 0;i < v.size();i++) cout << n % (m + 1) << " ";
  cout << "\n";
}

方案数分析

由于必输方可以随意拿取 $1$ 到 $M$ 个石子，所以影响方案数的因素是必输方的拿取方案。我们可以使用排列公式来解决，在排列时记录每种方式。

vector<vector<int>> v;
void dfs(int now,vector<int> path){
    if(now == N + 1){
        v.push_back(path);
        return;
    }
    for(int i = 1;i <= m;i++){
        path.push_back(i);
        dfs(now + 1,path);
        path.pop_back();
    }
}

每一方的拿取方案

由于必胜方需要让自己拿到石子数量与上一轮对方拿的石子数量之和为 $M+1$，所以若不计入先手必胜情况中的先手率先拿取的石子数量，轮数为：$N\div(M+1)$。

N = n / (m + 1);
for(int i = 0;i < N;i++){
  for(int j = 0;j < v.size();j++) cout << v[j][i] << " ";
  cout << "\n";
  for(int j = 0;j < v.size();j++) cout << m + 1 - v[j][i] << " ";
  cout << "\n";
}

正解

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,n,m;
vector<vector<int>> v;
void dfs(int now,vector<int> path){
    if(now == N + 1){
        v.push_back(path);
        return;
    }
    for(int i = 1;i <= m;i++){
        path.push_back(i);
        dfs(now + 1,path);
        path.pop_back();
    }
}
signed main(){
    cin >> n >> m;
    N = n / (m + 1);
    vector<int> path;
    dfs(1,path);
    if(n % (m + 1) == 0) cout << "second\n";
    else{
        cout << "first\n";
        for(int i = 0;i < v.size();i++) cout << n % (m + 1) << " ";
        cout << "\n";
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < v.size();j++) cout << v[j][i] << " ";
        cout << "\n";
        for(int j = 0;j < v.size();j++) cout << m + 1 - v[j][i] << " ";
        cout << "\n";
    }
    return 0;
}

时间复杂度：$O(M^{\frac{N}{M+1}})$
预计得分：$140pts$