上一主题 下一主题
ScriptCat,新一代的脚本管理器脚本站,与全世界分享你的用户脚本油猴脚本开发指南教程目录
返回列表 发新帖

2320. 统计放置房子的方式数 JavaScript计算出现问题

[复制链接]
  • TA的每日心情
    擦汗
    2024-7-16 09:20
  • 签到天数: 192 天

    [LV.7]常住居民III

    701

    主题

    5790

    回帖

    6624

    积分

    管理员

    非物质文化遗产社会摇传承人

    积分
    6624

    荣誉开发者管理员油中2周年生态建设者喜迎中秋

    发表于 2024-10-1 00:06:02 | 显示全部楼层 | 阅读模式

    一开始我也是打的相乘

    var countHousePlacements = function (n) {
        const dp = new Array(n).fill(0)
        dp[0] = 2;
        dp[1] = 3;
        for (let index = 2; index < dp.length; index++) {
            dp[index] = (dp[index - 1] + dp[index - 2]) % (1000000000 + 7)
        }
        return (dp[n-1]*dp[n-1])% (1000000000 + 7)
    };

    但是发现不管怎么样都差了几百
    没办法转成了dp

    var countHousePlacements = function (n) {
        const dp = new Array(n).fill(0).map(() => new Array(4).fill(0));
        dp[0][0] = 1;//不存在房屋
        dp[0][1] = 1;//存在房屋
        dp[0][2] = 1;//上存在下不存在
        dp[0][3] = 1;//上不存在下存在
        for (let index = 1; index < dp.length; index++) {
            dp[index][0] = (dp[index - 1][0] + dp[index - 1][1] + dp[index - 1][2] + dp[index - 1][3]) % (1000000000 + 7)
            dp[index][1] = dp[index - 1][0] % (1000000000 + 7)
            dp[index][2] = (dp[index - 1][3] + dp[index - 1][0]) % (1000000000 + 7)
            dp[index][3] = (dp[index - 1][2] + dp[index - 1][0]) % (1000000000 + 7)
        }
        let result = 0
        for (let index = 0; index < 4; index++) {
            result+=   dp[dp.length-1][index]
    
        }
        return result% (1000000000 + 7)
    };

    后来提交成功发现官解跟我的答案始终都差
    根据调试发现应该是JS的浮点数计算跟其他的语言有不一致的情况
    给数字后面加个n并且mod的数字也改为Bigint再跑就会出现正确答案

    var countHousePlacements = function (n) {
        const dp = new Array(n+1).fill(0n)
        dp[0] = 1n;
        dp[1] = 2n;
        for (let index = 2; index < dp.length; index++) {
            dp[index] =( dp[index - 1] + dp[index - 2]) % (1000000000n + 7n)
        }
        return (dp[n]*dp[n])% (1000000000n + 7n)
    };

    应该跟IEFI浮点数的标准实现有关,就不细究更多了,反正能过就行

    混的人。
    ------------------------------------------
    進撃!永遠の帝国の破壊虎---李恒道

    入驻了爱发电https://afdian.net/a/lihengdao666
    个人宣言:この世界で私に胜てる人とコードはまだ生まれていません。死ぬのが怖くなければ来てください。

    发表回复

    本版积分规则

    快速回复 返回顶部 返回列表