답안 #36239

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
36239 2017-12-06T12:36:07 Z Kerim 힘 센 거북 (IZhO11_turtle) C++14
5 / 100
1653 ms 772 KB
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int K=22,N=3e5+5;
PII arr[K];
int dis[K][K],dp[K][K],memo[K][K];
bool vis[N];
int prime[N],c,n,m,k,t,MOD;
int mod(ll x){
	while(x<0)	
		x+=MOD;
	return (x%MOD);	
}
int Fe(int x,int y){
	if(!y)
		return 1;
	int h=Fe(x,y/2);
	h=mod(h*1LL*h);
	if(y&1)
		h=mod(h*1LL*x);
	return h;	
}
int cnt(int x,int p){
	int res=0;
	for(int i=p;i<=x;i+=p)	
		res+=x/i;
	return res;	
}
int C(int x,int y){
	int ans=1;
	for(int i=0;prime[i]<=x and i<c;i++){
		int pw=cnt(x,prime[i])-cnt(y,prime[i])-cnt(x-y,prime[i]);
		ans=mod(ans*1LL*Fe(prime[i],pw));
	}
	return ans;
}
int way(int x,int y){
	return C(x+y-2,x-1);
}
int rec(int pos,int turn){
	if(pos==k+1)
		return 1;
	if(turn>t)
		return 0;
	int &ret=memo[pos][turn];
	if(~ret)
		return ret;ret=0;
	for(int i=pos+1;i<=k+1;i++)
		if(arr[i].ss>=arr[pos].ss)
			ret=mod(ret+mod(dp[pos][i]*1LL*rec(i,turn+1)));
	return ret;	
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
    for(int i=2;i<N;i++){
		if(vis[i])
			continue;
		for(int j=i;j<N;j+=i)
			vis[j]=1;
		prime[c++]=i;	
	}
    for(int i=1;i<=k;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		arr[i]=mp(x,y);
	}
	arr[0]=mp(0,0);
	arr[k+1]=mp(n,m);
	sort(arr,arr+k+2);
	for(int i=0;i<=k;i++)
		for(int j=i+1;j<=k+1;j++)
			if(arr[j].ss>=arr[i].ss)
				dis[i][j]=way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ss+1);
	for(int h=k+1;h>=1;h--)
		for(int i=h-1;i>=0;i--)
			if(arr[i].ss<=arr[h].ss){
				dp[i][h]=way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1);
				//~ printf("way(%d)(%d) = %d\n",i,h,way(arr[h].ff-arr[i].ff+1,arr[h].ss-arr[i].ss+1));
				for(int j=i+1;j<h;j++)
					if(arr[j].ss>=arr[i].ss and arr[h].ss>=arr[j].ss)
						dp[i][h]=mod(dp[i][h]-mod(dp[j][h]*1LL*way(arr[j].ff-arr[i].ff+1,arr[j].ss-arr[i].ff+1)));
			} 
	//~ for(int i=0;i<=k;i++)
		//~ for(int j=i+1;j<=k+1;j++)
			//~ printf("dp[%d][%d] = %d\n",i,j,dp[i][j]);	
	memset(memo,-1,sizeof memo);		
	printf("%d\n",rec(0,0));					
	return 0;
}

Compilation message

turtle.cpp: In function 'int rec(int, int)':
turtle.cpp:62:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if(~ret)
  ^~
turtle.cpp:63:14: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   return ret;ret=0;
              ^~~
turtle.cpp: In function 'int main()':
turtle.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&n,&m,&k,&t,&MOD);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 760 KB Output is correct
2 Incorrect 4 ms 760 KB Output isn't correct
3 Incorrect 8 ms 760 KB Output isn't correct
4 Incorrect 5 ms 764 KB Output isn't correct
5 Incorrect 28 ms 760 KB Output isn't correct
6 Incorrect 9 ms 764 KB Output isn't correct
7 Incorrect 10 ms 760 KB Output isn't correct
8 Incorrect 11 ms 764 KB Output isn't correct
9 Incorrect 51 ms 764 KB Output isn't correct
10 Incorrect 75 ms 772 KB Output isn't correct
11 Incorrect 397 ms 760 KB Output isn't correct
12 Incorrect 897 ms 760 KB Output isn't correct
13 Incorrect 370 ms 768 KB Output isn't correct
14 Incorrect 777 ms 760 KB Output isn't correct
15 Incorrect 668 ms 764 KB Output isn't correct
16 Incorrect 898 ms 760 KB Output isn't correct
17 Incorrect 768 ms 768 KB Output isn't correct
18 Incorrect 1653 ms 764 KB Output isn't correct
19 Incorrect 1466 ms 760 KB Output isn't correct
20 Incorrect 781 ms 764 KB Output isn't correct