QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#327748 | #1285. Stirling Number | NaCly_Fish | WA | 884ms | 27860kb | C++14 | 2.4kb | 2024-02-15 13:33:22 | 2024-02-15 13:33:23 |
Judging History
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'