比赛 Asm_Def战记之透明计算网络 评测结果 AAAAAAAAAA
题目名称 Asm_Def排兵布阵 最终得分 100
用户昵称 afo 运行时间 0.095 s
代码语言 C++ 内存使用 4.51 MiB
提交时间 2017-08-29 21:01:31
显示代码纯文本
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  5. const long long MOD=998244353;
  6. long long func[500010];
  7. int num[100010];
  8. inline void exgcd(long long a,long long b,long long &d,long long &x,long long &y){
  9. if(!b){
  10. d=a;
  11. x=1;
  12. y=0;
  13. }
  14. else {
  15. exgcd(b,a%b,d,y,x);
  16. y-=(a/b)*x;
  17. }
  18. }
  19. int main(){
  20. freopen("asm_formation.in","r",stdin);
  21. freopen("asm_formation.out","w",stdout);
  22. int n;
  23. scanf("%d",&n);
  24. int sum=0;
  25. for(int i=1;i<=n;i++){
  26. scanf("%d",&num[i]);
  27. sum+=num[i];
  28. }
  29. func[1]=1;
  30. for(int i=2;i<=sum;i++)
  31. func[i]=((func[i-1]%MOD)*(i%MOD))%MOD;
  32. long long ans=1;
  33. int now=num[1];
  34. for(int i=2;i<=n;i++){
  35. if(num[i]!=1){
  36. long long res=func[num[i]-1]*func[now];
  37. res%=MOD;
  38. long long tl=func[num[i]-1+now];
  39. long long x,y,d;
  40. exgcd(MOD,res,d,x,y);
  41. long long r=res/d,M=MOD/d;
  42. if(x>0){
  43. long long k=x/r;
  44. k++;
  45. y+=k*M;
  46. y%=MOD;
  47. }
  48. if(y<0){
  49. long long k=y/M;
  50. k++;
  51. y+=k*M;
  52. y%=MOD;
  53. }
  54. y*=tl;
  55. y%=MOD;
  56. ans=ans*y;
  57. ans%=MOD;
  58. //ans=(ans+MOD)%MOD;
  59. }
  60. now+=num[i];
  61. }
  62. cout<<ans<<endl;
  63. return 0;
  64. }