Daniel__d-CSDN博客

多项式指数函数(exp)已知A(x)A(x)A(x)，求使得B(x)≡eA(x)(modxn)B(x)\equiv{e^{A(x)}}\pmod{x^n}B(x)≡eA(x)(modxn)的B(x)B(x)B(x)前置知识：牛顿迭代(咕咕咕)观察本题，由于B(x)≡eA(x)(modxn)ln⁡B(x)−A(x)≡0(modxn)令G(B(x))≡lnB(x)−A(x)(modxn)B(x)\equiv{e^{A(x)}}\pmod{x^n}\\\ln B(x)-A(x)\equiv0\pmod

2020-10-24 16:44:04 1417

原创 200209-省选模拟测试2

200209-省选模拟测试2T1 串题目描述题解AC自动机+DP代码实现T2 两个串题目描述题解FFT代码实现#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#define M 10...

2020-08-06 16:52:43 174

原创 P4389-EGF

P4389题目描述题解我们写出每一件商品的生成函数：Fi(x)=1+xvi+x2vi+...=11−xviF_i(x)=1+x^{v_i}+x^{2v_i}+...=\frac{1}{1-x^{v_i}}Fi(x)=1+xvi+x2vi+...=1−xvi1那么将所有F(x)F(x)F(x)乘起来就是答案的生成函数：G(x)=∏i=1m(11−xi)aiG(x)=\prod\limits_{i=1}^m(\frac{1}{1-x^i})^{a_i}G(x)=i=1∏m(1−

2020-08-06 08:41:16 180

原创 P4841-EGF

P4841题目描述题目描题解代码#include<bits/stdc++.h>#define ll long long using namespace std;const int g=3;const int mod=1004535809; const int M=2100009;char s;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getch

2020-08-05 21:25:25 239

原创 POJ3734-EGF

POJ3734题目描述题解代码#include <map>#include <set>#include <cmath>#include <queue>#include <cstdio>#include <vector>#include <climits>#include <cstring>#include <cstdlib>#include <io

2020-08-05 20:52:08 116

原创 200905-省选模拟9

省选模拟9T2-P4323题解树哈希+换根dp。异或的树哈希方式，本题不会被卡。代码#include<bits/stdc++.h>#include<tr1/unordered_map>#define LL unsigned long long #define M 200009using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch);ch=getcha

2020-08-05 20:37:25 143

原创 P4451-生成函数

P4451题目描述题解代码#include<bits/stdc++.h>#define int long longusing namespace std;const int mod=1e9+7; int ksm(int a,int b){ int ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; }return ans;}signed main(){ int re=0;

2020-08-04 22:36:35 153

原创 CF438E-生成函数

CF438E题目描述题解代码暴力O(n3)O(n^3)O(n3)#include<bits/stdc++.h>#define int long long#define M 1000009using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-'){f=-1,ch=getchar(

2020-08-04 21:50:24 179

原创 HDU2243-AC自动机+矩阵快速幂

HDU2243题目描述长度不超过LLL，只由小写字母组成的，至少包含一个词根的单词，一共可能有多少个呢？这里就不考虑单词是否有实际意义。题解先考虑直接dp转移，但是考虑到nnn的大小，显然会T掉。考虑矩阵乘法，ans=总方案数−不含词根的单词ans=总方案数-不含词根的单词ans=总方案数−不含词根的单词；首先前半部分是一个幂和的形式：An=261+...+26nSn=An+1=260+261+...+26nSn+1=26Sn+1A_n=26^1+...+26^n\\S_n=A_n+1=2

2020-08-04 21:15:12 197 1

原创 BZOJ3771-生成函数，容斥

BZOJ3771题目描述给出 nnn个物品，价值为别为XiXiXi且各不相同，现在可以取111个、222个或333个，问每种价值和有几种情况？顺序不同算一种题解代码#include <cmath>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <

2020-08-01 21:23:48 222

原创 BZOJ3513-FFT，组合数学

BZOJ3513题目描述题目大意：给定nnn个长度分别为aia_iai的木棒，问随机选择333个木棒能够拼成三角形的概率。题解代码#include <cmath>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#de

2020-08-01 21:16:16 254

原创 BZOJ3509-FFT，分块

BZOJ3509题目描述给定一个长度为NNN的数组A[]A[]A[]，求有多少对i,j,k（1<=i<j<k<=Ni, j, k（1<=i< j< k<=Ni,j,k（1<=i<j<k<=N满足A[k]−A[j]=A[j]−A[i]A[k]-A[j]=A[j]-A[i]A[k]−A[j]=A[j]−A[i]。题解代码O(n2logn)O(n^2logn)O(n2logn)#include<bits/stdc++.h&g

2020-08-01 21:08:18 288

原创 P4199-FFT，manacher

P4199题目描述题解代码#include<bits/stdc++.h>#define ll long long#define LL unsigned long long#define M 2000009using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-'){f=-1,ch

2020-08-01 20:51:29 113

原创 P4721-分治FFT，生成函数

P4721题目描述题解代码生成函数O(nlogn)O(nlogn)O(nlogn)分治FFTO(nlog2n)O(nlog^2n)O(nlog2n)#include<bits/stdc++.h>#define ll long long #define M 400009//要开4倍！ using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!

2020-08-01 20:24:38 212

原创 P4173 残缺的字符串（单模式字符串匹配FFT）

P4173题目描述题解代码#include<cmath>#include<cstdio>#include<climits>#include<cstring>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getcha

2020-07-31 21:36:23 165

原创 P3723 礼物（FFT）

P3723 礼物题目描述题解代码#include <cmath>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#define ll long longusing namespace std;const int M

2020-07-31 21:09:00 139

原创 P3338-力（FFT）

P3338 力题目描述题解代码#include <cmath>#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int M=4e5+9;const double p

2020-07-31 20:23:17 140

原创多项式快速幂

多项式快速幂已知A(x)A(x)A(x)，求使得B(x)≡A(x)k(modxn)B(x)\equiv{A(x)^k}\pmod{x^n}B(x)≡A(x)k(modxn)两边先取对数(换底公式)，再exp回来ln⁡B(x)≡kln⁡A(x)(modxn)B(x)=ekln⁡A(x)(modxn)\ln B(x)\equiv{k\ln A(x)}\pmod{x^n}\\B(x)=e^{k\ln A(x)}\pmod{x^n}lnB(x)≡klnA(x)(modxn)B(x)=eklnA(x)(m

2020-07-30 20:55:13 187

原创多项式对数函数(ln)

多项式对数函数(ln)已知A(x)A(x)A(x)，求使得B(x)=ln⁡A(x)B(x)=\ln A(x)B(x)=lnA(x)的B(x)B(x)B(x)考虑先求导，后积分B′(x)=A′(x)A(x)B(x)=∫A′(x)A(x)dxB'(x)=\frac{A'(x)}{A(x)}\\B(x)=\int\frac{A'(x)}{A(x)}dxB′(x)=A(x)A′(x)B(x)=∫A(x)A′(x)dx附上求导和积分的公式A′(x)=∑(i+1)aixi∫A(x)dx=∑ai−1i

2020-07-30 20:42:09 738

原创多项式开根

多项式开根已知A(x)A(x)A(x),求使得B(x)2≡A(x)(modxn)B(x)^2\equiv{A(x)\pmod{x^n}}B(x)2≡A(x)(modxn)的B(x)B(x)B(x)类似求逆，考虑倍增。假设当前已知B′(x)2≡A(x)(modxn2)B'(x)^2\equiv{A(x)}\pmod{x^{\frac{n}{2}}}B′(x)2≡A(x)(modx2n)(B′(x)2−A(x))2≡0(modxn)B′(x)4−2B′(x)2A(x)+A(x)2≡0(modxn)B′

2020-07-30 20:28:37 326 1

原创多项式除法

多项式除法(取模)已知次数为nnn的A(x)A(x)A(x),次数为mmm的B(x)B(x)B(x),求使得A(x)=B(x)C(x)+D(x)A(x)=B(x)C(x)+D(x)A(x)=B(x)C(x)+D(x)的C(x),D(x)C(x),D(x)C(x),D(x)由题C(x)C(x)C(x)的次数为n−mn-mn−m，D(x)D(x)D(x)的次数为m−1m-1m−1考虑将系数颠倒过来。记AR(x)=xnA(1x)A^R(x)=x^nA(\frac{1}{x})AR(x)=xnA(x1)

2020-07-30 20:12:30 567

原创多项式求逆

多项式求逆板子 P4238已知A(x)A(x)A(x)，求使得A(x)B(x)≡1(modxn)A(x)B(x)\equiv 1 \pmod{x^n}A(x)B(x)≡1(modxn)的B(x)B(x)B(x)考虑倍增。假设当前已得到B′(x)B'(x)B′(x)，满足A(x)B′(x)≡1(modxn)A(x)B'(x)\equiv 1 \pmod{x^n}A(x)B′(x)≡1(modxn)A(x)B′(x)−1≡0(modxn2)(A(x)B′(x)−1)2≡0(mod2n)A(x)2B′(

2020-07-30 19:52:53 132

原创多项式全家桶

#include<bits/stdc++.h>#define ll long long using namespace std;const int g=3;const int mod=998244353; const int M=2100009;char s;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-'){f=

2020-07-30 19:36:50 120

原创 POJ2778-AC自动机，矩阵快速幂优化DP

POJ2778题目描述简要题意：给出mmm个病毒串，问你由ATGCATGCATGC构成的长度为 nnn 且不包含这些病毒串的字符串有多少个?题解定义dp[i][j]=dp[当前长度为i][当前在AC自动机的第j个节点]=方案数dp[i][j]=dp[当前长度为i][当前在AC自动机的第j个节点]=方案数dp[i][j]=dp[当前长度为i][当前在AC自动机的第j个节点]=方案数.转移方程也十分简单.但是注意到nnn的大小，显然会T到飞起，考虑矩阵乘法优化，其实再转化一下题意就是：全图中的000

2020-07-30 13:47:32 171

原创 P2518-数位dp，哈希

P2518题目描述题解用has维护先前每个数的个数，然后直接套板子即可代码#include<bits/stdc++.h>#include<tr1/unordered_map>#define int long long#define ull unsigned long long#define M 100009using namespace std;tr1::unordered_map<ull,int>mp;const int h=31;int a

2020-07-27 21:59:36 156

原创 LOJ6109-可持久化无旋Treap

LOJ6109题目描述题解代码#include<bits/stdc++.h>#define LL long long#define M 30000009using namespace std;int read(){ int f=1,re=0; char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=g...

2020-07-27 21:18:18 147

原创 LOJ6100-主席树区间修改和查询，二进制，二分

LOJ6100题目描述题解该题大致思路便是：第一步求出每一个点最远能保持单调不下降到哪个点（记为nxt[i]nxt[i]nxt[i]）第二步主席树区间修改build(rt[i−1],rt[i],1,n,i,nxt[i])build(rt[i-1],rt[i],1,n,i,nxt[i])build(rt[i−1],rt[i],1,n,i,nxt[i]),区间查询build(rt[l−...

2020-07-27 21:05:06 254

原创 P4070-后缀数组，ST表

P4070题目描述题解代码#include<bits/stdc++.h>#define int long long#define M 200009using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-'){f=-1,ch=getchar();} for(;isdigit(ch);

2020-07-26 11:40:44 162

原创 P4248-后缀数组，单调栈

P4248题目描述题解代码#include<bits/stdc++.h>#define M 500009 #define int long longusing namespace std;int m,n,rk[M],tp[M],sa[M],tax[M],height[M],ans,q[M],num[M];char s[M];int getans(){ int l=1,r=0,cnt=n; for(int i=1;i<=n;i++) num[i]=(n-1)*i;

2020-07-26 11:32:07 134

原创 SP694-后缀数组

SP694题目描述题解代码#include<bits/stdc++.h>#define M 1000009#define int long longusing namespace std;int n,tax[M],height[M],rk[M],sa[M],tp[M],m;char s[M];void Qsort(){ for(int i=0;i<=m;i++) tax[i]=0; for(int i=1;i<=n;i++) tax[rk[i]]++; fo

2020-07-26 11:24:19 104

原创 HDU4758-AC自动机+状压dp

HDU4758题目描述题解代码#include<bits/stdc++.h>using namespace std;int f[105][105][305][4],tr[551][2],val[550],cnt,n,m,ans,fail[550],a[2],b[2],t;char s[150];const int mod=1000000007;void clear(){ cnt=ans=0; memset(tr,0,sizeof(tr)); memset(val,0,si

2020-07-26 11:14:11 118

原创 HDU3341-AC自动机+dp

HDU3341题目描述题解代码#include<bits/stdc++.h>//细节较多 using namespace std;int tr[505][5],val[505],fail[505],has[41][41][41][41],dp[505][15009],n,ans,tot,cnt,num[5],a[5];char s[50]; void clear(){ tot=cnt=ans=0; memset(tr,0,sizeof(tr)); memset(val,0,

2020-07-26 10:57:32 130

原创 HDU2825-AC自动机+状压dp

HDU2825题目描述题解代码#include<bits/stdc++.h>using namespace std;int dp[28][110][1<<10],tr[110][26],val[110],cnt,n,m,kk,ans,fail[110];char s[15];const int mod=20090717;void clear(){ cnt=ans=0; memset(tr,0,sizeof(tr)); memset(val,0,sizeof(v

2020-07-26 10:51:33 168

原创 P1962-矩阵快速幂板子

#include<bits/stdc++.h>#define int long longusing namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar()); if(ch=='-'){f=-1,ch=getchar();} for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re

2020-07-25 21:38:32 123

原创 200723-省选模拟4

省选模拟4T1题目描述题解O(n2)dpO(n^2)dpO(n2)dp方程很好写出来f[i]f[i]f[i]表示当前选到第iii个数的最大分数转移方程为：f[i]=max(f[i],f[j]+val[i])[i−t[i]>=j,i−t[j]>=j]f[i]=max(f[i],f[j]+val[i])[i-t[i]>=j,i-t[j]>=j]f[i]=max(f[i],f[j]+val[i])[i−t[i]>=j,i−t[j]>=j]考虑怎么优化考虑第二个条

2020-07-24 09:09:36 127

原创后缀数组板子

#include<bits/stdc++.h> using namespace std;const int MAXN=1000005;char ch[MAXN],All[MAXN];int SA[MAXN],rank[MAXN],Height[MAXN],tax[MAXN],tp[MAXN],a[MAXN],n,m; char str[MAXN];//rank[i] 第i个后缀的排名; SA[i] 排名为i的后缀位置; Height[i] 排名为i的后缀与排名为(i-1)的后缀的

2020-07-22 16:03:03 146

原创 AC自动机板子

#include<bits/stdc++.h>//P3808 #define M 1000007using namespace std;int trie[M][26],cnt,val[M],last[M],fail[M],n;char s[M];void build(){ int u=0; int len=strlen(s); for(int i=0;i<len;i++){//建立trie树 int c=s[i]-'a'; if(!trie[u][c]) trie

2020-07-22 10:39:33 120

原创 P1896-状压dp

P1896题目描述题解与普通的状压dp几乎相同，只是多了一维来存储选的个数初始化：f[0][1][0]=1f[0][1][0]=1f[0][1][0]=1代码#include<bits/stdc++.h>#define int long long#define M 100009using namespace std;int read(){ int f=1,re=0;char ch; for(ch=getchar();!isdigit(ch)&&ch!='

2020-07-21 11:00:50 123

原创 P2051-线性dp

P2051题目描述题解1.第iii行什么都不放。f[i][j][k]=f[i][j][k]+f[i−1][j][k]f[i][j][k]=f[i][j][k]+f[i-1][j][k]f[i][j][k]=f[i][j][k]+f[i−1][j][k]2.放1个在空的列。空的列是m−j−km-j-km−j−k。f[i][j][k]=f[i][j][k]+f[i−1][j−1][k]×(m−(j−1)−k)f[i][j][k]=f[i][j][k]+f[i−1][j−1][k]×(m−(j−1)

2020-07-21 10:57:24 120

空空如也

空空如也