Submission #60605080

---

Source Code Expand

// LUOGU_RID: 193663705
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int N = 1e5 + 5;
constexpr ll MOD = 1e9 + 7;

array<ll, N> f;
int n, m;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i <= m; i += n) f[i] = 1;
	auto ins = [&](ll x)
	{
		for (ll i = x; i <= m; i++)
		{
			f[i] += f[i - x];
			f[i] >= MOD ? f[i] -= MOD : 0;	
		}	
	};
	auto del = [&](ll x)
	{
		for (ll i = m; i >= x; i--)
		{
			f[i] = (f[i] - f[i - x] + MOD);
			f[i] >= MOD ? f[i] -= MOD : 0;
		}
	};
	auto query = [&](int x)->ll
	{
		return 1ll * x * (x + 1) / 2;
	};
	for (int i = 1; i < n; i++) ins(query(i));
	ll ans = 0ll;
	for (int i = 1; i <= n; i++)
	{
		ll tot = query(i - 1);
		if (tot <= m) ans += f[m - tot];
		ans >= MOD ? ans -= MOD : 0;
		if (i == n) break;
		// (i,n]
		del(query(n - i));
		// [1,i]
		ins(query(i));	
	}
	cout << ans << "\n"; 
	return 0;
}

Submission Info

Judge Result