B. 牛牛的算术题解

推一下柿子就好了：

$\prod_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j ijk=\prod_{i=1}^ni\sum_{j=1}^ij\sum_{k=1}^jk=\prod_{i=1}^ni\sum_{j=1}^ij\times\frac {j(j+1)} 2$

令 $s[n]=\sum_{i=1}^n i\times \frac {i(i+1)}2$ ，代入得：

$\prod_{i=1}^n i\times s[i]$

可以发现，当 $n\geq 199999$ 时答案肯定为 $0$ ，所以只需要考虑 $n<199999$ 的情况。那么这个东西也像上面预处理出来就可以 $O(1)$ 回答询问了，代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000010
#define mod 199999

int T,n;
char s[maxn];
int sum[maxn],prod[maxn],inv2=(mod+1)/2;

int main()
{
    for(int i=1;i<=maxn-10;i++)sum[i]=(sum[i-1]+1ll*i*i%mod*(i+1)%mod*inv2%mod)%mod;
    prod[0]=1;for(int i=1;i<=maxn-10;i++)prod[i]=1ll*prod[i-1]*i%mod*sum[i]%mod;
    scanf("%d",&T);while(T--)
    {
        scanf("%s",s+1);int m=strlen(s+1);
        if(m>6){printf("0\n");continue;}
        n=0;for(int i=1;i<=m;i++)n=n*10+s[i]-'0';
        printf("%d\n",prod[n]);
    }
}

B. 牛牛的算术 题解

B. 牛牛的算术题解