首页 > 其他分享 >tran

tran

时间:2023-08-27 10:47:31浏览次数:26  
标签:对于 tran leq oplus True DP mathrm

[ABC317F] Nim

这个问题可以通过数位动态规划(DP)来解决。

我们考虑以下的数位DP来确定从二进制表示的最低位开始的下一位:

\(\mathrm{DP}[n][f_1][f_2][f_3][r_1][r_2][r_3]=\) 满足以下条件的整数组 \((x_1,x_2,x_3)\) 的个数:

  • 对于所有 \(i\),\(0 \leq x_i < 2^n\)
  • \(x_1\oplus x_2\oplus x_3=0\)
  • 对于每个 \(i\),"\(x_i\) 在 \(N\&(2^n-1)\) 以下"的真假为 \(f_i\)
  • 对于每个 \(i\),\(x_i\) 除以 \(A_i\) 的余数为 \(r_i\)

这里,\(\&\) 表示按位与运算。也就是说,\(N\&(2^n-1)\) 表示 \(N\) 的二进制表示的最低 \(n\) 位的值。

通过尝试每个 \(x_i\) 在二进制表示中从最低位开始的 \(n\) 位的值(共 \(2^3\) 种可能),我们可以从 \(\mathrm{DP}[n][*][*][*][*][*][*]\) 推导出 \(\mathrm{DP}[n+1][*][*][*][*][*][*]\)。

根据给定的约束条件 \(N < 2^{60}\),\(\mathrm{DP}[60][\mathrm{True}][\mathrm{True}][\mathrm{True}][0][0][0]\) 表示满足以下条件的整数组 \((x_1,x_2,x_3)\) 的个数:

  • 对于所有 \(i\),\(0 \leq x_i \leq N\)
  • \(x_1\oplus x_2\oplus x_3=0\)
  • 对于每个 \(i\),\(x_i\) 是 \(A_i\) 的倍数

所求答案是从第一个条件为 "对于所有 \(i\),\(1 \leq x_i \leq N\)" 的情况中减去得到的结果,即:

  • 对于某个 \(i\),\(x_i=0\)
  • \(x_1\oplus x_2\oplus x_3=0\)
  • 对于每个 \(i\),\(x_i\) 是 \(A_i\) 的倍数

这个可以很容易地计算出来。(分别令 \(x_1,x_2,x_3=0\),计算剩余二者的 \(\text{lcm}\),最后算出来,注意还有三者均为 \(0\))。

计算复杂度为 \(O(\log N \prod A_i)\)。

code

标签:对于,tran,leq,oplus,True,DP,mathrm
From: https://www.cnblogs.com/wscqwq/p/17659950.html

相关文章

  • 聊聊HuggingFace Transformer
    概述参见:聊聊HuggingFace项目组件一个完整的transformer模型主要包含三部分:Config、Tokenizer、Model。Config用于配置模型的名称、最终输出的样式、隐藏层宽度和深度、激活函数的类别等。示例:{"architectures":["BertForMaskedLM"],"attention_probs_dropo......
  • GPT之路(四) 神经网络架构Transformer工作原理
     原文:WhatAreTransformerModelsandHowDoTheyWork?Transformer模型是机器学习中最令人兴奋的新发展之一。它们在论文AttentionisAllYouNeed中被介绍。Transformer可以用于写故事、文章、诗歌,回答问题,翻译语言,与人类聊天,甚至可以通过对人类来说很难的考试!但是它们到底......
  • swin transformer
    摘要核心1.本文提出一种可以适用于多种任务的backbone->swintransformer2.Transformer迁移到CV中有两点挑战->物体尺度不一,图像分辨率大3.为了解决尺度不一的问题,SwinTransformer使用了分层的结构(Pyramid)4.为了能够在高分辨率上运行,SwinTransformer限制了attention的计算范围......
  • Windows11隐藏屏幕下方的白线:TranslucentTB软件
    问题引出:win11在设置中打开自动隐藏任务栏之后,有一条白线,看着很是烦人解决问题:使用Github开源项目Translucent隐藏这条白象1.可以在微软商店安装,如下图2.也可以点击链接到此页面下载TranslucentTB.appinstaller然后安装3.这个软件体积很小,占用的内存也很小,可以设置开机自动......
  • 使用 AutoGPTQ 和 transformers 让大语言模型更轻量化
    大语言模型在理解和生成人类水平的文字方面所展现出的非凡能力,正在许多领域带来应用上的革新。然而,在消费级硬件上训练和部署大语言模型的需求也变得越来越难以满足。......
  • Lock(锁)的使用 ReentrantLock
    Lock(锁)1.synchronized与Lock的对比Lock是显式锁(手动开启和关闭锁,别忘记关闭锁)synchronized是隐式锁,出了作用域自动释放。Lock只有代码块锁,synchronized有代码块锁和方法锁使用Lock锁,JVM将花费较少的时间来调度线程,性能更好。并且具有更好的扩展性(提供更多的子类)......
  • TransactionScope
     usingSystem.Transactions;using(TransactionScopescope=newTransactionScope(TransactionScopeOption.Required,newTransactionOptions{IsolationLevel=Syste......
  • transformer模型首次体验代码
    首先是安装python,更新pip源到清华源。安装transformerpipinstalltransformer安装jupyterlab,也简单一行pipinstalljupyterlab现在不想用anaconda了,因为国内没有源了,国外的又慢。直接用pip吧。然后开始体验之旅吧:打开终端,输入:jupyterlab会弹出一个web页面,代开后......
  • 使用 Transformers 优化文本转语音模型 Bark
    ......
  • Transformer计算公式
    LLMinferenceworkflowGenerativeInference.AtypicalLLMgenerativeinferencetaskconsistsoftwostages:i)theprefillstagewhichtakesapromptsequencetogeneratethekey-valuecache(KVcache)foreachtransformerlayeroftheLLM;andii)thed......