CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. ACM-ICPC
  3. 动态规划
  4. 正文

ABC262D - I Hate Non-integer Number(三维线性DP)

2022年8月13日 417点热度 1人点赞 0条评论

题目链接:ABC262D

题意:

给出n个正整数,选出若干个数字,求这若干个数字的平均值是正整数的方案数,答案对998244353取模。

思路:

一开始想着的是dp[i][j][k]表示前i个数选择j个数其中和为k的方案数。

k会很大,所以需要考虑取模,存储和对j取模。

不选a[i]的转移方程有dp[i][j][k] = dp[i-1][j][k],但是如果选a[i]的时候有些难办,现在sum=k那上一个状态如何得来?(sum-a[i])%(j-1)=?这个不好办。所以这个O(n^3)方法不太行。

定义dp[j][k][l]为把i作为分母(说明要选i个数),前j个数,选择k个,和模i为l的方案数。i枚举的是子集大小,%i的意义就是最后要除以的那个i。

  • 不选择a[j]:dp[j+1][k][l] += dp[j][k][l];
  • 选择a[j]:dp[j+1][k+1][(l+a[j])%i] += dp[j][k][l];需要满足k<i,因为这是递推的

代码

mint dp[N][N][N],ans;
inline void Case_Test()
{
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    for (int i=1;i<=n;i++)
    {
        memset(dp,0,sizeof dp);
        dp[0][0][0] = 1;
        for (int j=0;j<n;j++)
            for (int k=0;k<=i;k++)
                for (int l=0;l<i;l++)
                {
                    dp[j+1][k][l] += dp[j][k][l];
                    if (k<i) dp[j+1][k+1][(l+a[j])%i] += dp[j][k][l];
                }
        ans += dp[n][i][0];
    }
    cout<<ans;
}
标签: AtCoder 动态规划 线性DP
最后更新:2022年8月13日

Carry

来自于湖南长沙

点赞
< 上一篇

文章评论

取消回复
标签
AtCoder 动态规划 线性DP
文章目录
  • 题意:
  • 思路:
  • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS