• D. Chip Move(思维,模拟)


    There is a chip on the coordinate line. Initially, the chip is located at the point 00. You can perform any number of moves; each move increases the coordinate of the chip by some positive integer (which is called the length of the move). The length of the first move you make should be divisible by kk, the length of the second move — by k+1k+1, the third — by k+2k+2, and so on.

    For example, if k=2k=2, then the sequence of moves may look like this: 0→4→7→19→440→4→7→19→44, because 4−0=44−0=4 is divisible by 2=k2=k, 7−4=37−4=3 is divisible by 3=k+13=k+1, 19−7=1219−7=12 is divisible by 4=k+24=k+2, 44−19=2544−19=25 is divisible by 5=k+35=k+3.

    You are given two positive integers nn and kk. Your task is to count the number of ways to reach the point xx, starting from 00, for every x∈[1,n]x∈[1,n]. The number of ways can be very large, so print it modulo 998244353998244353. Two ways are considered different if they differ as sets of visited positions.

    Input

    The first (and only) line of the input contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105).

    Output

    Print nn integers — the number of ways to reach the point xx, starting from 00, for every x∈[1,n]x∈[1,n], taken modulo 998244353998244353.

    Examples

    input

    Copy

    8 1
    

    output

    Copy

    1 1 2 2 3 4 5 6 

    input

    Copy

    10 2
    

    output

    Copy

    0 1 0 1 1 1 1 2 2 2 

    Note

    Let's look at the first example:

    Ways to reach the point 11: [0,1][0,1];

    Ways to reach the point 22: [0,2][0,2];

    Ways to reach the point 33: [0,1,3][0,1,3], [0,3][0,3];

    Ways to reach the point 44: [0,2,4][0,2,4], [0,4][0,4];

    Ways to reach the point 55: [0,1,5][0,1,5], [0,3,5][0,3,5], [0,5][0,5];

    Ways to reach the point 66: [0,1,3,6][0,1,3,6], [0,2,6][0,2,6], [0,4,6][0,4,6], [0,6][0,6];

    Ways to reach the point 77: [0,2,4,7][0,2,4,7], [0,1,7][0,1,7], [0,3,7][0,3,7], [0,5,7][0,5,7], [0,7][0,7];

    Ways to reach the point 88: [0,3,5,8][0,3,5,8], [0,1,5,8][0,1,5,8], [0,2,8][0,2,8], [0,4,8][0,4,8], [0,6,8][0,6,8], [0,8][0,8].

    思路:

    1,没什么规律,k+2在k+1的基础上转移来的,有点类似dp,所以就模拟一下k加的过程

    2,b,c数组交替运用,详细的请看代码

    代码:

    1. #include
    2. using namespace std;
    3. #define int long long
    4. #define vec vector
    5. #define pi 3.1415926
    6. #define rep(i,l,r) for(int i=l;i<=r;++i)
    7. #pragma GCC optimize(2)//
    8. #pragma GCC optimize(3,"Ofast","inline")//
    9. const int maxj=2e5+100,mod=998244353,inf=0x7f7f7f7f7f7f7f;
    10. int a[maxj],b[maxj],c[maxj];
    11. void solve(){
    12. int n,k;cin>>n>>k;
    13. for(int i=k;i<=n;i+=k)a[i]++,b[i]++;//初始化数组
    14. int t=k*2+1;
    15. k++;
    16. bool ff=0;
    17. while(t<=n){//k+2在k+1基础上来的,类似于dp,有状态和转移方程之类的
    18. if(!ff){
    19. for(int i=t;i<=n;++i){
    20. c[i]=(b[i-k]+c[i-k])%mod;//b表示之前的状态,c表示当前k状态下,加多个k
    21. a[i]=(a[i]+c[i])%mod;//a进行累加
    22. }
    23. memset(b,0,sizeof(b));//清空b,防止对后续造成影响
    24. }else{
    25. for(int i=t;i<=n;++i){//c表示之前的状态,b表示当前k状态下,加多个k
    26. b[i]=(b[i-k]+c[i-k])%mod;
    27. a[i]=(a[i]+b[i])%mod;
    28. }
    29. memset(c,0,sizeof(c));
    30. }
    31. k++;
    32. ff=1-ff;
    33. t+=k;
    34. }
    35. for(int i=1;i<=n;++i)cout<' ';
    36. cout<<'\n';
    37. }
    38. signed main(){
    39. ios::sync_with_stdio(0);//能不用c语言的输入输出,尽量不要用
    40. cin.tie(0);
    41. cout.tie(0);
    42. int t;
    43. t=1;
    44. // cin>>t;
    45. while(t--)solve();
    46. return 0;
    47. }

  • 相关阅读:
    如何用度量数据驱动代码评审的改善
    JS中应该注意的点
    Java 浅析线程池ThreadPoolExecutor
    GAME (HDU)(博弈论)
    【JavaEE】多线程(一)
    高级篇之ENC编码器多机位帧同步配置详解
    【JVM笔记】引用计数算法与可达性分析算法
    记录一次递归查询导致的 java.lang.StackOverflowError: null
    【Python百日进阶-数据分析】Day326 - plotly.express.scatter_geo():地理散点图
    Spring框架系列(14) - SpringMVC实现原理之DispatcherServlet处理请求的过程
  • 原文地址:https://blog.csdn.net/m0_63054077/article/details/126179893