题解 P2054 【[AHOI2005]洗牌】

qqvq · 2018-11-16 14:51:47 · 题解

怎么有人特判AC，撤掉数据了

心累。。。第一眼看到原有题解就觉得不对劲，然后拍、改了好长时间

本篇题解之前的所有题解代码均不对

（我一个一个拖下来试的）

错误之处包括但不限于：

• 不开long long，全程int，读入1e10就gg了

• 乘法爆long long

• 复杂度不对（找循环节的）

• 某些情况下输出0

以及代码抄袭的那么明显真的好吗

暴力代码

//不存在n轮以后会变成初始状态的规律，可以用这个试一下

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100009
int a[MAXN], b[MAXN], n, m;
inline void refresh() {
  int *p1 = a + 1, *p2 = a + 1 + (n >> 1), *p = b + 1;
  for (int i = 1; i <= (n >> 1); ++i) *p++ = *p2++, *p++ = *p1++;
}

int main() {
  cin >> n >> m;
  for(int i = 1; i <= n; ++i) a[i] = i;
  for(int i = 1; i <= m; ++i) {
    refresh();
    for(int i = 1; i <= n; ++i) cout << b[i] << ' ';
    puts("");
    swap(a, b);
  }
  return 0;
}

正解代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x, y, a, b, n, m, l;

inline ll exgcd(ll a, ll b, ll &x, ll &y) {
  return !b ? (x = 1, y = 0, a) : (exgcd(b, a % b, y, x), y -= (a / b) * x);
}
inline ll mul(ll a, ll b, ll mod) {
  ll ret = 0;
  while (b) {
    if (b & 1) ret = (ret + a) % mod;
    a = (a + a) % mod;
    b >>= 1;
  }
  return ret % mod;
}
inline ll Pow(ll a, ll b, ll mod) {
  ll ret = 1;
  while (b) {
    if (b & 1) ret = mul(ret, a, mod);
    a = mul(a, a, mod);
    b >>= 1;
  }
  return ret % mod;
}

int main() {
  cin >> n >> m >> l;
  exgcd(2, n + 1, x, y);
  x = (x % (n + 1) + n + 1) % (n + 1);
  x = Pow(x, m, n + 1);//逆元是积性函数
  cout << mul(l, x, n + 1);
  return 0;
}