QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #289290 | #6325. Peaceful Results | ccc | Compile Error | / | / | C++14 | 7.3kb | 2023-12-23 16:42:21 | 2023-12-23 16:42:22 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15e5+155;
const int mod=998244353, G=3;
int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
int Inv(int x) { return ksm(x,mod-2); }
const int invG=Inv(G);
int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
double a[10][10]; int y[7];
void Read() { scanf("%lld",&n); really_n=n; scanf("%lld%lld%lld",&AR,&AP,&AS); scanf("%lld%lld%lld",&BR,&BP,&BS); scanf("%lld%lld%lld",&CR,&CP,&CS); }
void init() {
a[1][1]=1; a[1][2]=1; a[1][3]=1; a[1][7]=AR-AS;
a[2][4]=1; a[2][5]=1; a[2][6]=1; a[2][7]=AP-AS;
a[3][1]=1; a[3][2]=-1; a[3][5]=1; a[3][6]=-1; a[3][7]=BR-BS;
a[4][2]=-1; a[4][3]=1; a[4][4]=1; a[4][6]=-1; a[4][7]=BP-BS;
a[5][1]=1; a[5][3]=-1; a[5][5]=-1; a[5][6]=1; a[5][7]=CR-CS;
a[6][2]=1; a[6][3]=-1; a[6][4]=1; a[6][5]=-1; a[6][7]=CP-CS;
}
void solve_gs() {
const double eps=1e-8;
int nukt=n; n=6;
for(int i=1;i<=n;i++) {
bool fbi=false;
for(int j=i;j<=n;j++) { if(fabs(a[j][i])>eps) { fbi=true; for(int k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); break; } }
if(!fbi) { puts("0"); exit(0); }
for(int j=1;j<=n;j++) {
if(i==j) continue;
double num=a[j][i]/a[i][i];
for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*num;
}
}
for(int i=1;i<=n;i++) {
double yi=a[i][n+1]/a[i][i];
if(yi+eps<=ceil(yi)) { puts("0"); exit(0); }
// if(yi!=floor(yi)) { puts("0"); exit(0); }
y[i]=yi;
}
n=nukt;
}
void solve1() {
Read();
init(); solve_gs();
// for(int i=1;i<=6;i++) printf("%lld ",y[i]);
}
int tr[N];
void NTT(int *f,bool Is) {
for(int i=0;i<n;i++) if(i<tr[i]) swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1) {
int len=p>>1; int w_len_1=ksm( ( Is?G:invG ),(mod-1)/p );
for(int str=0;str<n;str+=p) {
int w_len_now=1;
for(int i=str;i<str+len;i++) {
int now=f[i+len]*w_len_now%mod;
f[i+len]=( f[i]-now+mod )%mod;
f[i]=( f[i]+now )%mod;
w_len_now = w_len_now * w_len_1 % mod;
}
}
}
}
int jc[N],inv[N];
int fa[N],fb[N],fc[N];
void INIT() {
jc[0]=1; for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
inv[n]=ksm(jc[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
void solve2() {
n=AS;//ÏÖÔÚ¼ÆËãµÄÊdzöSµÄ²½Êý
int s1=max( 0ll,min(-y[1],-y[4]) ), s2=max( 0ll,min(-y[2],-y[5]) ), s3=max( 0ll,min(-y[3],-y[6]) );
//ÿһÏî¾ùΪÕýÕûÊý£¬ÓÖÒòΪyÊDzîÖµ£¬¿ÉµÃÉÏʽ
int m=n; n=1; while(n<=2*m) n<<=1;
// for(int i=1;i<=6;i++) cout<<y[i]<<" ";
for(int i=s1;i<=m;i++) fa[i]=inv[i]*inv[i+y[1]]%mod*inv[i+y[4]]%mod;
for(int i=s2;i<=m;i++) fb[i]=inv[i]*inv[i+y[2]]%mod*inv[i+y[5]]%mod;
for(int i=s3;i<=m;i++) fc[i]=inv[i]*inv[i+y[3]]%mod*inv[i+y[6]]%mod;
for(int i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(fa,true); NTT(fb,true); NTT(fc,true);
for(int i=0;i<n;i++) fa[i]=fa[i]*fb[i]%mod*fc[i]%mod;
NTT(fa,false);
// for(int i=0;i<n;i++) cout<<fa[i]<<" ";
int ans=fa[m]*Inv(n)%mod*jc[really_n]%mod;
printf("%lld",ans);
}
void solve3() {
int s1=max( 0ll,min(-y[1],-y[4]) ), s2=max( 0ll,min(-y[2],-y[5]) ), s3=max( 0ll,min(-y[3],-y[6]) );
// for(int i=1;i<=6;i++) cout<<y[i]<<" ";
int ans=0;
for(int i=s1;i<=n;i++) {
for(int j=s2;j<=n;j++) {
for(int k=s3;k<=n;k++) {
if(i+j+k!=n) continue;
cout<<i<<" "<<j<<" "<<k<<endl;
int mul=jc[i]*jc[j]%mod*jc[k]%mod;
mul=mul*jc[i+y[1]]%mod*jc[i+y[4]]%mod;
mul=mul*jc[j+y[2]]%mod*jc[j+y[5]]%mod;
mul=mul*jc[k+y[3]]%mod*jc[k+y[6]]%mod;
cout<<Inv(mul)*jc[n]%mod<<" ";
ans+=Inv(mul)*jc[n]%mod;
}
}
} printf("%lld",ans);
}
#undef int
int main() {
solve1();
INIT();
solve2();
// solve3();
return 0;
} #include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=15e5+155;
const int mod=998244353, G=3;
int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
int Inv(int x) { return ksm(x,mod-2); }
const int invG=Inv(G);
int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
double a[10][10]; int y[7];
void Read() { scanf("%lld",&n); really_n=n; scanf("%lld%lld%lld",&AR,&AP,&AS); scanf("%lld%lld%lld",&BR,&BP,&BS); scanf("%lld%lld%lld",&CR,&CP,&CS); }
void init() {
a[1][1]=1; a[1][2]=1; a[1][3]=1; a[1][7]=AR-AS;
a[2][4]=1; a[2][5]=1; a[2][6]=1; a[2][7]=AP-AS;
a[3][1]=1; a[3][2]=-1; a[3][5]=1; a[3][6]=-1; a[3][7]=BR-BS;
a[4][2]=-1; a[4][3]=1; a[4][4]=1; a[4][6]=-1; a[4][7]=BP-BS;
a[5][1]=1; a[5][3]=-1; a[5][5]=-1; a[5][6]=1; a[5][7]=CR-CS;
a[6][2]=1; a[6][3]=-1; a[6][4]=1; a[6][5]=-1; a[6][7]=CP-CS;
}
void solve_gs() {
const double eps=1e-8;
int nukt=n; n=6;
for(int i=1;i<=n;i++) {
bool fbi=false;
for(int j=i;j<=n;j++) { if(fabs(a[j][i])>eps) { fbi=true; for(int k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); break; } }
if(!fbi) { puts("0"); exit(0); }
for(int j=1;j<=n;j++) {
if(i==j) continue;
double num=a[j][i]/a[i][i];
for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*num;
}
}
for(int i=1;i<=n;i++) {
double yi=a[i][n+1]/a[i][i];
if(yi!=ceil(yi)) { puts("0"); exit(0); }
// if(yi!=floor(yi)) { puts("0"); exit(0); }
y[i]=yi;
}
n=nukt;
}
void solve1() {
Read();
init(); solve_gs();
// for(int i=1;i<=6;i++) printf("%lld ",y[i]);
}
int tr[N];
void NTT(int *f,bool Is) {
for(int i=0;i<n;i++) if(i<tr[i]) swap(f[i],f[tr[i]]);
for(int p=2;p<=n;p<<=1) {
int len=p>>1; int w_len_1=ksm( ( Is?G:invG ),(mod-1)/p );
for(int str=0;str<n;str+=p) {
int w_len_now=1;
for(int i=str;i<str+len;i++) {
int now=f[i+len]*w_len_now%mod;
f[i+len]=( f[i]-now+mod )%mod;
f[i]=( f[i]+now )%mod;
w_len_now = w_len_now * w_len_1 % mod;
}
}
}
}
int jc[N],inv[N];
int fa[N],fb[N],fc[N];
void INIT() {
jc[0]=1; for(int i=1;i<=n;i++) jc[i]=jc[i-1]*i%mod;
inv[n]=ksm(jc[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
void solve2() {
n=AS;//ÏÖÔÚ¼ÆËãµÄÊdzöSµÄ²½Êý
int s1=max( 0ll,min(-y[1],-y[4]) ), s2=max( 0ll,min(-y[2],-y[5]) ), s3=max( 0ll,min(-y[3],-y[6]) );
//ÿһÏî¾ùΪÕýÕûÊý£¬ÓÖÒòΪyÊDzîÖµ£¬¿ÉµÃÉÏʽ
int m=n; n=1; while(n<=2*m) n<<=1;
// for(int i=1;i<=6;i++) cout<<y[i]<<" ";
for(int i=s1;i<=m;i++) fa[i]=inv[i]*inv[i+y[1]]%mod*inv[i+y[4]]%mod;
for(int i=s2;i<=m;i++) fb[i]=inv[i]*inv[i+y[2]]%mod*inv[i+y[5]]%mod;
for(int i=s3;i<=m;i++) fc[i]=inv[i]*inv[i+y[3]]%mod*inv[i+y[6]]%mod;
for(int i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
NTT(fa,true); NTT(fb,true); NTT(fc,true);
for(int i=0;i<n;i++) fa[i]=fa[i]*fb[i]%mod*fc[i]%mod;
NTT(fa,false);
// for(int i=0;i<n;i++) cout<<fa[i]<<" ";
int ans=fa[m]*Inv(n)%mod*jc[really_n]%mod;
printf("%lld",ans);
}
void solve3() {
int s1=max( 0ll,min(-y[1],-y[4]) ), s2=max( 0ll,min(-y[2],-y[5]) ), s3=max( 0ll,min(-y[3],-y[6]) );
// for(int i=1;i<=6;i++) cout<<y[i]<<" ";
int ans=0;
for(int i=s1;i<=n;i++) {
for(int j=s2;j<=n;j++) {
for(int k=s3;k<=n;k++) {
if(i+j+k!=n) continue;
cout<<i<<" "<<j<<" "<<k<<endl;
int mul=jc[i]*jc[j]%mod*jc[k]%mod;
mul=mul*jc[i+y[1]]%mod*jc[i+y[4]]%mod;
mul=mul*jc[j+y[2]]%mod*jc[j+y[5]]%mod;
mul=mul*jc[k+y[3]]%mod*jc[k+y[6]]%mod;
cout<<Inv(mul)*jc[n]%mod<<" ";
ans+=Inv(mul)*jc[n]%mod;
}
}
} printf("%lld",ans);
}
#undef int
int main() {
solve1();
INIT();
solve2();
// solve3();
return 0;
}
Details
answer.code:123:3: error: stray ‘#’ in program
123 | } #include<bits/stdc++.h>
| ^
answer.code:123:4: error: ‘include’ does not name a type
123 | } #include<bits/stdc++.h>
| ^~~~~~~
answer.code:126:11: error: redefinition of ‘const long long int N’
126 | const int N=15e5+155;
| ^
answer.code:4:11: note: ‘const long long int N’ previously defined here
4 | const int N=15e5+155;
| ^
answer.code:127:11: error: redefinition of ‘const long long int mod’
127 | const int mod=998244353, G=3;
| ^~~
answer.code:5:11: note: ‘const long long int mod’ previously defined here
5 | const int mod=998244353, G=3;
| ^~~
answer.code:127:26: error: redefinition of ‘const long long int G’
127 | const int mod=998244353, G=3;
| ^
answer.code:5:26: note: ‘const long long int G’ previously defined here
5 | const int mod=998244353, G=3;
| ^
answer.code:128:5: error: redefinition of ‘long long int ksm(long long int, long long int)’
128 | int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
| ^~~
answer.code:6:5: note: ‘long long int ksm(long long int, long long int)’ previously defined here
6 | int ksm(int x,int y) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans; }
| ^~~
answer.code:129:5: error: redefinition of ‘long long int Inv(long long int)’
129 | int Inv(int x) { return ksm(x,mod-2); }
| ^~~
answer.code:7:5: note: ‘long long int Inv(long long int)’ previously defined here
7 | int Inv(int x) { return ksm(x,mod-2); }
| ^~~
answer.code:130:11: error: redefinition of ‘const long long int invG’
130 | const int invG=Inv(G);
| ^~~~
answer.code:8:11: note: ‘const long long int invG’ previously declared here
8 | const int invG=Inv(G);
| ^~~~
answer.code:133:5: error: redefinition of ‘long long int n’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^
answer.code:11:5: note: ‘long long int n’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^
answer.code:133:7: error: redefinition of ‘long long int AR’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:7: note: ‘long long int AR’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:10: error: redefinition of ‘long long int AP’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:10: note: ‘long long int AP’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:13: error: redefinition of ‘long long int AS’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:13: note: ‘long long int AS’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:16: error: redefinition of ‘long long int BR’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:16: note: ‘long long int BR’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:19: error: redefinition of ‘long long int BP’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:19: note: ‘long long int BP’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:22: error: redefinition of ‘long long int BS’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:22: note: ‘long long int BS’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:25: error: redefinition of ‘long long int CR’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:25: note: ‘long long int CR’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:28: error: redefinition of ‘long long int CP’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:28: note: ‘long long int CP’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:31: error: redefinition of ‘long long int CS’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:11:31: note: ‘long long int CS’ previously declared here
11 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ^~
answer.code:133:34: error: redefinition of ‘long long int really_n’
133 | int n,AR,AP,AS,BR,BP,BS,CR,CP,CS,really_n;
| ...