hdu 2512 1 캐릭터 대모 험(제2 류 스 털 링 수)
제목:n 개의 캐릭터 는 임의의 책 에 넣 을 수 있 습 니 다.모든 책 에 있 는 캐릭터 는 무질서 합 니 다.몇 가지 방법 이 있 는 지 물 어보 세 요.
사고방식:이미 알 고 있 는 첫 번 째 종류의 스 텔 링 수:
p 개의 물 체 를 k 개의 비 공 순환 으로 배열 하 는 방법 수.s(p,0)=0 ,p>=1 ;s(p,p)=1 ,p>=0。
전달 식:s(p,k)=(p-1)*s(p-1,k)+s(p-1,k-1),1<=k>=p-1
전달 식 의 해석:
만약 p-1 개의 물체 가 k 개의 순환 으로 배열 되 었 다 면,p 의 물 체 는 임의의(p-1)개의 물체 에 원소 의 왼쪽 을 삽입 할 수 있다.그러면 s(p,k)=(p-1)*s(p-1,k)의 방법 수가 있다.만약 p-1 개의 물체 가 k-1 개의 순환 으로 배열 된다 면,p 개의 물체 가 k 개의 순환 을 만족 시 키 려 면 반드시 하나의 순환 이 되 어야 한다.그러면 s(p,k)=s(p-1,k-1)의 방법 수가 있다.
두 번 째 유형 은 바로:
p 개의 물 체 를 k 개의 비공 식 집합 으로 배열 하 는 방법 수.s(p,0)=0 ,p>=1 ;s(p,p)=1 ,p>=0。
전달 식:s(p,k)=k*s(p-1,k)+s(p-1,k-1),1<=k>=p-1
전달 식 의 해석:
만약 p-1 개의 물체 가 k 개의 집합 으로 배열 되 었 다 면,p 개의 물 체 는 k 개의 집합 중의 임의의 하 나 를 넣 을 수 있다.그러면 s(p,k)=k*s(p-1,k)의 방법 수가 있다.만약 p-1 개의 물체 가 k-1 개의 집합 으로 배열 된다 면,p 개의 물체 가 k 개의 집합 을 만족 시 키 려 면 반드시 하나의 집합 이 되 어야 한다.그러면 s(p,k)=s(p-1,k-1)의 방법 수가 있다.
너무 tm 닮 았 어 요.하 나 는 링 이 고 하 나 는 집합 이에 요.
p 개 물 체 를 1-k 개 집합 에 넣 는 모든 방법 수 는 우리 의 모든 종류,즉 베 어 수 입 니 다.
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 2003;
const ll mod = 1000;
int S[N][N], B[N];
void init()
{
for(int i = 1; i < N; i++)
{
S[i][0] = 0;
S[i][i] = 1;
for(int j = 1; j < i; j++)
{
S[i][j] = (j*S[i-1][j]+S[i-1][j-1])%mod;
}
}
B[0] = 1;
for(int i = 1; i < N; i++)
{
B[i] = 0;
for(int j = 1; j <= i; j++)
B[i] = (B[i]+S[i][j])%mod;
}
}
int main()
{
// freopen("in.txt", "r", stdin);
int t, x;
init();
scanf("%d", &t);
while(t--)
{
scanf("%d", &x);
printf("%d
", B[x]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 2512 1 캐릭터 대모 험(제2 류 스 털 링 수)텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
