2 条题解
-
0
houzhiyuan LV 6 @ 2021-12-15 19:19:57
考虑将可以买的价格放到这个矩阵中。
$$\begin{matrix}1&p+1&2p+1&\cdots&(k-1)p+1\\2&p+2&2p+2&\cdots&(k-1)p+2\\\vdots&\vdots&\vdots&\vdots&\vdots\\p&2p&3p&\cdots&kp\end{matrix} $$在这个矩阵中找 个数。
发现如果一列全部选，是可以满足条件的，这样的选法有 种。
如果选多列呢？
找到一种和为零的情况，找到第一个非空列，这样保证这列上选的数的个数 ，那么此时将这列向下循环移位一格，这样和就会加上 。
由于 是个质数，所以经过 次循环移位后得到的和都不相等，所以一种和为零的选多列的方案可以得到和为 的方案各一种。
假设和为 的方案数为 ，那么可以得到：
$$s_0-k=s_1=s_2=s_3=...=s_{p-1}\\ \sum s_i=C_{kp}^{p} $$直接算出 就是答案。
代码
#include<bits/stdc++.h> using namespace std; const int mod=998244353; int kuai(int a,int b){ int ans=1; for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod; return ans; } int C(int n,int m){ int ans=1; for(int i=1;i<=m;i++)ans=1ll*ans*i%mod; ans=kuai(ans,mod-2); for(int i=1;i<=m;i++)ans=1ll*ans*(n-i+1)%mod; return ans; } int _,p,k; int main(){ scanf("%d",&_); while(_--){ scanf("%d%d",&p,&k); printf("%d\n",(1ll*((C(1ll*p*k%mod,p)-k+mod)%mod)*kuai(p,mod-2)%mod+k)%mod); } }
- 1
信息
- ID
- 54
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者
-