tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

今日解いた問題たち②

つづきです。Solvedがだんだん減っていきます。

84B - Magical Array
数えるだけ。オーバーフローした。

#include<stdio.h>
int a[100000];
int main(){
	int b;
	scanf("%d",&b);
	for(int i=0;i<b;i++)scanf("%d",a+i);
	long long ret=0;
	int val=a[0];
	long long re=1;
	for(int i=1;i<b;i++){
		if(val!=a[i]){
			ret+=re*(re+1)/2;
			val=a[i];
			re=1;
		}else re++;
	}
	ret+=re*(re+1)/2;
	printf("%I64d\n",ret);
}

288B - Polo the Penguin and Houses
埋め込む必要なさそうだけど埋め込んだ。b^(b-1)*(a-b)^(a-b)になるらしい。

#include<stdio.h>
#include<algorithm>
using namespace std;
int key[]={1,2,9,64,625,7776,117649,2097152};
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	long long ret=key[b-1];
	int mod=1000000007;
	for(int i=0;i<a-b;i++)ret=ret*(a-b)%mod;
	printf("%I64d\n",ret);
}

150B - Quantity of Strings
問題文が許されない。問題そのものもクソ。

#include<stdio.h>
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	int mod=1000000007;
	long long ret=1;
	if(c>a||c==1){
		for(int i=0;i<a;i++)ret=ret*b%mod;
	}else if(c==a){
		for(int i=0;i<(a+1)/2;i++)ret=ret*b%mod;
	}else if(c%2==1){
		ret=b*b;
	}else ret=b;
	printf("%d\n",ret);
}

294C - Shaass and Lights
コンビネーション掛け算ゲー。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[1000];
long long C[1001][1001];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<b;i++){
		scanf("%d",c+i);
	}
	std::sort(c,c+b);
	int mod=1000000007;
	C[0][0]=1;
	for(int i=0;i<1000;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;
		}
	long long ret=1;
	int n=a-b;
	for(int i=0;i<b-1;i++){
		ret=ret*C[n][c[i+1]-c[i]-1]%mod;
		n-=c[i+1]-c[i]-1;
		for(int j=0;j<c[i+1]-c[i]-2;j++)ret=ret*2%mod;
		
	}
	ret=ret*C[n][c[0]-1]%mod;
	printf("%I64d\n",ret);
}

204A - Little Elephant and Interval
こういう系の問題は難しすぎる。

#include<stdio.h>
#include<algorithm>
using namespace std;
long long calc(long long a){
	if(a<10LL)return a;
	if(a==10LL)return 9;
	long long t=1;
	long long ret=0;
	while(t<a){
		if(t==10)ret+=t/10*9;
		else ret+=t/100*9;
		t*=10;
	}
	t/=10;
	//printf("%lld %lld\n",ret,t);
	for(int i=1;i<=9;i++){
		if(t*i>a)break;
		if(t*(i+1)<a){
			if(t==1)ret++;
			else ret+=t/10;
		}else{
			if(a-i-t*i>=0LL)ret+=(a-i-t*i)/10+1;
		}
	}
	return ret;
}
int main(){
	long long a,b;
	scanf("%I64d%I64d",&a,&b);
	printf("%I64d\n",calc(b)-calc(a-1));
}

285D - Permutation Sum
OEISを使うときはちゃんとどれが該当するかをしっかり調べましょう。

#include<stdio.h>
int magic[]={1,0, 3,0, 15,0, 133,0, 2025,0, 37851,0, 1030367,0, 36362925,0, 1606008513,0};
int main(){
	int a;
	int mod=1000000007;
	scanf("%d",&a);
	long long ret=magic[a-1];
	for(int i=1;i<=a;i++){
		ret=ret*i%mod;
	}
	printf("%d\n",(int)ret);
}