#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<long long> poly;
ll mod[100];
ll a[100];
ll N, K, M;
int ad[1<<21];
vector<ll> L, X, CT;
ll FAC[1<<20];
ll DB[7][1<<20], F[7][1<<20];
ll pw(ll a, ll b, ll mod)
{
ll ans = 1, mul = a;
while( b ) {
if( b & 1 ) ans = ans * mul % mod;
mul = mul * mul % mod, b /= 2;
}
return ans;
}
ll get_fact(ll N, ll mul, ll p)
{
if( F[ad[mul]][N] ) return F[ad[mul]][N];
if( N == 0 ) return 1;
ll q = N / mul, r = N % mul;
ll ans = 1, fac = 1;
ans = DB[ad[mul]][r];
fac = FAC[mul];
if( q == 0 ) return ans * get_fact(N/p, mul, p) % mul;
ans = pw(fac, q, mul) * ans % mul;
return F[ad[mul]][N] = ans * get_fact(N / p, mul, p) % mul;
}
ll gcd(ll a, ll b){
return b == 0 ? a : gcd(b, a%b);
}
pii extended_gcd(ll a, ll b){
if( b == 0 ) return pii(1, 0);
pii t = extended_gcd(b, a%b);
return pii( t.second, t.first - t.second * (a/b) );
}
ll modinverse(ll a, ll m)
{
return (extended_gcd(a, m).first % m + m ) % m;
}
ll cr(ll *a, ll *n, int size)
{
if( size == 1 ) return *a;
ll tmp = modinverse(n[0], n[1]);
ll tmp2 = (tmp * (a[1] - a[0]) % n[1] + n[1] ) % n[1];
ll ora = a[1];
ll tgcd = gcd(n[0], n[1]);
a[1] = a[0] + n[0] / tgcd * tmp2;
n[1] *= n[0] / tgcd;
ll ret = cr(a+1, n+1, size-1);
n[1] /= n[0] / tgcd;
a[1] = ora;
return ret;
}
ll fact(ll n, ll M, bool ch)
{
int sz = 0;
for(int c = 0; c < L.size(); c++){
ll m = L[c];
ll i = X[c];
ll cnt = CT[c];
a[sz] = get_fact(n, m, i);
if( !ch ){
ll su = N*2, tot = 0;
while( su ) tot += su / i, su /= i;
su = N+1;
while( su ) tot -= su / i, su /= i;
su = N;
while( su ) tot -= su / i, su /= i;
if( tot > cnt ) a[sz] = 0;
else{
for(int j = 0; j < tot; j++){
a[sz] = a[sz] * i % m;
}
}
}
mod[sz] = m;
sz++;
}
if( ch ){
for(int i = 0; i < sz; i++) a[i] = modinverse(a[i], mod[i]);
}
return cr(a, mod, sz);
}
ll Cat(ll n, ll m)
{
N = n, M = m;
return fact(2*N, M, false) * fact(N, M, true) % M * fact(N+1, M, true) % M;
}
//*
ll pw(ll a, int b, ll c)
{
ll ans = 1, mul = a;
while( b ){
if( b&1 ) ans = ans * mul % c;
mul = mul * mul % c, b >>= 1;
}
return ans;
}
int D = 1<<21, P = 1811939329, W = 13, R;
ll DP[1<<21];
ll C[1<<21];
ll T[1<<21];
ll w[(1<<21)+1], tim;
bool dir;
void priproc()
{
R = pw(D, P-2, P);
ll primitive_root = pw(W, (P-1)/D, P), mul = 1;
for(int i = 0; i <= D; i++){
w[i] = mul;
mul = mul * primitive_root % P;
}
}
void DFT(poly &p, int n) {
if (n == 1) return;
int Hn = n / 2;
poly p0(Hn), p1(Hn);
for (int k = 0; k < Hn; k ++) {
p0[k] = p[2*k];
p1[k] = p[2*k+1];
}
DFT(p0, Hn);
DFT(p1, Hn);
int dif = D/n;
if( dir ){
for (int i = 0, k = 0; k < D/2; k += dif, i++) {
p[i] = (p0[i] + w[k] * p1[i]) % P;
p[i + Hn] = (p0[i] + w[k + D/2] * p1[i]) % P;
}
}
else{
for (int i = 0, k = 0; k < D/2; k += dif, i++) {
p[i] = (p0[i] + w[D - k] * p1[i]) % P;
p[i + Hn] = (p0[i] + w[D/2 - k] * p1[i]) % P;
}
}
}
void poly_multi(poly& X, poly Y)
{
priproc();
dir = true; DFT(X, D); DFT(Y, D);
for(int i = 0; i < D; i++)
X[i] = X[i] * Y[i] % P;
dir = false; DFT(X, D);
for(int i = 0; i < D; i++) X[i] = X[i] * R % P;
}
int main()
{
int N;
int p, q, M, Q;
scanf("%d%d%d%d", &p, &q, &M, &Q);
if(p == 1 &&q == 0){
ll tmp = M;
for(ll i = 2; i <= tmp; i++){
if( i*i > tmp ) i = tmp;
ll m = 1, cnt = 0;
while( tmp % i == 0 ){
m *= i; cnt++;
tmp /= i;
}
if( m == 1 ) continue;
ll fac = 1;
ad[m] = L.size();
for(ll j = 1; j <= m; j++){
DB[ad[m]][j-1] = fac;
if( j % i == 0 ) continue;
fac = fac * j % m;
}
FAC[m] = fac;
L.push_back(m);
X.push_back(i);
CT.push_back(cnt);
}
for(int i = 1; i <= Q; i++){
for(int j = 0; j < 100; j++) a[j] = mod[j] = 0;
int A;
scanf("%d", &A);
if( M == 1 ){
printf("0\n");
continue;
}
ll mul = 2, ans = 1, su = A;
while(su){
if(su%2) ans = mul * ans % M;
su /= 2; mul = mul * mul % M;
}
if (A&1) printf("%lld\n", ans);
else printf("%lld\n", (ans - Cat(A/2, M) + M)%M);
}
}
else if(p == 0 &&q == 1 ){
DP[1] = 2;
ll tot = 0, mul = 2;
for(int i = 2; i <= 1000000; i++){
mul = mul * 2 % M;
if( i%2 ) tot = tot * 2 % M;
else tot = (tot * 2 + DP[i/2]) % M;
DP[i] = (mul - tot + M*2) % M;
}
for(int t = 1; t <= Q; t++){
int A;
scanf("%d", &A);
printf("%lld\n", DP[A]);
}
}
else{
ll tmp = M;
for(ll i = 2; i <= tmp; i++){
if( i*i > tmp ) i = tmp;
ll m = 1, cnt = 0;
while( tmp % i == 0 ){
m *= i; cnt++;
tmp /= i;
}
if( m == 1 ) continue;
ll fac = 1;
ad[m] = L.size();
for(ll j = 1; j <= m; j++){
DB[ad[m]][j-1] = fac;
if( j % i == 0 ) continue;
fac = fac * j % m;
}
FAC[m] = fac;
L.push_back(m);
X.push_back(i);
CT.push_back(cnt);
}
C[0] = 1;
for(int i = 1; i <= 1000000; i++){
C[i] = Cat(i, M);
}
DP[1] = 2;
ll tot = 0, mul = 2;
for(int i = 2; i <= 1000000; i++){
mul = mul * 2 % M;
if( i%2 ) tot = tot * 2 % M;
else tot = (tot * 2 + DP[i/2]) % M;
DP[i] = (mul - tot + M*2) % M;
}
mul = 8;
T[0] = 0; T[1] = 1; T[2] = 1;
do{
mul *= 2;
D = mul;
poly X(D, 0), Y(D, 0);
for(int j = 0; j < D/2; j++) X[j] = C[j];
for(int j = 0; j < D/4; j++) Y[j*2] = T[j];
poly_multi(X, Y);
for(int j = 1; j < D/2; j++) T[j] = (C[j] - X[j]%M + M) % M;
}while(mul != 1<<19);
for(int i = 1; i <= Q; i++){
int A;
scanf("%d", &A);
if(A&1) printf("%lld\n", DP[A]);
else printf("%lld\n", (DP[A] - T[A/2] + M) % M);
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
485 ms |
198196 KB |
Output is correct |
| 2 |
Correct |
845 ms |
198196 KB |
Output is correct |
| 3 |
Correct |
681 ms |
198196 KB |
Output is correct |
| 4 |
Correct |
659 ms |
198196 KB |
Output is correct |
| 5 |
Correct |
432 ms |
198196 KB |
Output is correct |
| 6 |
Correct |
178 ms |
198196 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
82 ms |
198196 KB |
Output is correct |
| 2 |
Correct |
84 ms |
198196 KB |
Output is correct |
| 3 |
Correct |
81 ms |
198196 KB |
Output is correct |
| 4 |
Correct |
74 ms |
198196 KB |
Output is correct |
| 5 |
Correct |
81 ms |
198196 KB |
Output is correct |
| 6 |
Correct |
88 ms |
198196 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5635 ms |
218588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
