1 Daniel__d

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 14w+

1024程序员节

1024程序员节快乐

2020-10-24 16:47:00

多项式指数函数(exp)

多项式指数函数(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-07-30 21:05:42

200209-省选模拟测试2

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

2020-02-09 20:24:12

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−xvi​1​那么将所有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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

多项式快速幂

多项式快速幂已知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

多项式对数函数(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

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。