51Nod-1259- 정수 분할 V2

1722 단어 활용단어참조dp

51Nod-1259- 정수 분할 V2


N을 몇 개의 정수의 합으로 나누면 몇 가지 다른 구분 방식이 있습니까? 예를 들어 n=4, {4} {1,3} {2,2} {1,1,2} {1,1,1,1}, 모두 5가지입니다.데이터가 비교적 크기 때문에 모드 10^9+7의 결과를 출력하면 된다.
Input
N(1 <= N <= 50000) 수를 입력합니다.
Output
출력 분할 수량 Mod 10^9 + 7.
Input 예
4
Output 예
5
블록 DP 복잡성 O (n*sqrt(n)
m = sqrt(n) 설정
우리는 우선 1~m의 모은 수를 사용하는 방안을 고려할 수 있는데, 완전히 배낭을 메면 된다
나머지 m+1~n에 대해 우리는 개수당 최대 m회까지 사용한 것을 발견했다. 그리고 g[i][j]는 i개수(m+1~m+i)와 j를 위한 방안의 수를 m++ g[i][j]=g[i-1][j-m]+g[i][j-i]로 표시했다.하나의 서열에 대해 우리는 두 가지 조작이 있다.기수 m 2 를 추가합니다.매 수마다 +1(여기 j는 정매거이기 때문에 매 수마다 1을 중복할 수 있음)

Code

#include
#define LL long long
#define RG register
using namespace std;

inline int gi() {
    int f = 1, s = 0;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') f = -1, c = getchar();
    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();
    return f == 1 ? s : -s;
}
const int N = 50010, Mod = 1e9+7;
int f[N], g[250][N], s[N];
int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
	int n = gi(), m = sqrt(n)+1;
	f[0] = 1;
	for (int i = 1; i < m; i++)
		for (int j = i; j <= n; j++)
			(f[j] += f[j-i]) %= Mod;
	int ans = 0;
	g[0][0] = 1;
	s[0] = 1;
	for (int i = 1; i < m; i++) {
		for (int j = m; j <= n; j++) {
			g[i][j] = (g[i-1][j-m] + g[i][j-i]) % Mod;
			s[j] = (s[j] + g[i][j]) % Mod;
		}
	}
	for (int i = 0; i <= n; i++)
		ans = (ans + (LL)f[i]*s[n-i]%Mod) % Mod;
	printf("%lld
", ans);
    return 0;
}
Ansible 실행 중: AWS에서 Ansible로 문제를 해결하는 방법
# ABC188 D - Snuke Prime

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage