[关闭]
@KirinBill 2017-10-06T09:28:15.000000Z 字数 5239 阅读 975

2017.10.6 NOIP模拟赛

题解 套题

要相信自己,但不要过分相信自己的直觉。

目录


装备部的难题

AebbJ.png
Aea1r.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <cstring>
  30. const int MAXN=500005;
  31. int n;
  32. int v[MAXN];
  33. inline void read_chr(char &c){
  34. do{c=getchar();}while(c!='L' && c!='R');
  35. }
  36. template<class T>
  37. long long mge_sort(int l,int r,T a[]){
  38. static T tmp[MAXN];
  39. if(l==r) return 0;
  40. int mid=l+r>>1;
  41. long long ret=mge_sort(l,mid,a)+mge_sort(mid+1,r,a);
  42. int cur=l-1,lp=l,rp=mid+1;
  43. while(lp<=mid && rp<=r){
  44. if(a[lp]>a[rp]){
  45. tmp[++cur]=a[rp++];
  46. ret+=mid-lp+1;
  47. }
  48. else tmp[++cur]=a[lp++];
  49. }
  50. while(lp<=mid) tmp[++cur]=a[lp++];
  51. while(rp<=r) tmp[++cur]=a[rp++];
  52. memcpy(a+l,tmp+l,(r-l+1)*sizeof(T));
  53. return ret;
  54. }
  55. int main(){
  56. setIO("problem");
  57. read(n);
  58. char cmd;
  59. for(int i=1;i<=n;++i){
  60. read_chr(cmd);
  61. read(v[i]);
  62. if(cmd=='L') v[i]=-v[i];
  63. }
  64. write(mge_sort(1,n,v));
  65. return 0;
  66. }

尼伯龙根之歌

Aev8M.png
Ae0e1.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. const int MAXN=100005,MAXM=5*MAXN,P=998244353;
  30. int n,m;
  31. int he[MAXN],dp[MAXN],inD[MAXN],outD[MAXN];
  32. bool noIn[MAXN];
  33. struct line{int to,nex;}ed[MAXM];
  34. inline void addE(int u,int v){
  35. static int cnt=0;
  36. ed[++cnt]=(line){v,he[u]};
  37. he[u]=cnt;
  38. }
  39. inline int pow(int x,int y){
  40. int ret=1;
  41. for(;y;y>>=1,x=(long long)x*x%P){
  42. if(y&1) ret=(long long)ret*x%P;
  43. }
  44. return ret;
  45. }
  46. inline int inv(int x){return pow(x,P-2);}
  47. void DAG_DP(int u){
  48. if(u==n){
  49. write(dp[u]);
  50. exit(0);
  51. }
  52. int psb=(long long)dp[u]*inv(outD[u])%P;
  53. for(int i=he[u],v;i;i=ed[i].nex){
  54. v=ed[i].to;
  55. dp[v]=(dp[v]+psb)%P;
  56. if(--inD[v]==0) DAG_DP(v);
  57. }
  58. }
  59. int main(){
  60. setIO("deathsong");
  61. read(n),read(m);
  62. for(int i=1,u,v;i<=m;++i){
  63. read(u),read(v);
  64. addE(u,v);
  65. ++outD[u],++inD[v];
  66. }
  67. for(int i=1;i<=n;++i) noIn[i]=(inD[i]==0);
  68. dp[1]=1;
  69. for(int i=1;i<=n;++i){
  70. if(noIn[i]) DAG_DP(i);
  71. }
  72. }

冰窖之谜

AehZT.png
AeQ2F.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. const int P=1e9+9;
  30. long long n,k;
  31. inline int pow(int x,long long y){
  32. int ret=1;
  33. for(;y;y>>=1,x=(long long)x*x%P){
  34. if(y&1) ret=(long long)ret*x%P;
  35. }
  36. return ret;
  37. }
  38. namespace solve1
  39. {
  40. const int MAXN=1e6+5;
  41. int fib[MAXN],sum[MAXN];
  42. inline void pre_tab(){
  43. fib[1]=1;
  44. for(int i=2;i<MAXN;++i)
  45. fib[i]=(fib[i-1]+fib[i-2])%P;
  46. }
  47. inline int solve(){
  48. for(int i=1;i<=n;++i)
  49. sum[i]=(sum[i-1]+pow(fib[i],k))%P;
  50. return sum[n];
  51. }
  52. }
  53. namespace solve2
  54. {
  55. const int sqrt_5=383008016,X=691504013,Y=308495997,MAXK=1e5+5;
  56. int fac[MAXK],fac_inv[MAXK];
  57. inline int inv(int x){return pow(x,P-2);}
  58. inline void pre_tab(){
  59. fac[0]=1;
  60. for(int i=1;i<MAXK;++i)
  61. fac[i]=(long long)fac[i-1]*i%P;
  62. fac_inv[MAXK-1]=inv(fac[MAXK-1]);
  63. for(int i=MAXK-2;i>=0;--i)
  64. fac_inv[i]=(long long)fac_inv[i+1]*(i+1)%P;
  65. }
  66. inline int C(int n,int m){
  67. return (long long)fac[n]*fac_inv[m]%P*fac_inv[n-m]%P;
  68. }
  69. inline int cal(int a){
  70. int b=k-a;
  71. int z=(long long)pow(X,b)*pow(Y,a)%P;
  72. int ret;
  73. if(z==1) ret=n%P;
  74. else{
  75. ret=(pow(z,n+1)-z+P)%P;
  76. ret=(long long)ret*inv((z-1+P)%P)%P;
  77. }
  78. return (long long)ret*C(k,a)%P;
  79. }
  80. inline int solve(){
  81. int ret=0;
  82. for(int i=0;i<=k;++i){
  83. if(i&1) ret=(ret-cal(i)+P)%P;
  84. else ret=(ret+cal(i))%P;
  85. }
  86. return (long long)ret*pow(inv(sqrt_5),k)%P;
  87. }
  88. }
  89. int main(){
  90. setIO("ice");
  91. int T;
  92. read(T);
  93. solve1::pre_tab();
  94. solve2::pre_tab();
  95. while(T--){
  96. read(n),read(k);
  97. if(n<solve1::MAXN) write(solve1::solve(),'\n');
  98. else write(solve2::solve(),'\n');
  99. }
  100. return 0;
  101. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注