题解 | 前缀平方和序列

import sys
from math import sqrt,comb
input=sys.stdin.readline
MOD=10**9+7
def solve():
    n,x=map(int,input().split())
    m=int(sqrt(x))
    while (m+1)*(m+1)<=x:
        m+=1
    print(comb(m,n)%MOD)

solve()

组合题

要在小于x的平方数中选择n个，并且正整数的前缀和递增，所以是组合问题，python可以直接使用comb

pypy3中要自己实现，这里为了方便顺手用的记忆化搜索

import sys
from math import sqrt
from functools import lru_cache
sys.setrecursionlimit(10**9)
input=sys.stdin.readline
MOD=10**9+7

@lru_cache(maxsize=None)
def inv(i):
    return pow(i, MOD-2, MOD)
 
@lru_cache(maxsize=None)
def fac(i):
    if i == 0:
        return 1
    if i == 1:
        return 1
    return fac(i-1)*i % MOD
 
 
@lru_cache(maxsize=None)
def C(n, m):
    if m > n or m < 0:
        return 0
    if n == 0 or n == m:
        return 1
    z = fac(n)
    m = fac(m)*fac(n-m)
    return z*inv(m) % MOD

def solve():
    n,x=map(int,input().split())
    m=int(sqrt(x))
    while (m+1)*(m+1)<=x:
        m+=1
    print(C(m,n))

solve()