今日解いた問題たち⑧

解法を考えて整理してからPCを起動するとはかどる。

213B - Numbers
桁ごとに挿入するタイプの数え上げDP。leading 0を取り除くために最上位をループで決めています。

#include<stdio.h>
#include<algorithm>
using namespace std;
int d[10];
long long dp[10][101];
int C[1000][1000];
int main(){
	int a;
	int mod=1000000007;
	scanf("%d",&a);
	for(int i=0;i<10;i++){
		scanf("%d",d+i);
	}
	C[0][0]=1;
	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 ret=0;
	for(int i=1;i<10;i++){
		int e=d[i];
		d[i]=max(0,d[i]-1);
		for(int j=0;j<10;j++)
			for(int k=0;k<100;k++)
				dp[j][k]=0LL;
		for(int j=d[0];j<a;j++)
			dp[0][j]=1LL;
		for(int j=0;j<9;j++){
			for(int k=0;k<a;k++){
				if(!dp[j][k])continue;
				for(int l=d[j+1];k+l<a;l++){
					dp[j+1][k+l]=(dp[j+1][k+l]+dp[j][k]*C[k+l][l])%mod;
				}
			}
		}
		for(int j=0;j<a;j++)ret=(ret+dp[9][j])%mod;
		d[i]=e;
	}
	printf("%d\n",ret);
}

52B - Right Triangles
掛け算するだけ。

#include<stdio.h>
char str[1024][1024];
int R[1024];
int C[1024];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(str[i][j]=='*'){
				R[i]++;C[j]++;
			}
		}
	}
	long long ret=0;
	for(int i=0;i<a;i++)
		for(int j=0;j<b;j++)
			if(str[i][j]=='*')ret+=(R[i]-1)*(C[j]-1);
	printf("%I64d\n",ret);
}

223C - Partial Sums
各項にかかる係数がパスカルの三角形を斜めにしたようなもので与えられるので、コンビネーション計算を逆元を使う方針で求めて
足していくだけです。どうしてもこの逆元計算が覚えられない。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[2000];
long long inv[3000];
long long ter[2000];
long long ret[2000];
int main(){
	int mod=1000000007;
	inv[1]=1LL;
	for(int i=2;i<3000;i++){
		inv[i]=mod-inv[mod%i]*(mod/i)%mod;
	}
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%d",c+i);
	if(b==0){
		for(int i=0;i<a;i++){
			printf("%d",c[i]);
			if(i<a-1)printf(" ");
			else printf("\n");
		}
		return 0;
	}
	b--;
	for(int i=0;i<a;i++){
		ter[i]=1LL;
		for(int j=0;j<i;j++){
			ter[i]=ter[i]*(b+i-j)%mod;
			ter[i]=ter[i]*inv[j+1]%mod;
		}
	}
	for(int i=0;i<a;i++){
		for(int j=0;i+j<a;j++){
			ret[i+j]=(ret[i+j]+ter[j]*c[i])%mod;
		}
	}
	for(int i=0;i<a;i++){
		printf("%d",(int)(ret[i]));
		if(i<a-1)printf(" ");
		else printf("\n");
	}
}