当前位置: 首页 > news >正文

[SDOI2017]数字表格

又一道没有做出来的题

首先做最基础的mobius反演,可以得到,答案就是一堆fi^k乘起来,k是下面这个东西。

1545866-20190331232159659-1546978059.png

套路的用T代替id,并枚举T。

指数的式子变成 π(i|T) mu(T/i)✖(n/T)✖(m/T)

考虑先枚举指数再枚举i(没想到这一步!)

1545866-20190331232538857-770003238.png

令dp[T]=π (i|T) f[i]^mu(T/i)。

dp[T]可以在一个调和级数的复杂度内求出。

求出dp数组的前缀积,就可以除法分块sqrt(n)logn解决本题。

#include<bits/stdc++.h>
#define N 2200000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*flag;
}
const int mo=1e9+7;
bool is_prime[N];
int f[N],mu[N],prime[N];
void solve(int n)
{
    memset(is_prime,true,sizeof(is_prime));
    is_prime[0]=is_prime[1]=false;
    mu[0]=mu[1]=1;f[0]=0;f[1]=1;
    for(int i=2,cnt=0;i<=n;i++)
    {
        f[i]=(f[i-1]+f[i-2])%mo;
        if(is_prime[i])mu[i]=-1,prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            int k=i*prime[j];
            if(k>n)break;
            is_prime[k]=false;
            if(i%prime[j])mu[k]=-mu[i];else {mu[k]=0;break;}
        }
    }
}
int t,len,dp[N],pd[N];
int ksm(int x,int k)
{
    int ans=1;
    while(k)
    {
        if(k&1)ans=1ll*ans*x%mo;
        k>>=1;x=1ll*x*x%mo;
    }
    return ans;
}
void work()
{
    int n=read(),m=read(),ans=1;
    for(int l=1,r;l<=min(n,m);l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans=1ll*ans*ksm(1ll*dp[r]*pd[l-1]%mo,1ll*(n/l)*(m/l)%(mo-1))%mo;
    }
    printf("%d\n",(ans%mo+mo)%mo);
}
int main()
{
    t=read();len=1e6;solve(len);
    for(int i=0;i<=len;i++)dp[i]=pd[i]=1;
    for(int i=1;i<=len;i++)
    {
        int x=f[i],y=ksm(f[i],mo-2);
        for(int j=i;j<=len;j+=i)
        {
            if(mu[j/i]==+1)dp[j]=1ll*dp[j]*x%mo,pd[j]=1ll*pd[j]*y%mo;
            if(mu[j/i]==-1)dp[j]=1ll*dp[j]*y%mo,pd[j]=1ll*pd[j]*x%mo;
        }
    }
    for(int i=1;i<=len;i++)dp[i]=1ll*dp[i]*dp[i-1]%mo,pd[i]=1ll*pd[i]*pd[i-1]%mo;
    for(int i=1;i<=t;i++)work();
    return 0;
}

转载于:https://www.cnblogs.com/Creed-qwq/p/10633990.html

相关文章:

  • Sentinel Client: 整合Apollo规则持久化
  • 2019.4.1 事务和隔离级别
  • [LOJ 6213]「美团 CodeM 决赛」radar
  • 一、ABP框架框架摘要
  • Java-Runoob-高级教程-实例-字符串:02. Java 实例 - 查找字符串最后一次出现的位置...
  • “尝试加载 Oracle 客户端库时引发 BadImageFormatException。如果在安装 32 位 Oracle 客户端组件的情况下以 64 位模式运行,将出现此问题。”...
  • Http input plugin
  • elasticsearch+logstash+kibana部署
  • 物联网的概念
  • 漂亮数组 Beautiful Array
  • es6常用功能与异步详解(JS高级面试题)
  • python----__str__与__repr__的区别
  • OpenCV入门学习资料汇总
  • 性能测试必知必会
  • Typora + Mathpix Snip,相见恨晚的神器
  • 08.Android之View事件问题
  • ABAP的include关键字,Java的import, C的include和C4C ABSL 的import比较
  • Git初体验
  • Java 网络编程(2):UDP 的使用
  • Java编程基础24——递归练习
  • js学习笔记
  • Node项目之评分系统(二)- 数据库设计
  • overflow: hidden IE7无效
  • - 概述 - 《设计模式(极简c++版)》
  • 免费小说阅读小程序
  • 爬虫模拟登陆 SegmentFault
  • 如何正确配置 Ubuntu 14.04 服务器?
  • 体验javascript之美-第五课 匿名函数自执行和闭包是一回事儿吗?
  • 线性表及其算法(java实现)
  • 一些关于Rust在2019年的思考
  • 在 Chrome DevTools 中调试 JavaScript 入门
  • 主流的CSS水平和垂直居中技术大全
  • #pragma data_seg 共享数据区(转)
  • #基础#使用Jupyter进行Notebook的转换 .ipynb文件导出为.md文件
  • (02)Cartographer源码无死角解析-(03) 新数据运行与地图保存、加载地图启动仅定位模式
  • (1)Android开发优化---------UI优化
  • (1)安装hadoop之虚拟机准备(配置IP与主机名)
  • (6)STL算法之转换
  • (Forward) Music Player: From UI Proposal to Code
  • (非本人原创)我们工作到底是为了什么?​——HP大中华区总裁孙振耀退休感言(r4笔记第60天)...
  • (力扣记录)235. 二叉搜索树的最近公共祖先
  • (十三)Java springcloud B2B2C o2o多用户商城 springcloud架构 - SSO单点登录之OAuth2.0 根据token获取用户信息(4)...
  • (十一)c52学习之旅-动态数码管
  • (四)Controller接口控制器详解(三)
  • (原創) 系統分析和系統設計有什麼差別? (OO)
  • (转)EOS中账户、钱包和密钥的关系
  • .gitignore
  • .NET 8.0 发布到 IIS
  • .net 反编译_.net反编译的相关问题
  • .net 无限分类
  • .NET/C# 中设置当发生某个特定异常时进入断点(不借助 Visual Studio 的纯代码实现)
  • .NET4.0并行计算技术基础(1)
  • @Autowired多个相同类型bean装配问题
  • @entity 不限字节长度的类型_一文读懂Redis常见对象类型的底层数据结构
  • @for /l %i in (1,1,10) do md %i 批处理自动建立目录