QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#327748#1285. Stirling NumberNaCly_FishWA 884ms27860kbC++142.4kb2024-02-15 13:33:222024-02-15 13:33:23

Judging History

你现在查看的是最新测评结果

  • [2024-02-15 13:33:23]
  • 评测
  • 测评结果:WA
  • 用时:884ms
  • 内存:27860kb
  • [2024-02-15 13:33:22]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1000003
#define ll long long
using namespace std;

inline int power(int a,int t,const int& p){
    int res = 1;
    while(t){
        if(t&1) res = (ll)res*a%p;
        a = (ll)a*a%p;
        t >>= 1;
    }
    return res;
}

int findrt(const int& x){
    static int fac[N];
    int cnt = 0,m = x-1;
    for(int i=2;i*i<=m;++i){
        if(m%i!=0) continue;
        fac[++cnt] = i;
        while(m%i==0) m /= i;
    }
    if(m>1) fac[++cnt] = m;
    for(int i=2;i<=x;++i){
        bool flag = true;
        for(int j=1;j<=cnt;++j){
            if(power(i,(x-1)/fac[j],x)!=1) continue;
            flag = false;
            break;
        }
        if(flag) return i;
    }
    return -1;
}

int fac[N],ifac[N],pw[N],lg[N],inv[N];
int g;

void init(const int& p){
    pw[0] = inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for(int i=2;i<p;++i) fac[i] = (ll)fac[i-1]*i%p;
    ifac[p-1] = p-1;
    for(int i=p-2;i;--i) ifac[i] = (ll)ifac[i+1]*(i+1)%p;
    for(int i=2;i<p;++i) inv[i] = (ll)fac[i-1]*ifac[i]%p;
    for(int i=1;i<p-1;++i) pw[i] = (ll)pw[i-1]*g%p;
    for(int i=0;i<p-1;++i) lg[pw[i]] = i;

}

int binom(ll n,ll m,const int& p){
    if(n<m) return 0;
    if(n>=p) return (ll)binom(n/p,m/p,p)*binom(n%p,m%p,p)%p;
    return (ll)fac[n]*ifac[m]%p*ifac[n-m]%p;
}

int sum(int n,int m,const int& p){ // [x^m] of x^{\overline n}/(1-x)
    if(n==0) return 1;
    if(m>=n) return fac[n];
    static int f[N];
    for(int i=0;i<p-1;++i) f[i] = (ll)binom(pw[i]+n-1,n,p)*fac[n]%p;
    int res = (ll)f[0]*(m+1)%p,b = power(g,p-2,p);
    for(int j=1;j<p-1;++j)
        res = (res + (ll)f[j]*(1-power(b,(ll)j*(m+1)%(p-1),p))%p*power(1-power(b,j,p),p-2,p))%p;
    res = (ll)res*(p-1)%p;
    return res;
}

int solve(ll n,ll m,const int& p){
    ll L,q = n/p;
    int t,r = n%p;
    if(m<q) return 0;
    m -= q;
    t = m%(p-1),L = m/(p-1);
    //printf("q = %lld,t = %d,L = %lld\n",q,t,L);
    //printf("fac[%d] = %d\n",r,fac[r]);
    int res = ((ll)sum(r,t,p)*binom(q,L,p) - (ll)fac[r]*(L==0?0:binom(q-1,L-1,p)))%p;
    return ((q-L)&1)?-res:res;
}

ll n,l,r;
int p;

int main(){
    scanf("%lld%lld%lld%d",&n,&l,&r,&p);
    g = findrt(p);
    init(p);
    printf("%d",(solve(n,r,p)-solve(n,l-1,p)+p)%p);
    return 0;   
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 16036kb

input:

4 1 4 5

output:

4

result:

ok "4"

Test #2:

score: 0
Accepted
time: 3ms
memory: 16196kb

input:

6 5 5 29

output:

15

result:

ok "15"

Test #3:

score: 0
Accepted
time: 884ms
memory: 27860kb

input:

1000 685 975 999983

output:

482808

result:

ok "482808"

Test #4:

score: 0
Accepted
time: 0ms
memory: 14052kb

input:

8 7 8 7

output:

1

result:

ok "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 14128kb

input:

6 4 6 3

output:

2

result:

ok "2"

Test #6:

score: 0
Accepted
time: 2ms
memory: 13944kb

input:

31494923 16387579 27674098 2

output:

0

result:

ok "0"

Test #7:

score: 0
Accepted
time: 14ms
memory: 24604kb

input:

1000000000 179971578 813833436 383101

output:

53093

result:

ok "53093"

Test #8:

score: 0
Accepted
time: 265ms
memory: 25688kb

input:

1000000000 243662537 919841454 336437

output:

75332

result:

ok "75332"

Test #9:

score: -100
Wrong Answer
time: 31ms
memory: 26460kb

input:

1000000000 802415407 880806868 999983

output:

-39212

result:

wrong answer 1st words differ - expected: '960771', found: '-39212'