TLX Practice Contest

2015年5月8日3,6476

被练习赛虐QAQ

快速冪脑补一下

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a,b,k1,k2;
ll qpow(ll a,ll b,ll p)
{
	ll ans=1;
	for(ll i=b;i;i>>=1,a=a*a%p) 
		if(i&1)ans=ans*a%p;
	return ans;
} 
int main()
{
	a=read();b=read();k1=read();k2=read(); 
	ll t=a*qpow(10,k1-1,b)%b;
	for(int i=1;i<=k2-k1+1;i++)
	{
		printf("%lld",t*10/b);
		t=t*10%b;
	}
	puts("");
	return 0;
}

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int a,b,k1,k2;

ll qpow(ll a,ll b,ll p)

{

ll ans=1;

for(ll i=b;i;i>>=1,a=a*a%p)

if(i&1)ans=ans*a%p;

return ans;

}

int main()

{

a=read();b=read();k1=read();k2=read();

ll t=a*qpow(10,k1-1,b)%b;

for(int i=1;i<=k2-k1+1;i++)

{

printf("%lld",t*10/b);

t=t*10%b;

}

puts("");

return 0;

}

把两种行分开

分别dp求前i行有j行两人都错

然后枚举两种行分别两人都错了i，j

用排列组合算一下贡献即可

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define mod 1000000007
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
int n,t1,t2,sam,dif;
char ch[2005],c[2005][15];
ll f[2005][2005],g[2005][2005],C[2005][2005];//same diff
int a[2005],b[2005],num[2005];
void pre()
{
	C[0][0]=1;
	for(int i=1;i<=2000;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=2000;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
	}
}
int main()
{
	pre();
	n=read();t1=read();t2=read();
	if(t1>n||t2>n){puts("-1");return 0;}
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch+1);
		a[i]=ch[1]-'a';
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch+1);
		b[i]=ch[1]-'a';
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%s",c[i]);
		if(c[i][a[i]]=='.'||c[i][b[i]]=='.'){puts("-1");return 0;}
		for(int j=0;j<5;j++)
			num[i]+=(c[i][j]!='.');
	}
	for(int i=1;i<=n;i++)
		if(a[i]==b[i])sam++;
		else dif++;
	f[0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<=i;j++)
		{
			(f[i+1][j]+=f[i][j])%=mod;
			if(a[i+1]==b[i+1])
				(f[i+1][j+1]+=f[i][j]*(num[i+1]-1)%mod+mod)%=mod;
		}
	g[0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<=i;j++)
		{
			(g[i+1][j]+=g[i][j])%=mod;
			if(a[i+1]!=b[i+1])
				(g[i+1][j+1]+=g[i][j]*(num[i+1]-2)%mod+mod)%=mod;
		}
	ll ans=0;
	for(int i=0;i<=sam;i++)
		for(int j=0;j<=dif;j++)
		{
			int q1=t1-(sam-i),q2=t2-(sam-i),tmp=dif-j;
			if(q1>=0&&q2>=0&&q1+q2==tmp)
			{
				ans+=f[n][i]*g[n][j]%mod*C[tmp][q1]%mod;
				ans%=mod;
			}
		}
	printf("%lld\n",ans);
	return 0;
}

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

#define mod 1000000007

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int n,t1,t2,sam,dif;

char ch[2005],c[2005][15];

ll f[2005][2005],g[2005][2005],C[2005][2005];//same diff

int a[2005],b[2005],num[2005];

void pre()

{

C[0][0]=1;

for(int i=1;i<=2000;i++)

{

C[i][0]=1;

for(int j=1;j<=2000;j++)

C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;

}

int main()

{

pre();

n=read();t1=read();t2=read();

if(t1>n||t2>n){puts("-1");return 0;}

for(int i=1;i<=n;i++)

{

scanf("%s",ch+1);

a[i]=ch[1]-'a';

}

for(int i=1;i<=n;i++)

{

scanf("%s",ch+1);

b[i]=ch[1]-'a';

}

for(int i=1;i<=n;i++)

{

scanf("%s",c[i]);

if(c[i][a[i]]=='.'||c[i][b[i]]=='.'){puts("-1");return 0;}

for(int j=0;j<5;j++)

num[i]+=(c[i][j]!='.');

}

for(int i=1;i<=n;i++)

if(a[i]==b[i])sam++;

else dif++;

f[0][0]=1;

for(int i=0;i<n;i++)

for(int j=0;j<=i;j++)

{

(f[i+1][j]+=f[i][j])%=mod;

if(a[i+1]==b[i+1])

(f[i+1][j+1]+=f[i][j]*(num[i+1]-1)%mod+mod)%=mod;

}

g[0][0]=1;

for(int i=0;i<n;i++)

for(int j=0;j<=i;j++)

{

(g[i+1][j]+=g[i][j])%=mod;

if(a[i+1]!=b[i+1])

(g[i+1][j+1]+=g[i][j]*(num[i+1]-2)%mod+mod)%=mod;

}

ll ans=0;

for(int i=0;i<=sam;i++)

for(int j=0;j<=dif;j++)

{

int q1=t1-(sam-i),q2=t2-(sam-i),tmp=dif-j;

if(q1>=0&&q2>=0&&q1+q2==tmp)

{

ans+=f[n][i]*g[n][j]%mod*C[tmp][q1]%mod;

ans%=mod;

}

printf("%lld\n",ans);

return 0;

}

二分+树形dp

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int n,m,K;
int f[100005],size[100005];
vector<int>a[100005];
bool cmp(int a,int b)
{
	return size[a]-f[a]<size[b]-f[b];
}
void dp(int x)
{
	size[x]=1;f[x]=0;
    for(int i=0;i<a[x].size();i++)
	{
		dp(a[x][i]);
		size[x]+=size[a[x][i]];
	}
	sort(a[x].begin(),a[x].end(),cmp);
	int t=0;
	for(;t+K<a[x].size();t++)
		f[x]+=size[a[x][t]];
	for(int i=t;i<a[x].size();i++)
		f[x]+=f[a[x][i]];
}
int main()
{
	n=read();m=read();
	for(int i=2;i<=n;i++)
	{
		int x=read();
		a[x].push_back(i);
	}
	int l=0,r=n,ans=0;
	while(l<=r)
	{
		K=(l+r)>>1;
		dp(1);
		if(n-f[1]<m)l=K+1;
		else ans=K,r=K-1;
	}
	printf("%d\n",ans);
	return 0;
}