Submission #105254

#	Time	Username	Problem	Language	Result	Execution time	Memory
105254		he_____he	Tents (JOI18_tents)	C++14	48 / 100	2032 ms	24440 KiB

tents

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int readint(){
	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;
}

const int cys=1000000007;
int n,m;
ll d[3005][3005];

int mod(int x){return x>=cys?x-cys:x;}

ll qpow(ll x,ll p){
	ll ret=1;
	for(;p;p>>=1,x=x*x%cys) if(p&1) ret=ret*x%cys;
	return ret;
}

int main(){
	n=readint(); m=readint();
	d[m][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){
			for(int k=0;k<=m-j;k++){
				if(j<m&&k) d[j][k]=mod(d[j][k]+d[j+1][k-1]*(j+1)%cys);
				if(k<m-j) d[j][k]=mod(d[j][k]+d[j][k+1]*(k+1)%cys);
				if(j+1<m) d[j][k]=mod(d[j][k]+d[j+2][k]*((j+2)*(j+1)/2)%cys);
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=m;i++) for(int j=0;j<=m-i;j++) ans=mod(ans+d[i][j]*qpow(4,j)%cys);
	printf("%lld\n",mod(ans+cys-1));
	return 0;
}

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:40:32: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
  printf("%lld\n",mod(ans+cys-1));
                  ~~~~~~~~~~~~~~^

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52