UVA11806 - Cheerleaders (용 척 원리 + 이 진)
제목: m * n 의 직사각형 격자 에 k 개의 같은 돌 을 넣 고 몇 가지 방법 이 있 느 냐 고 물 었 다.각 칸 에 최대 한 개의 돌 을 넣 고 모든 돌 을 다 놓 아야 하 며 첫 번 째 줄, 마지막 줄, 첫 번 째 열, 마지막 열 에 모두 돌 이 있어 야 한다.
사고: 첫 번 째 줄 에 돌 이 없 는 방안 집 이 A 라 고 가정 하고 마지막 줄 에 돌 이 없 는 방안 집 은 B 이 며 첫 번 째 줄 에 돌 이 없 는 방안 집 은 C 이 고 마지막 열 에 돌 이 없 는 방안 집 은 D 이 며 전집 은 S 이다. 그러면 원 하 는 답 은 바로 'S 에서 A, B, C, D 의 그 어떠한 집합 에서 도' 의 요소 갯 수 이다. 여기 가 바로 용 척 원 리 를 활용 하 는 것 이다.프로그램 에 서 는 2 진법 으로 집합 을 표시 할 수 있다.
코드:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 510;
const int MOD = 1000007;
int C[MAXN][MAXN];
int n, m, k;
void init() {
memset(C, 0, sizeof(C));
C[0][0] = 1;
for (int i = 0; i < MAXN; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
int main() {
init();
int cas, t = 1;
scanf("%d", &cas);
while (cas--) {
scanf("%d%d%d", &n, &m, &k);
int sum = 0;
for (int S = 0; S < 16; S++) {
int b = 0, r = n, c = m;
for (int i = 0; i < 4; i++) {
if (S & (1 << i)) {
if (i % 2)
r--;
else
c--;
b++;
}
}
if (b & 1)
sum = (sum + MOD - C[r * c][k]) % MOD;
else
sum = (sum + C[r * c][k]) % MOD;
}
printf("Case %d: %d
", t++, sum);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
