蓝桥每日真题之整数分解

题目来源

2021年蓝桥省赛第二场D题

题目连接：http://acm.mangata.ltd/p/P1102

视频讲解

https://www.bilibili.com/video/BV11L4y1b7JQ/

思路 思路1

这个很容易想到直接使用五重循环去跑，但是这样估计是比赛结束前应该是跑不出来得

思路2

我们很轻松能想到一个优化那就是去掉一层，因为我们枚举四层后剩下的方案数就是余下的数，但是这也不够，我们再仔细想想会发现我们其实只用三层循环即可，因为剩下的可能数量就为余数减1，那么这样来看我们就能很轻松的解决这个问题

思路3

使用隔板法，我们将2021看作n个隔板，那么就会有2020个间隔，那么我们的目的不就是想将这一堆2021个板子分成5份吗，所以只需要挑选四个间隔点即可，那么答案总数就是 C 2020 4 C_{2020}^4 C20204​也就是691677274345

代码 思路2的代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair
ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
int n,a[N];

int main()
{
//	cout