1 条题解

  • 0
    @ 2026-2-1 14:21:18
    #include <bits/stdc++.h>
    using namespace std;
    //O(n^1.5) 
    const int N=200005,B=450,P=998244353;
    int n;
    int ans=0;
    int dp[N];//计算当前棋子在i格的填色方案 
    int v[B+5][B+5];//
    //当a[i]很小时(即小于B),用二维数组维护的时间复杂度较低
    //当a[i]很大时(即大于B),用朴素的动态规划来做,复杂度较为小 
    int main(){
        scanf("%d",&n);
        dp[1]=1;
        for(int i=1;i<=n;i++){
        	int x;
        	scanf("%d",&x);
        	for(int j=1;j<B;j++){//计算a[i]很小时的情况 
        		dp[i]=(dp[i]+v[j][i%j])%P;
    		}
    		if(x<B){//维护二位数组 
    			v[x][i%x]=(v[x][i%x]+dp[i])%P;
    		}else{//朴素的dp
    			int p=i;
    			while(p+x<=n){
    				p+=x;
    				dp[p]=(dp[i]+dp[p])%P;//状态转移方程,计算a[i]很大的情况 
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    		ans=(ans+dp[i])%P;//计算总答案 
    	printf("%d",ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    8267
    时间
    2500ms
    内存
    1024MiB
    难度
    8
    标签
    递交数
    13
    已通过
    7
    上传者