Submission #6007

#	Time	Username	Problem	Language	Result	Execution time	Memory
6007		model_code	없는 등수 찾기 (GA7_rank)	C++98	10 / 100	0 ms	2228 KiB

rank

#include<stdio.h>
#define mod 1000000007

typedef long long lld;

int n, m, r, a[270], b[270];
lld dy1[270][270], dy2[270][270], dap=1;

void countk(int k){
	int i, j;
	lld u1, u2, d;
	dy1[0][0]=dy2[0][0]=1;
	for(i=1; i<=n; i++){
		if(b[i]<k)d=b[i]-a[i]+1, u1=u2=0;
		else if(a[i]>k)u1=u2=b[i]-a[i]+1, d=0;
		else d=k-a[i], u1=b[i]-k+1, u2=b[i]-k;
		for(j=0; j<=i; j++){
			dy1[i][j] = u1*dy1[i-1][j], dy2[i][j] = u2*dy2[i-1][j];
			if(j)dy1[i][j] += d*dy1[i-1][j-1], dy2[i][j] += d*dy2[i-1][j-1];
			dy1[i][j] %= mod, dy2[i][j] %= mod;
		}
	}
	dap -= (dy1[n][r-1]-dy2[n][r-1]);
	dap %= mod;
	if(dap<0)dap += mod;
}

int main(){
	int i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=n; i++)scanf("%d%d", &a[i], &b[i]), dap=dap*(b[i]-a[i]+1)%mod;
	scanf("%d", &r);
	for(i=0; i<=m; i++)countk(i);
	printf("%lld", dap);
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40