答题卡

答题卡

https://ac.nowcoder.com/acm/contest/5389/C

题意:

求n * n的网格图横竖对称的填法

思路:

假设是个n * n的网格图,如果第一行放在第一列那就剩下的(n-1) * (n-1)化简问题 , 如果第一行放在第二列 , 那第二行的位置也就固定了,剩下(n-2) * (n-2),同理第三第四。。。。,除去第一行有 n - 1 行
所以可以得出dp[ i ] = dp[ i - 1 ] + (i-1)*dp[ i - 2 ]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100005];
int main(){
    dp[0] = dp[1] = 1;dp[2] = 2;
    ll n;
    cin>>n;
    for(int i = 3 ; i <= n ;++i){
        dp[i] = (dp[i-1] + (i-1)*dp[i-2])%mod;
    }
    cout<<dp[n]<<endl;
}
全部评论
dp[ i ] = dp[ i - 1 ] + (n-1)*dp[ i - 2 ]因该是dp[ i ] = dp[ i - 1 ] + (i-1)*dp[ i - 2 ]
点赞 回复 分享
发布于 2020-05-02 15:09
不愧是你,大佬厉害
点赞 回复 分享
发布于 2020-05-02 13:12
感谢分享
点赞 回复 分享
发布于 2020-05-02 10:25
我用深搜还错了,还能这么做~
点赞 回复 分享
发布于 2020-05-02 10:18

相关推荐

点赞 评论 收藏
分享
人间雪:简历最好只要一页,除非你牛逼到一页都写不下了
点赞 评论 收藏
分享
07-01 23:23
郑州大学 Java
否极泰来来来来:牛客迟早有高三的
点赞 评论 收藏
分享
评论
7
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务