余数之和

给出正整数 n 和 k，计算 j(n,k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n 的值。

例如j(5,3) = 3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5 = 0 + 1 + 0 + 3 + 3 = 7。

输入格式

输入仅一行，包含两个整数 n,,k。

输出格式

输出仅一行，即 j(n,k)。

数据范围

1≤n,k≤10^9

输入样例

5 3

输出样例

7

思路：

整除分块：

(它喵的，不知道别人网站里的公式可以复制，自己学了半天mathjax语法)

$\lfloor x \rfloor$表示对x向下取整，通过打表可以发现n/i会有多个相等的区间，区间的右端点即为n/(n/i),则整除分块的代码为：

1
2
3
4
for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
	ans+=(r-l+1)*(n/l);
}

而本题的答案为

只要通过等差数列求和公式就能推出每个区间要减去(k/l)(r-l+1)(l+r)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() 
{
    ll n,k;
    scanf("%lld%lld",&n,&k);
    ll ans=n*k;
    for(ll l=1,r;l<=n;l=r+1) {
        if(k/l!=0) r=min(k/(k/l),n); 
        else r=n;
        ans-=(k/l)*(r-l+1)*(l+r)/2;
    }
    printf("%lld",ans);
    return 0;
}

Matrix

Fill an n×n matrix with numbers in [1,n2], where each number occurs exactly once.

For a fixed number filling method, let ai be the mininum number in the iith row, and S={a1,a2,…,an}∩{1,2,…,n}.

You need to calculate ∑|S|(mod998244353), i.e. the sum of the size of S over all possible methods.

Input

This problem contains multiple test cases.

The first line contains a single integer T (1≤T≤30).

Then T cases follow, each of which contains a single interger n (1≤n≤5000).

Output

For each test case, output one line contains the value of ∑|S|(mod998244353)

input

1
2
1
2

output

1
40

思路：
考虑每一个数的贡献，比如1可以作为贡献的方案数就是n C(n n-1,n-1)
其中组合数部分表示1作为该行的最小值出现，选择剩下的数的方案数；n表示该行可以出现在1-n里任意一行。
最后还要乘n ! ∗ ( n * n − n ) !，前者表示1所在行的所有数都可以全排列一遍，后者表示剩下的数可以全排列,然后累加出1 − n的贡献

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 25000001;
const int mod = 998244353;
 
ll qpow(ll a, ll b, ll p)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
 
ll fac[maxn];
void init()
{
    fac[0] = 1;
    for (int i = 1; i < maxn; i++)
    {
        fac[i] = fac[i - 1] * i % mod;
    }
}
ll infac(ll x)
{
    return qpow(x, mod - 2, mod);
}
ll C(ll n, ll m)
{
    if (n < m)
        return 0;
    return fac[n] * infac(fac[m]) % mod * infac(fac[n - m]) % mod;
}
int main()
{
    init();
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        ll n;
        scanf("%lld", &n);
        ll ans = n * fac[n] % mod * fac[n * n - n] % mod;
        ll sum = 0;
        for (int i = 1; i <= n; i++)
        {
            sum += C(n * n - i, n - 1);
            sum = sum % mod;
        }
        printf("%lld\n", ans * sum % mod);
    }
    return 0;
}