今天是达哥出的题(翻车了QAQ)
T1
地精部落
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define rint register int
using namespace std;
const int N=4206;
int n,mod;
ll f[N][N];
ll dp()
{
if(n==1) return 1;
rint i,j; ll tt;
f[1][1]=1;
for(i=2;i<=n;++i)
{
tt=0;
for(j=i-1;j>=0;--j)
{
tt=(tt+f[i-1][i-j])%mod;
f[i][j]=tt;
}
}
ll an=0;
for(i=1;i<=n;++i)
an=(an+f[n][i])%mod;
return (an<<1)%mod;
}
int main(){
//freopen("rabbit.in","r",stdin);
//freopen("rabbit.out","w",stdout);
scanf("%d%d",&n,&mod);
printf("%lld",dp());
}
T2
考虑选了一个方格之后，会有对应的方格也必须跟它一样
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define rint register int
using namespace std;
inline void readchar(char &x)
{
char q=getchar();
while(q<'a'||q>'z') q=getchar();
x=q;
}
const int N=206;
int Q;
int n,m;
int con[31];
int work()
{
rint i,j;
int ff,tot2,tot4=(n>>1)*(m>>1);
if( (!(n&1)) && (!(m&1)) )
tot2=0;
else
if( (n&1) && (m&1) )
tot2=(n>>1)+(m>>1);
else
if( (n&1) && (!(m&1)) )
tot2=(m>>1);
else
tot2=(n>>1);
for(i=1;i<=tot4;++i)
{
ff=0;
for(j=0;j<26;++j)
if(con[j]>=4)
{
ff=1; con[j]-=4;
break;
}
if(!ff) return 0;
}
for(i=1;i<=tot2;++i)
{
ff=0;
for(j=0;j<26;++j)
if(con[j]>=2)
{
ff=1; con[j]-=2;
break;
}
if(!ff) return 0;
}
return 1;
}
int main(){
//freopen("T2.in","r",stdin);
//freopen("quilt.in","r",stdin);
//freopen("quilt.out","w",stdout);
rint i,j;
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&n,&m);
char tin;
mem(con,0);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
readchar(tin),++con[tin-'a'];
if(work())
printf("Yes
");
else
printf("No
");
}
}
T3
(1)我考试的思路
$f_{x}$ 在以x为根的子树里，从下面上来的蚊子的期望存活个数
$fs_{x}$ 在以x为根的子树里，从下面上来的蚊子的实际存活个数
$g_{x}$ 从x上面来的蚊子的期望存活个数
$gs_{x}$ 从x上面来的蚊子的期实际存活个数
转移就很简单了
$$ f_{x}=sum_{k|son(x)}f_{k}*(1-frac{p}{q}) $$
$$ans=sum_{x|leaf}gs_{x}-g_{x}$$
(2)周自神
$f_{x}$ 在以x为根的子树里，从下面上来的蚊子的期望存活个数
$fs_{x}$ 在以x为根的子树里，从下面上来的蚊子的实际存活个数
$fsum_{x} = sum_{k|x}f_{k} $
$$ans=sum_{x=1}^nsum_{son|x}f_{son}*(fsum_{x}-f_{son})*fs_{son} $$
其实本质一样啦
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define rint register int
using namespace std;
inline void read(int &x)
{
x=0; char q=getchar();
while(q<'0'||q>'9') q=getchar();
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
}
inline void readll(ll &x)
{
x=0; char q=getchar();
while(q<'0'||q>'9') q=getchar();
while(q>='0'&&q<='9') x=x*10+q-'0',q=getchar();
}
const int N=5000006;
const int mod=1000000007;
ll qpow(ll a,int ci)
{
ll an=1;
while(ci)
{
if(ci&1)
an=an*a%mod;
a=a*a%mod;
ci>>=1;
}
return an;
}
int first[N*2],nt[N*2],ver[N*2],e;
void addbian(int u,int v)
{
ver[e]=v;
nt[e]=first[u];
first[u]=e++;
}
int n,d;
ll p,q,at,unat;
ll xi[N],sh[N],xinum[N],shnum[N];
int size[N],fa[N],dep[N];
void dfs1(int x)
{
size[x]=1;
for(int i=first[x];i!=-1;i=nt[i])
{
if(ver[i]==fa[x])
continue;
fa[ver[i]]=x;
dep[ver[i]]=dep[x]+1;
dfs1(ver[i]);
size[x]+=size[ver[i]];
xinum[x]+=xinum[ver[i]];
if(dep[x]<=d)
xi[x]=(xi[x]+xi[ver[i]]*unat%mod)%mod;
else
xi[x]=(xi[x]+xi[ver[i]])%mod;
}
if(size[x]==1)
{
xinum[x]=1; xi[x]=1;
if(dep[x]<=d) xi[x]=unat;
}
}
void dfs2(int x)
{
for(int i=first[x];i!=-1;i=nt[i])
{
if(ver[i]==fa[x])
continue;
shnum[ver[i]]=shnum[x]+xinum[x]-xinum[ver[i]];
if(dep[x]<=d)
sh[ver[i]]=(sh[x]+(xi[x]-xi[ver[i]]*unat%mod+mod)%mod)%mod;
else
sh[ver[i]]=(sh[x]+(xi[x]-xi[ver[i]]+mod)%mod)%mod;
if(dep[ver[i]]<=d) sh[ver[i]]=sh[ver[i]]*unat%mod;
dfs2(ver[i]);
}
}
int main(){
//freopen("T3.in","r",stdin);
//freopen("T3.out","w",stdout);
//freopen("mosquito.in","r",stdin);
// freopen("mosquito.out","w",stdout);
rint i,j;
mem(first,-1);
read(n);
int tin1,tin2;
for(i=1;i<n;++i)
{
read(tin1); read(tin2);
addbian(tin1,tin2);
addbian(tin2,tin1);
}
read(d); readll(p); readll(q);
at=p*qpow(q,mod-2)%mod;
unat=(1LL-at+mod)%mod;
dfs1(1);
dfs2(1);
ll an=0;
for(i=1;i<=n;++i)
if(size[i]==1)
an=(an+(shnum[i]-sh[i]+mod)%mod)%mod;
cout<<an%mod;
}
达哥今天晚上要尴尬了...