问题 K: 运动会＜__int128＞_综合

时间限制: 1 Sec 内存限制: 128 MB

题目描述

在一次运会上，有一个比赛项目，共有N个人参加比赛，要将这N个人分组，每组人数不少于K个，问有多少种分组方式？
比如有16个运动员，每组人数不少于5个，共有6种分组方式：
(1) 分一组，为16人；
(2) 分二组，分别为11人、5人；
(3) 分二组，分别为10人、6人；
(4) 分二组，分别为9人、7人；
(5) 分二组，分别为8人、8人；
(6) 分三组，分别为6人、5人、5人。
注意：6+5+5，5+6+5，5+5+6为同一种，只算一种分组方式；

输入

输入共一行为两个整数N, K。表示有N个运动员分组，每组不少于K个人(1 ≤ K ≤ N ≤ 500)。

输出

输出共一行为一个整数，表示分组数。

样例输入 Copy

16 5

样例输出 Copy

int128大数

unsigned int : 0~4e9
int: -2e9~2e9
unsigned long: 0～4294967295

long: -2147483648～2147483647
__int64 / long long的最大值：-9e18~9e18

unsigned __int64 / unsigned long long的最大值：0~18e18

#include <bits/stdc++.h>
using namespace std;
typedef __int128 ll;
ll dp[505][505];
ll int128read()
{ll x=0;int flag=1;string a;cin>>a;for(char c:a){if(c=='-')flag=-1;else x=x*10+c-'0';}return flag*x;
}
void int128print(__int128 x)
{if(x<0){putchar('-');x=-x;}if(x>9)int128print(x/10);putchar(x%10+'0');
}
ll dfs(int n,int k)
{if(n<k)   return 0;if(n<2*k) return 1;if(dp[n][k]!=0) return dp[n][k];for(int i=k;i<=n;i++)dp[n][k]+=dfs(n-i,i);///递增，避免重复dp[n][k]++;///自己算一个return dp[n][k];
}
int main()
{ll n,k;scanf("%lld%lld",&n,&k);ll ans=dfs(n,k);int128print(ans);
}