链接：https://ac.nowcoder.com/acm/contest/7079/B
来源：牛客网

题目描述

牛牛最近学习了取模是什么 于是他看到了下面这一道题：

多次询问：每次询问包含一个正整数 nnn 要求你输出下列结果
∏i=1n∑j=1i∑k=1ji×j×k\prod_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j i\times j\times k∏i=1n​∑j=1i​∑k=1j​i×j×k
为了避免结果过大 只需要输出这个式子对 199999199999199999（=2×32×41×271+1=2\times 3^2 \times 41 \times 271+1=2×32×41×271+1，一个质数） 取模的结果。
输入描述:

第一行一个正整数 TTT 表示询问次数。

接下来 TTT 行 每行一个正整数 nnn 含义如上所述

输出描述:

TTT 行非负整数 代表答案。

示例1
输入
复制

5
1
2
3
4
5

输出
复制

1
14
1050
73001
100955

说明

n=2 的情况：(111)(211+221+22*2) = 14

备注:

n≤10105n \leq 10{105}n≤10105

保证输入总长度 ≤5×105\leq 5 \times 10^5≤5×105 且 T≤105T \leq 10^5T≤105

---

感谢出题人@RainAir的解答\color{red}{感谢出题人@RainAir的解答}感谢出题人@RainAir的解答

题目: 给定公式∏i=1n∑j=1i∑k=1j(i∗j∗k)\prod_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}(i*j*k)∏i=1n​∑j=1i​∑k=1j​(i∗j∗k)，和n，求结果对199999取模的值

• 首先因为取模操作，当i从1枚举到20000时，出现了0，所以对于任何大于等于200000的n答案都是0
  上述公式可以化简
  ∏i=1n∑j=1i∑k=1j(i∗j∗k)=∏i=1ni∗(∑j=1ij∗(∑k=1jk))\prod_{i=1}^{n}\sum_{j=1}^{i}\sum_{k=1}^{j}(i*j*k)=\prod_{i=1}^{n}i*(\sum_{j=1}^{i}j*(\sum_{k=1}^{j}k)~~~)i=1∏n​j=1∑i​k=1∑j​(i∗j∗k)=i=1∏n​i∗(j=1∑i​j∗(k=1∑j​k))

• 可以预处理出k和j的前缀和后再预处理出i的前缀积即可

• 注意边界sumi[0] = 1

#ifdef debug#include <time.h>#include "win_majiao.h"#endif#include <iostream>#include <algorithm>#include <vector>#include <string.h>#include <map>#include <set>#include <stack>#include <queue>#include <stdlib.h>#include <math.h>#define MAXN ((int)2e5+7)#define ll long long int#define INF (0x7f7f7f7f)#define fori(lef, rig) for(int i=lef; i<=rig; i++)#define forj(lef, rig) for(int j=lef; j<=rig; j++)#define fork(lef, rig) for(int k=lef; k<=rig; k++)#define QAQ (0)using namespace std;#define show(x...) \do { \cout << "\033[31;1m " << #x << " -> "; \err(x); \} while (0)void err() { cout << "\033[39;0m" << endl; }template<typename T, typename... A>void err(T a, A... x) { cout << a << ' '; err(x...); }namespace FastIO{char print_f[105];void read() {}void print() { putchar('\n'); }template <typename T, typename... T2>inline void read(T &x, T2 &... oth) {x = 0;char ch = getchar();ll f = 1;while (!isdigit(ch)) {if (ch == '-') f *= -1; ch = getchar();}while (isdigit(ch)) {x = x * 10 + ch - 48;ch = getchar();}x *= f;read(oth...);}template <typename T, typename... T2>inline void print(T x, T2... oth) {ll p3=-1;if(x<0) putchar('-'), x=-x;do{print_f[++p3] = x%10 + 48;} while(x/=10);while(p3>=0) putchar(print_f[p3--]);putchar(' ');print(oth...);}} // namespace FastIOusing FastIO::print;using FastIO::read;int n, m, Q, K, sumi[MAXN], sumj[MAXN], sumk[MAXN];#define mod (199999)char str[MAXN];signed main() {#ifdef debugfreopen("test.txt", "r", stdin);clock_t stime = clock();#endiffor(int k=1; k<=mod; k++) sumk[k] = (sumk[k-1] + k) % mod;for(int j=1; j<=mod; j++) sumj[j] = ((sumj[j-1]%mod)+(1ll*j*sumk[j])%mod) % mod;sumi[0] = 1;for(int i=1; i<=mod; i++) {ll p = ((sumi[i-1]*1ll*i%mod) * (sumj[i]%mod)) % mod;sumi[i] = p;}// forarr(sumk, 1, 10);// forarr(sumj, 1, 10);scanf("%d ", &Q);while(Q--) {scanf("%s ", str);int len = strlen(str);if(len > 7) { printf("0\n"); continue ; }n = 0;for(int i=0; str[i]; i++)n = n * 10 + (str[i] - '0');if(n >= mod) { printf("0\n"); continue ; }printf("%d\n", sumi[n]);}#ifdef debugclock_t etime = clock();printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);#endif return 0;}

java代码

import java.io.*;import java.math.BigDecimal;import java.math.BigInteger;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;public class Main {public static final boolean debug = false;public static String INPATH = "C:\\Users\\majiao\\Desktop\\test.txt",OUTPATH = "C:\\Users\\majiao\\Desktop\\out.txt";public static StreamTokenizer tok;public static BufferedReader cin;public static PrintWriter cout;public static long start_time = 0, out_time = 0;public static int n, m, K, Q, MAXN = (int)2e5+7, INF = 0x3f3f3f3f;public static byte buf[] = new byte[MAXN];public static int sumi[] = new int[MAXN], sumj[] = new int[MAXN], sumk[] = new int[MAXN] ;public static int mod = 199999;public static void main(String[] args) throws IOException {main_init();if(debug) { start_time = System.currentTimeMillis(); }if(false) { System.setOut(new PrintStream(OUTPATH)); }if(false) {for(int k=1; k<=mod; k++)sumk[k] = (sumk[k-1] + k) % mod;for(int j=1; j<=mod; j++)sumj[j] = (int) (( (sumj[j-1]%mod) + (sumk[j]*1L*j) % mod) % mod);sumi[0] = 1;for(int i=1; i<=mod; i++) {long p = (((sumi[i-1]*i*1L) % mod) * (sumj[i]) % mod);sumi[i] = (int) p;}} else {for(int k=1; k<=mod; k++) sumk[k] = (sumk[k-1] + k) % mod;for(int j=1; j<=mod; j++) sumj[j] = (int) (((sumj[j-1]%mod)+(1l*j*sumk[j])%mod) % mod);sumi[0] = 1;for(int i=1; i<=mod; i++) {long p = ((sumi[i-1]*1l*i%mod) * (sumj[i]%mod)) % mod;sumi[i] = (int) p;}}Q = read_int();while(Q-- > 0) {String s = next_str();if(s.length() > 7) { cout.println('0'); continue; }n = Integer.parseInt(s);if(n > mod) { cout.println('0'); continue ; }cout.println(sumi[n]);}if(debug) {out_time = System.currentTimeMillis();cout.printf("run time : %d ms\n", out_time-start_time);}cout.flush();}public static void main_init() {try {if (debug) {cin = new BufferedReader(new InputStreamReader(new FileInputStream(INPATH)));} else {cin = new BufferedReader(new InputStreamReader(System.in));}cout = new PrintWriter(new OutputStreamWriter(System.out));// cout = new PrintWriter(OUTPATH);tok = new StreamTokenizer(cin);} catch (Exception e) {e.printStackTrace();}}public static String next_str() {try {tok.nextToken();if (tok.ttype == StreamTokenizer.TT_EOF)return null;else if (tok.ttype == StreamTokenizer.TT_NUMBER) {return String.valueOf((int)tok.nval);} else if (tok.ttype == StreamTokenizer.TT_WORD) {return tok.sval;} else return null;} catch (Exception e) {e.printStackTrace();return null;}}public static int read_int() { return Integer.parseInt(next_str()); }public static long read_long() { return Long.parseLong(next_str()); }public static double read_double() { return Double.parseDouble(next_str()); }public static BigInteger read_big() { return new BigInteger(next_str()); }public static BigDecimal read_dec() { return new BigDecimal(next_str()); }}