牛客：牛牛的算术（线性递推）

题意：

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

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

多次询问：每次询问包含一个正整数 $∏i=1n∑j=1i∑k=1ji×j×kprod_{i=1}^n sum_{j=1}^i sum_{k=1}^j i imes j imes k∏i=1n∑j=1i∑k=1ji×j×k 为了避免结果过大只需要输出这个式子对 199999199999199999（=2×32×41×271+1=2 imes 3^2 imes 41 imes 271+1=2×32×41×271+1，一个质数）取模的结果。$

$题解：$

$线性递推一下，答案从n-1到n之间的转移应该是比较显然的。$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
const int mod=199999;
typedef long long ll;
int t;
int n;
ll ans[maxn];
ll f[maxn];
ll tt[maxn];

int main () {
    ans[0]=1;
    for (int i=1;i<maxn;i++) {
        f[i]=f[i-1]+i;
        f[i]%=mod;
        tt[i]=tt[i-1]+i*f[i]%mod;
        tt[i]%=mod;
        ans[i]=ans[i-1]*tt[i]%mod*i;
        ans[i]%=mod;
    }
    int t;
    scanf("%d",&t);
    while (t--) {
        string s;
        cin>>s;
        if (s.size()>6) {
            printf("0
");
            continue;
        }
        n=0;
        for (int i=0;i<s.size();i++) n=n*10+s[i]-'0';
        if (n>=199999) {
            printf("0
");
            continue;
        }
        printf("%lld
",ans[n]);
        //for (int i=1;i<=n;i++) printf("%d
",cnt[i]);
    }
}