今日解いた問題たち⑨

今日は実装が楽系多め。

9D - How many trees?
dp[i][j]:=i個のノードを持つ高さj以上の二分木の個数

#include<stdio.h>
#include<algorithm>
using namespace std;
long long dp[100][100];
long long calc(int a,int b){
	if(~dp[a][b])return dp[a][b];
	if(a<b)return dp[a][b]=0;
	if(a==0||a==1)return dp[a][b]=1;
	long long ret=0LL;
	for(int i=0;i<a;i++){
		ret+=-calc(i,b-1)*calc(a-i-1,b-1)+calc(i,b-1)*calc(a-i-1,0)+calc(i,0)*calc(a-i-1,b-1);
	}
	return dp[a][b]=ret;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			dp[i][j]=-1;
	printf("%I64d\n",calc(a,b));
}

232B - Table
各列の個数が周期nになっていないといけないことに考慮して、組み合わせの数を最初に繰り返し二乗法で求めてからDP.
これがDiv1Bなのか…

#include<stdio.h>
#include<algorithm>
using namespace std;
long long C[1000][1000];
long long dp[101][10001];
long long ad[100][101];
int main(){
	C[0][0]=1LL;
	int mod=1000000007;
	for(int i=0;i<999;i++)
		for(int j=0;j<=i;j++){
			C[i+1][j]=(C[i+1][j]+C[i][j])%mod;
			C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod;
		}
	int a,c;
	long long b;
	scanf("%d%I64d%d",&a,&b,&c);
	for(int i=0;i<a;i++){
		for(int j=0;j<=a;j++){
			long long v=C[a][j];
			long long s=1LL;
			long long t=(b-i-1)/a+1;
			while(t){
				if(t%2){
					s=s*v%mod;
				}
				v=v*v%mod;
				t/=2;
			}
			ad[i][j]=s;
		}
	}
	dp[0][0]=1LL;
	for(int i=0;i<a;i++){
		for(int j=0;j<=c;j++){
			if(!dp[i][j])continue;
			for(int k=0;k<=a&&j+k<=c;k++){
				dp[i+1][j+k]=(dp[i+1][j+k]+dp[i][j]*ad[i][k])%mod;
			}
		}
	}
	printf("%I64d\n",dp[a][c]);
}

341C - Iahub and Permutations
もう当該の位置の番号を持つ数が他の場所で使われている-1の個数とそうでない-1の個数を数えて包除原理。

#include<stdio.h>
long long C[3000][3000];
int c[2000];
int d[2000];
int main(){
	int a;
	scanf("%d",&a);
	int n=0;
	int m=0;
	for(int i=0;i<a;i++){
		scanf("%d",c+i);
		if(~c[i]){
			d[c[i]-1]=1;
		}else n++;
	}
	for(int i=0;i<a;i++){
		if(!d[i]&&c[i]==-1){
			m++;
		}
	}
	long long ret=0;
	int mod=1000000007;
	C[0][0]=1LL;
	for(int i=0;i<2001;i++)
		for(int j=0;j<=i;j++){
			C[i+1][j]=(C[i+1][j]+C[i][j])%mod;
			C[i+1][j+1]=(C[i+1][j+1]+C[i][j])%mod;
		}
	for(int i=0;i<=m;i++){
		long long val=C[m][i];
		for(int j=0;j<n-i;j++){
			val=val*(n-i-j)%mod;
		}
		if(i%2)ret=(ret+mod-val)%mod;
		else ret=(ret+val)%mod;
	}
	printf("%d\n",(int)ret);
}