QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#99465 | #6328. Many Products | George_Plover# | RE | 7ms | 14516kb | C++23 | 3.1kb | 2023-04-22 17:09:00 | 2023-04-22 17:09:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define wln putchar('\n')
#define ll long long
#define vi vector<int>
const int N=300005,MOD=998244353,N2=1<<17,G=3;
int sqr(int x){return 1ll*x*x%MOD;}
int mo(int x){return x>=MOD?x-MOD:x;}
void moplus(int &x,int y){x=mo(x+y);}
int ksm(int a,int b)
{
int res=1;
while(b)
{
if(b&1)res=1ll*res*a%MOD;
a=1ll*a*a%MOD;
b>>=1;
}
return res;
}
int fac[N],ifac[N];
void math_init(int n)
{
fac[0]=1;
For(i,1,n)fac[i]=1ll*fac[i-1]*i%MOD;
ifac[n]=ksm(fac[n],MOD-2);
Rof(i,n,1)ifac[i-1]=1ll*ifac[i]*i%MOD;
}
int getC(int a,int b){return 1ll*fac[a]*ifac[b]%MOD*ifac[a-b]%MOD;}
void dft(int n,int a[],int w[])
{
for(int i=0;(1<<i)<n;i++)
for(int j=0;j<n;j+=1<<i+1)
For(k,0,(1<<i)-1)
{
int x=a[j+k],y=1ll*w[(n>>i+1)*k]*a[j+(1<<i)+k]%MOD;
a[j+k]=mo(x+y); a[j+(1<<i)+k]=mo(x-y+MOD);
}
}
void mul(int n,int a[],int b[])
{
static int r[N2],w[N2>>1];
int invn=ksm(n,MOD-2);
r[0]=0;
For(i,1,n-1)
{
r[i]=r[i>>1]>>1|(i&1)*(n>>1);
if(r[i]<i)swap(a[r[i]],a[i]),swap(b[r[i]],b[i]);
}
w[0]=1; w[1]=ksm(G,(MOD-1)/n);
For(i,2,(n>>1)-1)w[i]=1ll*w[i-1]*w[1]%MOD;
dft(n,a,w); dft(n,b,w);
For(i,0,n-1)
{
a[i]=1ll*a[i]*b[i]%MOD;
if(r[i]<i)swap(a[r[i]],a[i]);
}
dft(n,a,w);
reverse(a+1,a+n);
For(i,0,n-1)a[i]=1ll*a[i]*invn%MOD;
}
void mul(vi &a,vi &b)
{
int lena=a.size(),lenb=b.size(),n=1;
while(n<lena+lenb-1)n<<=1;
int aa[n],bb[n];
copy(a.begin(),a.end(),aa);
copy(b.begin(),b.end(),bb);
fill(aa+lena,aa+n,0);
fill(bb+lenb,bb+n,0);
mul(n,aa,bb);
while(n&&aa[n-1]==0)n--;
a.clear();
For(i,0,n-1)a.push_back(aa[i]);
}
int n,a[N],lenp;
vi A[N];
ll m,p[N];
void solve(int l,int r)
{
if(l==r)return;
int mid=l+r>>1;
solve(l,mid);
solve(mid+1,r);
mul(A[l],A[mid+1]);
}
int main()
{
math_init(300000);
scanf("%d%lld",&n,&m);
ll mm=m;
for(int i=2;1ll*i*i<=m;i++)
if(m%i==0)
{
p[++lenp]=i;
while(m%i==0)m/=i,a[lenp]++;
}
if(m>1)p[++lenp]=m,a[lenp]=1;
//For(i,1,lenp)printf("(%lld,%d)",p[i],a[i]); wln;
m=mm;
For(i,1,n)
{
int x;
scanf("%d",&x);
A[i].push_back(x);
A[i].push_back(1);
}
solve(1,n);
//for(int x:A[1])printf("%d ",x); wln;
//printf("---\n");
int res=(m+A[1][0])%MOD;
For(i,1,lenp)res=1ll*res*getC(a[i]+n-1,n-1)%MOD;
//printf("res=%d\n",res);
For(i,1,n-1)
{
int s=A[1][i];
For(j,1,lenp)
{
int ss=0,x=1;
For(k,0,a[j])
{
ss=(ss+1ll*x*getC(k+i-1,i-1)%MOD*getC(a[j]-k+n-i-1,n-i-1))%MOD;
x=1ll*x*p[j]%MOD;
}
s=1ll*s*ss%MOD;
}
moplus(res,s);
}
printf("%d",res);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14440kb
input:
2 3 0 1
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 2ms
memory: 14516kb
input:
5 1 0 1 2 3 4
output:
120
result:
ok 1 number(s): "120"
Test #3:
score: 0
Accepted
time: 7ms
memory: 14408kb
input:
10 314159265358 0 1 2 3 4 5 6 7 8 9
output:
658270849
result:
ok 1 number(s): "658270849"
Test #4:
score: -100
Runtime Error
input:
200000 999999999989 823489320 406308599 710963770 183707427 192930969 941365774 318564299 391028855 945374838 651744270 515755727 220857626 599403217 214957584 335628890 771694833 40989299 34892948 630275822 869708185 432704750 924850167 707864789 232688853 406616372 529994171 782650336 979286144 65...