首页 > 试题广场 >

视力表

[编程题]视力表
  • 热度指数：1905 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小强今天体检，其中有一个环节是测视力
小强看到的视力表是一张的表格，但是由于小强视力太差，他无法看清表格中的符号。不过热爱数学的他给自己出了这样一个问题：假设现在有a个向上的符号，b个向下的符号，c个向左的符号，d个向右的符号，把这些符号填到视力表中，总共有多少种可能的情况呢？

输入描述:
第一行输入五个数N, a, b, c, d
保证


输出描述:
输出一个数字，表示答案
由于结果可能很大，只需输出对998244353取模之后的结果即可
示例1

输入

2 3 1 0 0

输出

4

说明

共有如下四种情况

上上    上上
上下    下上

上下    下上
上上    上上
示例2

输入

2 2 1 1 0

输出

12
示例3

输入

2 1 1 1 1

输出

24

备注:
数据保证，且
对于的数据，N = 2
对于的数据, 
对于的数据，
对于的数据，
算法知识视频讲解
添加回答
缀念201902191412240头像 缀念201902191412240
1.将二维平铺成一维，答案(n*n)!/(a!*b!*c!*d!)
2.这里使用逆元计算。
注意(前三个写成a=m*a1+k,b=m*b1+v得证)
(a+b)%m=(a%m+b%m)%m
(a−b)%m=(a%m−b%m)%m
(a×b)%m=(a%m×b%m)%m
除法不成立
3.结论：a的逆元 = a^(p-2) mod p 
过程可以B站或百度
费马小定理:a^(p-1)=1(mod p)
a * a^(p-2) =1(mod p)
4.inv[i]=(i!)^-1=(i+1) * (i+1)!^-1=inv[i+1]*(i+1) 
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<map>
#include<iomanip>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include <cstdlib>
#include <climits>
#include <ctype.h>
#include<functional>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long int ll;
int n, a, b, c, d;
const int MOD = 998244353;
ll f[maxn], inv[maxn];//f存储i阶乘，inv存储(i阶乘)的逆元
//
ll Pow(ll x, ll t)
{
	ll cnt = 1;
	while (t)
	{
		if (t & 1)
			cnt = cnt*x%MOD;
		x = x * x %MOD;
		t >>= 1;
	}
	return cnt;
}

void init()
{
	cin >> n >> a >> b >> c >> d;
	n = n*n;
	f[0] = 1;
	for (int i = 1;i <= n;i++)
		f[i] = i*f[i - 1] % MOD;

	//a的逆元 = a^(p-2) mod p 
	inv[0] = 1;
	inv[n] = Pow(f[n], MOD - 2);
	//inv[i]=inv[i+1]*(i+1)
	for (int i = n-1;i >= 1;i--)
		inv[i] = inv[i + 1] * (i + 1) % MOD;
}

int main()
{
	init();
	ll ans = f[n];
	//cout << f[n] << ' ' << inv[a] << ' ' << inv[b] << ' ' << inv[c] << ' ' << inv[d] << '\n';
	//for (int i = n;i >= 1;i--)
	//	cout << inv[i] << ' ';
	//cout << endl;
	ans = ans*inv[a] % MOD;
	ans = ans*inv[b] % MOD;
	ans = ans*inv[c] % MOD;
	ans = ans*inv[d] % MOD;
	cout << ans << '\n';
}
/*
3 7 1 0 1
*/

发表于 2021-08-18 11:54:14 回复(0)
pein531头像 pein531
本来这个题应该写一个快速计算阶乘的算法，结果这个数据量暴力法一下给过了。用python现成的函数更加方便。 
from math import factorial

n, a, b, c, d = map(int, input().split())
print(factorial(n*n) // factorial(a) // factorial(b) // factorial(c) // factorial(d) % 998244353)

发表于 2021-07-22 13:04:56 回复(2)
墨羽魂韶头像 墨羽魂韶

由于这个题没有给出具体数据, 写的时候照着能解决尽可能大的数据写的

通过分析, 不难发现最终结果为组合数
可以选择正常的组合数公式, 也可以选择使用阶乘公式+逆元进行组合数计算, 但是由于初衷是解决尽可能大的数据, 选择了使用lucas定理解决
lucas定理: (摘自百度)
我们令
那么:

代码可以递归的去实现这个过程, 其中递归终点为
时间

换成人话说就是

#include<iostream>
#include<algorithm>
using namespace std;

#define int long long

int qmi(int a,int k,int p) {
    int res = 1;
    while(k) {
        if(k&1)res = res*a%p;
        a = a*a%p;
        k>>=1;
    }
    return res;
}

int C(int a,int b,int p) {
    if(b>a)return 0;
    int res = 1;

    for(int i=1,j=a;i<=b;i++,j--) {
        res = res*j%p;
        res = res*qmi(i,p-2,p)%p;
    }
    return res;
}

int lucas(int a,int b,int p) {
    if(a<p && b<p) return C(a,b,p);
    return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}

signed main() {
    int n, a, b, c, d; cin >> n >> a >> b >> c >> d;
    int p = 998244353;
    // C_{n*n}^a*C_{n*n-a}^b*C_{n*n-a-b}^c
    int ans = lucas(n*n, a, p) * lucas(n*n-a, b, p) %p;
    ans *= lucas(n*n-a-b, c, p) %p;
    cout << ans % p << endl;

}
发表于 2022-03-13 08:38:26 回复(0)
炖蘑菇汤头像 炖蘑菇汤
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x = new int[4];
        x[0] = in.nextInt();
        x[1] = in.nextInt();
        x[2] = in.nextInt();
        x[3] = in.nextInt();
        Arrays.sort(x);
        int[][][][] dp = new int[x[0] + 2][x[1] + 2][x[2] + 2][x[3] + 2];
        fun(dp, x);
        System.out.println(dp[x[0] + 1][x[1] + 1][x[2] + 1][x[3] + 1]);
    }

    public static void fun(int[][][][] dp, int[] x) {
        int mod = 998244353;
        for (int i = 1; i <= x[0] + 1; i++) {
            if (i == 1) {
                dp[1][1][1][1] = 1;
            } else {
                dp[i][i][i][i] = (2 * dp[i - 1][i][i][i] % mod) * 2 % mod;
            }

            for (int m = i + 1; m <= x[3] + 1; m++) {
                dp[i][i][i][m] = ((2 * dp[i - 1][i][i][m] % mod + dp[i - 1][i][i][m]) % mod + dp[i][i][i][m - 1]) % mod;
            }
            for (int o = i + 1; o <= x[2] + 1; o++) {
                dp[i][i][o][o] = (2 * dp[i - 1][i][o][o] % mod + 2 * dp[i][i][o - 1][o] % mod) % mod;
                for (int p = o + 1; p <= x[3] + 1; p++) {
                    dp[i][i][o][p] = ((2 * dp[i - 1][i][o][p] % mod + dp[i][i][o - 1][p]) % mod + dp[i][i][o][p - 1]) % mod;
                }
            }
            for (int j = i + 1; j <= x[1] + 1; j++) {
                dp[i][j][j][j] = ((dp[i - 1][j][j][j] + dp[i][j - 1][j][j]) % mod + 2 * dp[i][j - 1][j][j] % mod) % mod;
                for (int m = j + 1; m <= x[3] + 1; m++) {
                    dp[i][j][j][m] = (2 * dp[i][j - 1][j][m] % mod + (dp[i - 1][j][j][m] + dp[i][j][j][m - 1]) % mod ) % mod;
                }
                for (int o = j + 1; o <= x[2] + 1; o++) {
                    dp[i][j][o][o] = ((dp[i - 1][j][o][o] + dp[i][j - 1][o][o]) % mod + 2 * dp[i][j][o - 1][o] % mod) % mod;
                    for (int m = o + 1; m <= x[3] + 1; m++) {
                        dp[i][j][o][m] = (((dp[i - 1][j][o][m] + dp[i][j - 1][o][m]) % mod + dp[i][j][o - 1][m]) % mod + dp[i][j][o][m - 1]) % mod;
                    }
                }
            }
        }
    }
}
发表于 2022-04-02 14:06:59 回复(0)
Java
momo_gogogo头像 momo_gogogo
题目没说范围，不如直接不讲武德使用BigInteger吧~ 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;


public class Main {
    static int mod = 998244353;

    public static void main(String[] args) throws InterruptedException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int N = s[0];
        int a = s[1];
        int b = s[2];
        int c = s[3];
        BigInteger t = cal(N * N - a - b - c + 1, N * N);
        BigInteger ka = cal(1, a);
        BigInteger kb = cal(1, b);
        BigInteger kc = cal(1, c);
        t = t.divide(ka.multiply(kb.multiply(kc)));
        t = t.mod(new BigInteger(mod + ""));
        System.out.println(t.toString());
    }

    public static BigInteger cal(int a, int b) {
        BigInteger t = new BigInteger(1 + "");
        for (int i = a; i <= b; i++) {
            t = t.multiply(new BigInteger(i + ""));
        }
        return t;
    }
}


发表于 2022-08-14 22:42:15 回复(0)
ccdesue头像 ccdesue
多重集排列公式
发表于 2022-02-13 11:53:15 回复(0)
牛Coding头像 牛Coding
求排列数问题，结果为：(N*N)!/(a!*b!*c!*d!)，使用逆元计算
编辑于 2021-05-31 10:35:29 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 阿里巴巴 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 信息技术岗 区块链 测试开发工程师 大数据开发工程师 数据分析师 Java工程师
上传者：小小
难度：
7条回答 6426浏览

热门推荐

通过挑战的用户

相关试题

视力表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号