BZOJ3992:[SDOI2015]序列统计

2024-02-05 14:58

本文主要是介绍BZOJ3992:[SDOI2015]序列统计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

dpdp(i,j)ijC(k)Skdp(i+1,jk%m)=kdp(i,j)C(k)dpO(m2n)+m1(0)m1dpdp(i+1,(j+k)%(m1))=kdp(i,j)C(k)西FFT西线qwq西便qwq 这 个 题 大 概 裸 d p 这 样 : d p ( i , j ) 代 表 已 经 填 了 前 i 个 位 置 , 当 前 乘 积 为 j 的 方 案 数 C ( k ) 代 表 集 合 S 中 是 否 存 在 k d p ( i + 1 , j ∗ k % m ) = ∑ k d p ( i , j ) ∗ C ( k ) 然 后 这 个 d p 是 O ( m 2 n ) 的 , 也 没 啥 优 化 的 办 法 我 们 尝 试 将 ∗ 转 化 成 + 原 根 是 个 不 错 的 选 择 原 根 可 以 将 m − 1 个 不 同 的 数 字 ( 这 个 题 目 里 0 可 以 不 计 ) 对 应 到 m − 1 个 不 同 的 幂 上 所 以 我 们 对 应 了 之 后 , d p 方 程 就 改 变 了 : d p ( i + 1 , ( j + k ) % ( m − 1 ) ) = ∑ k d p ( i , j ) ∗ C ( k ) 然 后 这 东 西 大 家 就 很 熟 悉 了 吧 , F F T 呀 明 显 这 东 西 是 个 线 性 递 推 呀 然 后 就 直 接 多 项 式 快 速 幂 就 好 了 q w q 这 东 西 是 我 随 便 起 了 个 名 q w q 注 意 细 节 就 好 了

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define LL long long
using namespace std;
inline int read(){int x=0,f=1;char ch=' ';while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return x*f;
}
const int N=2e4+5,mod=1004535809,g=3,gi=334845270;
int n,m,x,S,G,vis[N],H[N],R[N],bin[1<<19];
LL C[N],ans[N];
inline LL ksm(LL a,LL n,int p=mod){LL ans=1LL;while(n){if(n&1)ans=ans*a%p;a=a*a%p;n>>=1;}return ans;
}
inline void init(){for(int i=1;i<m;++i){memset(vis,0,sizeof(vis));int flag=1;for(int j=1;j<m;++j){int tmp=ksm(i,j,m);if(vis[tmp]){flag=0;break;}vis[tmp]=1;}if(flag){G=i;break;}}for(int i=0;i<m;++i)H[ksm(G,i,m)]=i;for(int i=0;i<18;++i)bin[1<<i]=i;
}
inline void NTT(LL *a,int n,int f){int L=bin[n];for(int i=0;i<n;++i)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));for(int i=0;i<n;++i)if(i<R[i])swap(a[i],a[R[i]]);for(int i=1;i<n;i<<=1){LL wn=ksm(f==1?g:gi,(mod-1)/(i<<1));for(int j=0;j<n;j+=(i<<1)){LL w=1LL;for(int k=0;k<i;++k,w=w*wn%mod){LL x=a[j+k],y=w*a[j+k+i]%mod;a[j+k]=(x+y)%mod;a[j+k+i]=(x-y+mod)%mod;}}}if(f==-1)for(int i=0;i<n;++i)a[i]=a[i]*ksm(n,mod-2)%mod;
}
inline void poly_ksm(LL *a,LL *ans,int n,int b){for(int i=0;i<n;++i)ans[i]=a[i];b--;while(b){if(b&1){NTT(ans,n,1);NTT(a,n,1);for(int i=0;i<n;++i)ans[i]=ans[i]*a[i]%mod;NTT(ans,n,-1);NTT(a,n,-1);for(int i=m-1;i<n;++i)ans[i%(m-1)]=(ans[i%(m-1)]+ans[i])%mod;for(int i=m-1;i<n;++i)ans[i]=0;}NTT(a,n,1);for(int i=0;i<n;++i)a[i]=a[i]*a[i]%mod;NTT(a,n,-1);for(int i=m-1;i<n;++i)a[i%(m-1)]=(a[i%(m-1)]+a[i])%mod;for(int i=m-1;i<n;++i)a[i]=0;b>>=1;}
}
int main(){n=read();m=read();x=read();S=read();init();for(int i=1;i<=S;++i){int tmp=read();if(tmp)C[H[tmp]%(m-1)]=1;}int Len;for(Len=1;Len<(m<<1);Len<<=1);poly_ksm(C,ans,Len,n);printf("%lld",ans[H[x]%(m-1)]);return 0;
}

这篇关于BZOJ3992:[SDOI2015]序列统计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/681273

相关文章

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

opencv实现像素统计的示例代码

《opencv实现像素统计的示例代码》本文介绍了OpenCV中统计图像像素信息的常用方法和函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 统计像素值的基本信息2. 统计像素值的直方图3. 统计像素值的总和4. 统计非零像素的数量

如何使用 Bash 脚本中的time命令来统计命令执行时间(中英双语)

《如何使用Bash脚本中的time命令来统计命令执行时间(中英双语)》本文介绍了如何在Bash脚本中使用`time`命令来测量命令执行时间,包括`real`、`user`和`sys`三个时间指标,... 使用 Bash 脚本中的 time 命令来统计命令执行时间在日常的开发和运维过程中,性能监控和优化是不

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import