Cómo encontrar el número de combinación grande (módulo) (algoritmo ACM)
El significado es relativamente simple. Consiste en m**** 0 y n 1 para formar una cadena numérica, pero el número de veces que 1 aparece de izquierda a derecha. La derecha no es menor que el número de veces que aparece 0.
Según el algoritmo de Daniel: el resultado es C(m+n, n)-C(m+n, m-1), y luego tomando el módulo, podemos simplificar la fórmula como:
(n+m)! *
(n-m+1) / ((m)!* (n+1)!)
Luego encuentra el módulo, pero como hay muchas combinaciones, usa grande La multiplicación y división de números expirará. Después de leer los informes de otras personas, me di cuenta de que puedes usar el método de simplificación de números primos para encontrar rápidamente el módulo, n = 2^p[i] *
3^. p[i] * 5^p [i]*...La remodelación puede ser rápida~(^=^)~.
#include
#include
#include
#include< string.h>
usando el espacio de nombres std;
#define M 2000005
#define mm 20100501
bool sig[M];
int prime[150000], p[150000], len; // prime registra el número primo, p registra la potencia del número primo len registra la longitud
void getprime( ) // Filtrar números primos
{
int i,j,k=0;
prime[k++] = 2;
for(i=3; i<=M; i+=2)
{
si( !sig[i] )
{<
primo[ k++] = i;
for(j=i; j<=M; j+=i)
sig[j] = 1;
}
}
}
void get(int k, int s) // ¡Descompone los números primos de K! , Suma y resta exponencial de S (denominador, numerador)
{
int i, mid;
for(i=0; prime[i]< =k && prime[i]; i++)
{
medio = k;
mientras(medio)
{
si(s)
p[i] += mid/prime[i]
else
p[i] -= mid/prime[i];
mid /= prime[i];
}
}
if(len < i )
len = i;
}
__int64 cal() // Resultado del cálculo (prime[i....] ^p [i...]) % mm
{
__int64 i,ans = 1;
for(i=0; i<=len; i++ )
{
si( p[i] )
{
__int64 t = primo[i], b = p[ i], ret = 1;
while(b) //calcular (t^b) % mm
{
if(b%2) ret *= t %mm;
t = t*t%mm;
b /= 2;
}
ans = ( ans*ret ) % mm;
}
}
return ans;
}
int main()
{
int t,m,n,i,mid;
__int64 ans;
getprime();
cin>>t;
mientras(t--)
{
cin>>n>>m;
len = 0;<