某一个人 2024/2/18 0:15:12
好了吗？
某一个人 2024/2/18 0:15:20
商铭朗 2024/2/18 0:21:14
0
商铭朗 2024/2/18 0:21:16
现在写
你已开启消息免打扰，如需关闭，请在聊天设置中操作。
カタオモイ 2024/4/22 19:10:56
求助求助
カタオモイ 2024/4/22 19:11:06
生成函数有必要重点学嘛？
商铭朗 2024/4/22 19:11:13
啊
商铭朗 2024/4/22 19:11:19
（思考）
カタオモイ 2024/4/22 19:11:21
商铭朗 2024/4/22 19:11:23
水很深
商铭朗 2024/4/22 19:11:30
NOI 不考 FFT
カタオモイ 2024/4/22 19:11:42
我看有人说必学又有人说不考的
商铭朗 2024/4/22 19:11:45
我觉得可以作为兴趣了解，但是不建议专攻
カタオモイ 2024/4/22 19:12:01
行
商铭朗 2024/4/22 19:12:07
nayuta
我看有人说必学又有人说不考的
FFT 肯定考不了啦
商铭朗 2024/4/22 19:12:10
但是 GF 可以考
商铭朗 2024/4/22 19:12:21
一个典型的例子就是 [省选联考2020] 组合数问题
商铭朗 2024/4/22 19:12:32
唉唉这个也不是 GF
カタオモイ 2024/4/22 19:13:43
感觉很重要的样子但又感觉用不到
カタオモイ 2024/4/22 19:13:54
挺抽象的
カタオモイ 2024/4/22 19:13:59
(*/ω＼*)
商铭朗 2024/4/22 19:14:13
近四年省选都没考吧
商铭朗 2024/4/22 19:14:17
（几乎）
商铭朗 2024/4/22 19:14:39
最多就是考到 Lagrange 插值（比如省选联考 2024 重塑时光）
カタオモイ 2024/4/22 19:15:04
行
カタオモイ 2024/4/22 19:15:06
谢谢
商铭朗 2024/4/22 19:15:26
カタオモイ 2024/4/22 19:17:26
草
nayuta 2024/4/24 18:08:30
班上发的零食我放你桌上了
nayuta 2024/4/24 18:08:35
商铭朗 2024/4/24 19:02:24
谢谢
商铭朗 17:34:34
商铭朗 17:34:35
nayuta 17:39:06
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=3e5+5;
int n;
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx=0;
int a[Max];
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
int tot[Max];
struct node{
int num,to;
node()
{
num=to=0;
}
node(int numm,int too)
{
num=numm;
to=too;
}
};
node dp[Max][5];
bool cmp(node a,node b)
{
return a.num>b.num;
}
bool cmp2(int a,int b)
{
return a>b;
}
int x,y,w;
void dfs(int now,int from)
{
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
dfs(p[i].to,now);
dp[now][++tot[now]]=node(dp[p[i].to][1].num+a[now],dp[p[i].to][1].to);
sort(dp[now]+1,dp[now]+1+tot[now],cmp);
if(tot[now]>2)
tot[now]=2;
if(tot[now]==2)
{
if(dp[now][1].num+dp[now][2].num>w)
{
w=dp[now][1].num+dp[now][2].num;
x=dp[now][1].to;
y=dp[now][2].to;
}
}
}
if(tot[now]==0)
{
dp[now][1]=node(a[now],now);
tot[now]++;
}
}
int cnt,to[Max],len[Max][5],cl[Max];
bool dfs2(int now,int from)
{
bool yes=false;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
if(dfs2(p[i].to,now))
{
to[++cnt]=now;
yes=true;
}
else
{
len[now][++cl[now]]=dp[p[i].to][1].num;
sort(len[now]+1,len[now]+1+cl[now],cmp2);
if(cl[now]>2)cl[now]=2;
}
}
if(now==x)
{
to[++cnt]=now;
return true;
}
return yes;
}
int ans=0,am[Max];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,1);
dfs2(y,y);
int acn=0,sum;
for(int i=cnt;i>=1;i--)
{
acn+=a[to[i]];
am[i]=max(acn+len[to[i]][1],am[i+1]);
}
sum=acn;
acn=0;
for(int i=1;i<=cnt;i++)
{
acn+=a[to[i]];
ans=max(ans,acn+len[to[i]][1]+am[i+1]);
ans=max(ans,sum+len[to[i]][1]+len[to[i]][2]-a[to[i]]);
}
printf("%lld",ans);
}
nayuta 17:50:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=3e5+5;
int n;
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx=0;
int a[Max];
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
int tot[Max];
struct node{
int num,to;
node()
{
num=to=0;
}
node(int numm,int too)
{
num=numm;
to=too;
}
};
node dp[Max][5];
bool cmp(node a,node b)
{
return a.num>b.num;
}
bool cmp2(int a,int b)
{
return a>b;
}
int x,y,w;
void dfs(int now,int from)
{
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
dfs(p[i].to,now);
dp[now][++tot[now]]=node(dp[p[i].to][1].num+a[now],dp[p[i].to][1].to);
sort(dp[now]+1,dp[now]+1+tot[now],cmp);
if(tot[now]>2)
tot[now]=2;
if(dp[now][1].num>w)
{
w=dp[now][1].num;
x=dp[now][1].to;
y=now;
}
if(tot[now]==2)
{
if(dp[now][1].num+dp[now][2].num>w)
{
w=dp[now][1].num+dp[now][2].num;
x=dp[now][1].to;
y=dp[now][2].to;
}
}
}
if(tot[now]==0)
{
dp[now][1]=node(a[now],now);
tot[now]++;
}
}
int cnt,to[Max],len[Max][5],cl[Max];
bool dfs2(int now,int from)
{
bool yes=false;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
if(dfs2(p[i].to,now))
{
to[++cnt]=now;
yes=true;
}
else
{
len[now][++cl[now]]=dp[p[i].to][1].num;
sort(len[now]+1,len[now]+1+cl[now],cmp2);
if(cl[now]>2)cl[now]=2;
}
}
if(now==x)
{
to[++cnt]=now;
return true;
}
return yes;
}
int ans=0,am[Max];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,1);
dfs2(y,y);
int acn=0,sum;
for(int i=cnt;i>=1;i--)
{
acn+=a[to[i]];
am[i]=max(acn+len[to[i]][1],am[i+1]);
}
sum=acn;
acn=0;
for(int i=1;i<=cnt;i++)
{
acn+=a[to[i]];
ans=max(ans,acn+len[to[i]][1]+am[i+1]);
ans=max(ans,sum+len[to[i]][1]+len[to[i]][2]-a[to[i]]);
}
printf("%lld",ans);
}
nayuta 17:50:31
再交一发
nayuta 17:50:41
商铭朗 17:50:59
商铭朗 17:51:00
商铭朗 17:51:10
nayuta 17:52:13
nayuta 18:13:50
草好像知道为什么了
nayuta 18:13:54
我是傻逼
商铭朗 18:14:07
？
商铭朗 18:15:04
商铭朗 18:15:07
你觉得这句话对吗
商铭朗 18:15:08
m
nayuta 18:16:01
蛤？
nayuta 18:34:00
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=3e5+5;
int n;
struct edge{
int to,next;
}p[Max*2];
int head[Max],last[Max],idx=0;
int a[Max];
void add(int u,int v)
{
if(!head[u])
head[u]=++idx;
else
p[last[u]].next=++idx;
last[u]=idx;
p[idx].to=v;
}
int tot[Max];
struct node{
int num,to,dep;
node()
{
num=to=dep=0;
}
node(int numm,int too,int depp)
{
num=numm;
to=too;
dep=depp;
}
};
node dp[Max][5];
bool cmp(node a,node b)
{
return a.num>b.num;
}
bool cmp2(int a,int b)
{
return a>b;
}
int x,y,w;
void dfs(int now,int from)
{
dp[now][1]=node(a[now],now,now);
tot[now]++;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
dfs(p[i].to,now);
dp[now][++tot[now]]=node(dp[p[i].to][1].num+a[now],p[i].to,dp[p[i].to][1].to);
sort(dp[now]+1,dp[now]+1+tot[now],cmp);
if(tot[now]>2)
tot[now]=2;
if(dp[now][1].num>w)
{
w=dp[now][1].num;
x=dp[now][1].dep;
y=now;
}
if(tot[now]==2)
{
if(dp[now][1].num+dp[now][2].num>w)
{
w=dp[now][1].num+dp[now][2].num;
x=dp[now][1].dep;
y=dp[now][2].dep;
}
}
}
}
void dfs3(int now,int from)
{
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
if(dp[now][1].to==p[i].to)
{
if(dp[now][2].to)
dp[p[i].to][++tot[p[i].to]]=node(dp[now][2].num+a[p[i].to]+a[now],dp[now][2].to,0);
}
else
dp[p[i].to][++tot[p[i].to]]=node(dp[now][1].num+a[p[i].to]+a[now],dp[now][1].to,0);
sort(dp[now]+1,dp[now]+1+tot[now],cmp);
if(tot[now]>2)
tot[now]=2;
dfs3(p[i].to,now);
}
}
int cnt,to[Max],len[Max][5],cl[Max];
bool dfs2(int now,int from)
{
bool yes=false;
for(int i=head[now];p[i].to;i=p[i].next)
{
if(p[i].to==from)
continue;
if(dfs2(p[i].to,now))
{
to[++cnt]=now;
yes=true;
}
else
{
if(dp[p[i].to][1].to!=now)
len[now][++cl[now]]=dp[p[i].to][1].num;
else if(dp[p[i].to][2].to)
len[now][++cl[now]]=dp[p[i].to][2].num;
sort(len[now]+1,len[now]+1+cl[now],cmp2);
if(cl[now]>2)cl[now]=2;
}
}
if(now==x)
{
to[++cnt]=now;
return true;
}
return yes;
}
int ans=0,am[Max];
signed main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int u,v;
for(int i=1;i<n;i++)
{
scanf("%lld%lld",&u,&v);
add(u,v);
add(v,u);
}
dfs(1,1);
dfs3(1,1);
dfs2(y,y);
int acn=0,sum;
for(int i=cnt;i>=1;i--)
{
acn+=a[to[i]];
am[i]=max(acn+len[to[i]][1],am[i+1]);
}
sum=acn;
acn=0;
for(int i=1;i<=cnt;i++)
{
acn+=a[to[i]];
ans=max(ans,acn+len[to[i]][1]+am[i+1]);
ans=max(ans,sum+len[to[i]][1]+len[to[i]][2]-a[to[i]]);
}
printf("%lld",ans);
}
nayuta 18:34:03
淦
nayuta 18:34:06
最后一遍
nayuta 18:34:19
商铭朗 18:34:31
商铭朗 18:34:40
nayuta 18:34:53
a？
nayuta 18:52:46
nayuta 18:52:48
草
商铭朗 18:53:00
nayuta 18:53:04
布想玩啦
nayuta 18:53:08
商铭朗 19:07:12
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN=4e6+10, p=998244353, G=3;
int qpow(int a, int n) {
int res=1;
while (n) {
if (n&1) res=res*a%p;
a=a*a%p; n>>=1;
}
return res;
}
#define inv(x) qpow(x,p-2)
signed rev[MAXN];
using poly=vector<int>;
istream& operator>>(istream& is, poly& f) {
for (auto& i: f) cin>>i;
return is;
}
poly ntt(const poly& a, int n, int sgn=1) {
poly f=a; f.resize(n);
int bit=__lg(n);
for (int i=1; i<n; ++i)
rev[i]=(rev[i>>1]>>1) | ((i&1)<<(bit-1));
for (int i=1; i<n; ++i)
if (i<rev[i]) swap(f[i],f[rev[i]]);
for (int l=1, t=1; l<n; l<<=1, ++t) {
int step=qpow(G,p-1+((p-1)>>t)*sgn);
for (int j=0; j<n; j+=l<<1)
for (int k=j, cur=1; k<j+l; ++k, cur=cur*step%p) {
int g=f[k], h=cur*f[k+l]%p;
f[k]=(g+h)%p, f[k+l]=(p+g-h)%p;
}
}
if (sgn==-1) {
int invn=inv(n);
for (auto &i: f)
i=i*invn%p;
}
return f;
}
poly convolution(const poly& f, const poly& g) {
int n=f.size(), m=g.size(); int N=1ll<<(__lg(n+m+1)+1);
poly a=ntt(f,N), b=ntt(g,N);
for (int i=0; i<N; ++i) a[i]=a[i]*b[i]%p;
a=ntt(a,N,-1);
a.resize(n+m-1);
return a;
}
poly get_inv(const poly& f) {
assert(f[0]%p);
poly g(1); g[0]=inv(f[0]);
int deg=1; int n=f.size();
while (deg<n<<1) {
int N=deg<<1;
auto h=ntt(deg<=n?poly(f.begin(),f.begin()+deg):f,N); g=ntt(g,N);
for (int i=0; i<N; ++i)
g[i]=g[i]*(p+2-g[i]*h[i]%p)%p;
g=ntt(g,N,-1); g.resize(deg);
deg<<=1;
}
g.resize(n);
return g;
}
poly get_deriv(const poly& f) {
int n=f.size();
auto g=poly(n);
for (int i=0; i<n-1; ++i)
g[i]=(i+1)*f[i+1]%p;
return g;
}
poly get_integ(const poly& f) {
int n=f.size();
auto g=poly(n+1);
for (int i=0; i<n; ++i)
g[i+1]=f[i]*inv(i+1)%p;
g[0]=0;
return g;
}
poly get_ln(const poly& f) {
int n=f.size();
assert(f[0]==1);
auto g=get_deriv(f), h=get_inv(f);
g=convolution(g,h); g.resize(n);
g=get_integ(g); g.resize(n);
return g;
}
poly get_exp(const poly& f) {
int n=f.size(); assert(!f[0]);
int deg=1; poly g={1};
while (deg<n<<1) {
int N=deg<<1;
auto lng=get_ln(g);
for (int i=0; i<deg; ++i)
lng[i]=(p+f[i]-lng[i])%p;
lng[0]++;
lng=ntt(lng,N); g=ntt(g,N);
for (int i=0; i<N; ++i)
g[i]=g[i]*lng[i]%p;
g=ntt(g,N,-1);
deg<<=1; g.resize(deg);
}
g.resize(n);
return g;
}
poly qpow(poly a, int n, int deg) {
poly res(deg); res[0]=1;
while (n) {
if (n&1) res=convolution(res,a);
a=convolution(a,a);
res.resize(deg);
a.resize(deg);
n>>=1;
}
return res;
}
int n, m, a, b;
int fac[MAXN], ifac[MAXN];
poly get_f(int pr) {
poly f(m);
for (int i=0; i<m; ++i)
f[i]=(p-pr*ifac[i]%p)%p;
f[0]++;
poly g(m);
for (int i=0,pw=1; i<m; ++i) {
g[i]=pw*ifac[i]%p;
pw=pw*n%p;
}
f=qpow(get_inv(f),n+1,m);
f=convolution(f,g);
return f;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n>>m>>a>>b; m++; n--;
if (a==b) {
for (int i=0; i<=m; ++i) cout<<1<<'\n';
return 0;
}
fac[0]=ifac[0]=1;
for (int i=1; i<=1e5; ++i) fac[i]=fac[i-1]*i%p, ifac[i]=inv(fac[i]);
int pr=a*inv(b)%p, apr=(p+1-pr)%p;
auto g=get_f(apr); poly f(m);
for (int i=0; i<m; ++i) f[i]=ifac[i];
f=convolution(f,g);
int pw=qpow(pr,n+1);
for (auto &i: f) i=i*pw%p;
for (int i=0; i<m; ++i) {
cout<<f[i]*fac[i]%p<<'\n';
}
}