Codeforces 1105C Ayoub and Lost Array (计数DP)

题目大意：

有一个长度为 n 的数列的未知数列，数列的每一个数的值都在区间 [l,r] 的范围内。现在问你能够构成多少个这样的数组，使得数组内的所有数的和能够被 3 整除。

解题分析：

类似于这种数据量大的计数问题，要不就是数学推公式，要不就是dp。

根据所有数之和能被3整除的性质，我们将所有数用%3的余数表示，推出状态转移方程：$$ dp[i][j+k]=dp[i-1][j]*num[k] $$

$dp[i][j]$表示：前$i$项之和余$j$的方案数。

这篇博客讲解的比较详细 >>>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N int(2e5+7)

const int mod = 1e9+;

ll dp[N][];

int main(){

    int n,l,r;

    scanf("%d%d%d",&n,&l,&r);

    int num0,num1,num2;     //得到余数分别为0,1,2的数的个数

    num0=r/-(l-)/;

    num1=(r-+)/-(l-+)/;

    num2=r-l+-num0-num1;

    dp[][]=num0;      //初始化dp第一项

    dp[][]=num1;

    dp[][]=num2;

    for(int i=;i<=n;i++){

        dp[i][]=((dp[i-][]*num0)%mod+(dp[i-][]*num1)%mod+(dp[i-][]*num2)%mod)%mod;

        dp[i][]=((dp[i-][]*num0)%mod+(dp[i-][]*num1)%mod+(dp[i-][]*num2)%mod)%mod;

        dp[i][]=((dp[i-][]*num0)%mod+(dp[i-][]*num1)%mod+(dp[i-][]*num2)%mod)%mod;

    }

    printf("%d\n",dp[n][]);

}

2019-02-22

巴特西

Codeforces 1105C Ayoub and Lost Array (计数DP)

最新文章

热门文章