期望得分：100+100+0=200
实际得分：
坐标的每一位不是0就是1，所以答案就是
C（n，k）
#include<cstdio>
#include<iostream> using namespace std; const int mod=1e9+; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int Pow(int a,int b)
{
int res=;
for(;b;a=1LL*a*a%mod,b>>=)
if(b&) res=1LL*res*a%mod;
return res;
} int main()
{
freopen("cube.in","r",stdin);
freopen("cube.out","w",stdout);
int n,k;
read(n); read(k);
int ans=;
for(int i=;i<=k;i++)
ans=1LL*ans*Pow(i,mod-)%mod*(n-i+)%mod;
cout<<ans;
}
货物一定是走在最大生成树上
如果按限重从大到小加边，那么一个联通块只需要有一个仓库
并查集维护即可
考场代码写的有点儿乱
#include<algorithm>
#include<iostream>
#include<cstdio> using namespace std; #define N 100001 int n,m; int fa[N];
bool cal[N]; int ans[N],tmp[N]; bool vis[N]; struct node
{
int u,v,lim;
bool use;
}e[N]; struct query
{
int id,w;
}a[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool cmp(node p,node q) { return p.lim>q.lim; } bool cmp2(query p,query q) { return p.w>q.w; } bool cmp3(node p,node q)
{
if(p.use!=q.use) return p.use>q.use;
return p.lim>q.lim;
} int find(int i) { return fa[i]==i ? i : fa[i]=find(fa[i]); } void MST()
{
for(int i=;i<=n;i++) fa[i]=i;
int tot=,i=,u,v;
while(tot!=n- && i<m)
{
i++;
u=find(e[i].u); v=find(e[i].v);
if(u==v) continue;
tot++; e[i].use=true;
fa[u]=v;
}
} int main()
{
freopen("warehouse.in","r",stdin);
freopen("warehouse.out","w",stdout);
int q;
read(n); read(m); read(q);
for(int i=;i<=m;i++) read(e[i].u),read(e[i].v),read(e[i].lim);
sort(e+,e+m+,cmp);
for(int i=;i<=q;i++) read(a[i].w),a[i].id=i;
sort(a+,a+q+,cmp2);
MST();
sort(e+,e+m+,cmp3);
for(int i=;i<=n;i++) fa[i]=i;
int ne=,nq=; int sum=n;
while(ne<=m)
{
if(!e[ne].use) break;
while(ne<=m && e[ne].lim>=a[nq].w)
{
if(find(e[ne].u)==find(e[ne].v))
{
ne++;
continue;
}
fa[find(e[ne].u)]=find(e[ne].v);
sum--;
ne++;
}
ans[a[nq].id]=sum;
nq++;
}
for(int i=nq;i<=q;i++) ans[a[i].id]=sum;
for(int i=;i<=q;i++) cout<<ans[i]<<'\n';
}
答案=原词典单词数+前缀后缀拼接单词数
统计前缀和后缀 拼接的单词：
一个基本错误思路：
如果有s1个长为l1 的前缀，有s2个长为l2的后缀，那么 他们对长为l1+l2 的单词的贡献为 s1*s2
错因：有可能会重复计数
例：
有单词 abc bcd
那么合法单词abcd 会计算3次：
a+bcd ab+cd abc+d
所以对于每个合法的单词，强行规定一个分离位置，来保证一个单词只会被计算一次
规定的分离位置：
若单词长为i的前缀是词典中单词的前缀，长为i+1的前缀不是词典中单词的前缀
那么i就是单词的分离位置
即这个单词是由前面长为i的前缀 和 i后面的后缀 拼接而成
在这个不会算重的思路的基础上
设f[i][j] 表示 原词典单词中 长度为i的前缀，再加1个字母j就不是前缀的 前缀数量
g[i][j] 表示 原词典单词中 长为i的后缀，第1个字母是j的 后缀数量
这两个数组在 正序和倒序 trie树上dfs即可解决
那么长为 i+k 的 前缀后缀 拼接单词数量 = Σ f[i][j]*g[k][j] j∈[0,26)
但思路仍然还有一个bug：
长为len 的 单词 的所有前缀 都是词典中单词的前缀
例：
词典中单词 cool o
那么 co 是一个长为2的合法单词
但是co按上述方法找不到分离位置
对于这种单词，我们强制规定 最后两个字母之间为分离位置
注意：这种单词还要满足 不是原词典中的单词，后缀非空 两个条件
所以 设t[i][j] 表示 长为i的前缀，最后一个字母是j 且 不是词典中单词的数量
注意这里不要把长为1的前缀统计进去
如果 g[1][j] 那么 长为i的合法单词 就可以累计 t[i][j]
#include<cstdio>
#include<cstring>
#include<algorithm> #define N 10001
#define L 51 using namespace std; const int mod=1e9+; char s[L]; int ans[]; int f[L][],g[L][],t[L][]; struct TRIE
{
int trie[N*L][],id; int endd[N*L]; void insert(int len)
{
int now=;
for(int i=;i<=len;i++)
{
if(!trie[now][s[i]-'a']) trie[now][s[i]-'a']=++id;
now=trie[now][s[i]-'a'];
}
endd[now]++;
} void dfs(int x,int dep)
{
for(int i=;i<;++i)
{
if(x && !trie[x][i]) f[dep][i]++;
if(x && trie[x][i] && !endd[trie[x][i]]) t[dep+][i]++;
if(trie[x][i]) dfs(trie[x][i],dep+);
}
} void dfs2(int x,int dep)
{
for(int i=;i<;++i)
if(trie[x][i]) g[dep+][i]++,dfs2(trie[x][i],dep+);
} }t1,t2; int main()
{
freopen("word.in","r",stdin);
freopen("word.out","w",stdout);
int n,q,len;
scanf("%d%d",&n,&q);
for(int i=;i<=n;i++)
{
scanf("%s",s+);
len=strlen(s+);
t1.insert(len);
reverse(s+,s+len+);
t2.insert(len);
ans[len]++;
}
t1.dfs(,);
t2.dfs2(,);
for(int i=;i<=;++i)
for(int j=;j<;++j)
if(g[][j]) ans[i]=(ans[i]+t[i][j])%mod;
for(int i=;i<=;++i)
for(int k=;k<=;++k)
for(int j=;j<;++j)
ans[i+k]=(1LL*ans[i+k]+f[i][j]*g[k][j]%mod)%mod;
int x;
while(q--)
{
scanf("%d",&x);
printf("%d\n",ans[x]);
}
}