uoj86 mx의 조합수(lucas정리+수위dp+원근과 지표+NTT)

uoj
제목 묘사

해제 시간

먼저 $p$가 이렇게 작은지 질수인지 보고 $lucas$의 정리를 가장 먼저 생각하세요.
$lucas $정리의 또 다른 쓰기 방법은 $p $진법으로 변환한 후 $C 를 계산하는 것입니다.{n}^{m} =\Pi C_{a_i}^{b_i} $
그래서 $l-1$와 $r$에 대해 각각 한 번씩 $dp$를 진행하는 것을 고려합니다.
$dp[i][j]$는 낮은 위치에서 $i$위치로 계산한 결과를 추출하면 $j$이고 합법적인 범위 내의 방안수를 보장합니다
$dg[i][j]$는 낮은 위치에서 $i$위치로 계산한 결과를 추출하면 $j$이고 합법적인 범위 내의 방안수임을 보장하지 않습니다
전환 방법:
계산된 대상 $i $
$n$이미 정해졌습니다. 즉, $bi$이(가) 이미 결정되었습니다.
그래서 $x$값을 이 자리에 매거하는 $ai $$k $, $C 설정{k}^{b_i}=g $
전환:
$ dg[i][jg mod p]+=dg[i-1][j] $
$ dp[i][jg mod p]+=dg[i-1][j](k
$ dp[i][jg mod p]+=dg[i-1][j](k=a_{i_{max}}) $
시간 복잡도 $p^{2}logn $.
이 폭력은 50점인 것 같다.
그리고 최적화를 고려한다.
~~ (이렇게 독종을 어떻게 생각해냈지)~~
상식의 $jg$는 최적화를 고려할 수 있습니다.
이때 독종의 수학 문제와 같이 우리는 p가 질수라는 것을 보았고 직접 지표로 그것을 낮추면 좋겠다...(뭐?)
아니면 위의 dp방정식을 고려하세요.
우리는 지금 i위로 매거하고 위의 첫 번째 이동식을 예로 들자.
$f[x]=\Sigma[C {k}^{b i}==x]$를 설정합니다.
그러면 전이식은 곱셈 볼륨 $dg^{'}[i]=\Sigma dg[j]*\Sigma f[g]* [jg mod p==i]$로 바뀝니다.
위 지표 이후 $dg^{'}[i]=\Sigma dg[j]*\Sigma f[g]* [(ln[j]+ln[g])mod\phi(p)===i]$
NTT에 올라가.
(markdown 공식 뭐야 빈칸도 안 나와)

#include
using namespace std;
typedef long long lint;
typedef __int128 llint;
templateinline void read(TP &tar)
{
    TP ret=0,f=1;char ch=getchar();
    while(ch'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=(TP)ret*10+ch-'0';ch=getchar();}
    tar=ret*f;
}
namespace LarjaIX
{
const int N=70011,maxn=65536,P=30011,B=150;
const int mo=998244353,G=3;
lint fpow(lint a1,lint p1,lint m1);
void ntt(lint *f1,int tp);
int p,phi,len=1,g;llint n,l,r;
int rev[N];
int bitn[B],bitm[B],maxbit;
int fac[P],inv[P],facinv[P];
int ln[P];
int c[B][P];
lint ans[P];
lint f1[N],f2[N],dp[N],dg[N],dt[N];
lint wg[N],iwg[N];
void work(llint lim)
{
    memset(dp,0,sizeof(dp));
    memset(dg,0,sizeof(dg));
    memset(bitn,0,sizeof(bitn));
    for(int i=1;lim;i++) bitn[i]=lim%p,lim/=p,maxbit=max(maxbit,i);
    dp[1]=dg[1]=1;
    for(int b=1;b<=maxbit;b++)
    {
        memset(f1,0,sizeof(f1)),memset(f2,0,sizeof(f2));
        for(int i=1;i
>1]>>1)|((len>>1)*(i&1));
    //-----------------------------------------------------------------------------------------------------
    //just get the g and ln of p
    {
        int tmp=phi;
        for(int i=2;i*i<=tmp;i++)if(tmp%i==0)
        {
            pri[++pri[0]]=i;
            while(tmp%i==0) tmp/=i;
        }
        if(tmp!=1) pri[++pri[0]]=tmp;
        for(int i=1;i
>=1;
    }
    return ret;
}
void ntt(lint *f1,int tp)
{
    for(int i=0;i