首页
登录 | 注册

【取对数】【哈希】Petrozavodsk Winter Training Camp 2018 Day 1: Jagiellonian U Contest, Tuesday, January 30, 2018 Problem J. Bobby Tables

题意:给你一个大整数X的素因子分解形式,每个因子不超过m。问你能否找到两个数n,k,k<=n<=m,使得C(n,k)=X。

不妨取对数,把乘法转换成加法。枚举n,然后去找最大的k(<=n/2),使得ln(C(n,k))<=ln(X),然后用哈希去验证是否恰好等于ln(X)。

由于n和k有单调性,所以枚举其实是O(m)。

妈的这个哈希思想贼巧妙啊,因为对数使得精度爆炸,所以不妨同步弄个哈希值,来判相等。

opencup的标程:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include "bits/stdc++.h"
using namespace std;

using UInt = unsigned long long;
using Float = long double;

const int M = 150 * 1000;

Float LogSum[M+1];
UInt Hash[M+1];
UInt HashSum[M+1];

void Init(int m) {
  // LogF
  LogSum[0] = 0.;
  for (int i = 1; i <= m; ++i) {
    LogSum[i] = LogSum[i-1] + log((Float) i);
  }
  
  // Hash, HashF
  std::mt19937 gen;
  uniform_int_distribution<UInt> distr;
  vector<int> sieve(m+1, 0);
  for (int i = 2; i * i <= m; ++i) {
    if (sieve[i] == 0) {
      for (int j = i * i; j <= m; j += i) {
        sieve[j] = i;
      }
    }
  }
  Hash[0] = Hash[1] = 0; 
  for (int i = 2; i <= m; ++i) {
    if (sieve[i] == 0) {
      Hash[i] = distr(gen);
    } else {
      Hash[i] = Hash[i/sieve[i]] + Hash[sieve[i]];
    }
  }
  partial_sum(Hash, Hash + m + 1, HashSum);
}

Float LogBinom(int n, int k) {
  return LogSum[n] - LogSum[n-k] - LogSum[k];
}

UInt HashBinom(int n, int k) {
  return HashSum[n] - HashSum[n-k] - HashSum[k];
}

bool Solve(const vector<int>& factors, int m, int& n, int& k) {
  for (int p : factors) {if (p > m) { return false; }}
  Float log_x = 0;
  UInt hash_x = 0;
  for (int p : factors) { log_x += log((Float) p); hash_x += Hash[p]; }

  //check 
  int b = m;
  for (int a = 0; a <= m; ++a) {
    while (b > 0 && (a + b - 1 > m || LogBinom(a+b-1, a) >= log_x)) { --b; }
    if (b > 0 && HashBinom(a + b - 1, a) == hash_x) {
      n = a + b - 1;
      k = a;
      return true;
    }
    if (a + b <= m && HashBinom(a+b, a) == hash_x) {
      n = a + b;
      k = a;
      return true;
    }
  }
  return false;
}

int main() {
  Init(M);
  ios_base::sync_with_stdio(false);
  int z;
  cin >> z;
  while (z--) {
    int t;
    int m;
    cin >> t >> m;
    vector<int> factors(t);
    for (int i = 0; i < t; ++i) {
      cin >> factors[i];
    }

    //assert(t != 0);
    int n, k;
    if (Solve(factors, m, n, k)) {
      cout << "YES\n";
      cout << n << ' ' << k << '\n';
    } else {
      cout << "NO\n";
    }
  }
}

相关文章

  • PyCharm 2018 永久激活
    PyCharm是一种Python IDE,带有一整套可以帮助用户在使用Python语言开发时提高其效率的工具,比如调试.语法高亮.Project管理.代码跳转.智能提示.自动完成.单元测试.版本控制.此外,该IDE提供了一些高级功能,以用于 ...
  • TensorFlow之DNN(三):神经网络的正则化方法(Dropout、L2正则化、早停和数据增强)
    这一篇博客整理用TensorFlow实现神经网络正则化的内容. 深层神经网络往往具有数十万乃至数百万的参数,可以进行非常复杂的特征变换,具有强大的学习能力,因此容易在训练集上过拟合.缓解神经网络的过拟合问题,一般有两种思路,一种是用正则化方 ...
  • AI历史和哲学基础浅谈
    换个角度看AI:研究历史和哲学逻辑 正如题图所示,仿生人会梦见电子羊吗?(注:Do Androids Dream of Electric Sheep?是Philip K. Dick所著的一本科幻小说,讲述人类在一个崩坏的环境中复制自己并奴役 ...
  • ERP不规范,同事两行泪
    最近的很多次对外交流,都聊到了ERP建设的话题,并且无一例外的不那么让人省心,回想我这么多年走过的ERP坑坑路,在这里也写下经验和总结,希望能给正在或者即将走上ERP建设路的企业一些思考和帮助. 导读 1.几个瞎眼而普遍的案例 2.ERP的 ...
  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...

2020 cecdns.com webmaster#cecdns.com
12 q. 0.079 s.
京ICP备10005923号