这次考试，我当时觉得自己状态不错，T1是一个很明显的树形DP，但是我退错了DP方程，这样例太水了竟然过了，所以我当时就没有检查，因为要用到求最大值并取模，所以我当时想了三种办法：1.高精度 2.取log 3.计算商和余数，其实前两种是可行的，但是我当时选了第三种，没仔细考虑这大小显然会爆炸，于是就死了。T2我觉得是一个找规律的题，但是没什么思路，打了个暴力还打假了，T3，T4都一样，暴力都没拿到分。期望得分：100+20+10+45，实际得分 0。
T1 卷
思路：这道题很显然是一个树形DP，设\(f_{i,0}\)表示以 i 为跟的子树中，不选 i 的最大乘积，\(f_{i,1}\) 表示选上 i ，我当时写的DP方程是：
\(f_{i,0}=max(f_{i,0},f_{son,1})\)
\(f_{i,1}=max(f_{i,1},f_{son,0}\times w_i)\)
这东西漏洞百出，实际上DP方程是这样的
\(f_{i,0}=f_{i,0}\times max(f_{son,1},f_{son,0})\)
\(f_{i,1}=f_{i,1}\times f_{son,0}\)
然后考虑求最大值并取模的问题，因为我上面说到的计算商和余数的方法不可行，于是可以使用前两种方法，听说高精度可以打模数进制高精加，就不用打高精模，但是我没有实践，我用的是取log,一种很套路的思想，遇到大数乘积比大小可以考虑对数，
\(log(a\times b)=log(a)+log(b)\),这样把乘法转化为加法，即可求出答案，开两个数组，一个比较大小，另一个存储真实乘积，代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int mo=1e9+7;
const int N=2e5+10;
const double eps=1e-6;
int n,tot;
int w[N],fa[N],size[N],deep[N];
int to[N<<1],head[N],next[N<<1];
long double dp[N][2],cun[N];
int f[N][2];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
iv dfs(int st,int f)
{
fa[st]=f;
deep[st]=deep[f]+1;
size[st]=1;
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==f) continue;
dfs(p,st);
size[st]+=size[p];
}
}
iv DFS(int st)
{
bool fl=0;
dp[st][0]=0;
dp[st][1]=cun[st];
f[st][0]=1;
f[st][1]=w[st];
for(re i=head[st];i;i=next[i])
{
int p=to[i];
if(p==fa[st]) continue;
DFS(p);
if(dp[p][0]-dp[p][1]>=eps)
{
dp[st][0]+=dp[p][0];
f[st][0]=(f[st][0]%mo)*(f[p][0]%mo)%mo;
}
else
{
dp[st][0]+=dp[p][1];
f[st][0]=(f[st][0]%mo)*(f[p][1]%mo)%mo;
}
dp[st][1]=dp[st][1]+dp[p][0];
f[st][1]=(f[st][1]%mo)*(f[p][0]%mo)%mo;
}
return;
}
signed main()
{
n=read();
for(re i=1;i<=n;i++)
w[i]=read();
for(re i=1;i<=n;i++)
cun[i]=log(w[i]);
int u,v;
for(re i=1;i<n;i++)
{
u=read();
v=read();
add(u,v);
add(v,u);
}
dfs(1,0);
DFS(1);
if(dp[1][0]-dp[1][1]>=eps)
printf("%lld\n",f[1][0]%mo);
else
printf("%lld\n",f[1][1]%mo);
return 0;
}
T2 简单题
思路：一道找规律题，把n个数拆成若干条链，每条链形如\(p,2\times p,...,2^k\times p\)
在这些链中，不难发现都是\(log\)级别的，显然我们是间隔选数，于是对于所有链长为偶数的链,必然是恰好一半给A,一半给B,并且总共恰好有两种分法,对答案直接贡献2 。对于链长为奇数的链,会多出来一个元素可能给A,也可能给B，所以最终答案区间一定在一个\([L,R]\)范围内。现在我们考虑如何计算贡献，我们发现，每条链都是以奇数数字开头的，我们需要算出
一个数组\(cnt_i\)表示长度为 i 的链的个数，\(l\)表示选数的最小个数，\(num\)表示长度为偶数的链的个数,\(tot\)表示长度为奇数的链的个数。
考虑\(cnt\)数组的求法，首先我们明确定义，以奇数开头的链长为 i 的链的个数，那么我们容易想到结果可能是\(f_i=n/(2^i+1)/2\),但是这样会算重，所以我们要算的应该是
\(p\times 2^k<=n ,p\times 2^{k+1}>n\),那么我们应该用\(cnt_i=f_i-f_{i+1}\),
现在考虑\(l\)的求法，发现不管长度为奇偶，最小选数都为\(cnt[i]/2\),最后统计答案即可。
代码如下：
AC_code
#include<bits/stdc++.h>
#define int long long
#define re register int
#define ii inline int
#define iv inline void
#define lc (rt<<1)
#define rc (rt<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int mo=10000019;
int n,m,q,tot,num,l;
int pre[mo],f[mo],cnt[mo],jc[mo+10];
ii read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
ii ksm(int d,int z)
{
int out=1;
while(z)
{
if(z&1)
out=out*d%mo;
z>>=1;
d=d%mo*d%mo;
}
return out;
}
ii suan(int n,int m)
{
if(m>n) return 0;
return jc[n]%mo*ksm(jc[n-m]%mo*(jc[m]%mo)%mo,mo-2)%mo;
}
ii C(int n,int m)
{
if(n==0 or m==0)
return 1;
if(m>n)
return 0;
return C(n/mo,m/mo)*suan(n%mo,m%mo)%mo;
}
signed main()
{
n=read();
q=read();
int k=log2(n);
pre[0]=1;
for(re i=1;i<=k;i++)
pre[i]=pre[i-1]*2;
for(re i=0;i<=k;i++)
f[i]=(n/pre[i]+1)/2;
for(re i=0;i<=k;i++)
cnt[i]=f[i]-f[i+1];
jc[0]=1;
for(re i=1;i<mo;i++)
jc[i]=jc[i-1]%mo*i%mo;
for(re i=0;i<=k;i++)
{
l+=(cnt[i]*((i+1)/2));
if(!(i&1))
tot+=cnt[i];
else
num+=cnt[i];
}
while(q--)
{
m=read();
if(m<l)
{
printf("0\n");
continue;
}
printf("%lld\n",C(tot,m-l)%mo*(ksm(2,num)%mo)%mo);
}
return 0;
}