似乎好久没有写过模拟赛总结了
T1
problem
给出(n,k,m)，且满足(sumlimits_{i = 1}^k a_i = n),求所有可能的(sumlimits_{i = 1}^k {a_i}^m)
solution
考场写了个三维dp，(n^4)的dp，t了，得分20
考虑一个数对答案的贡献：他的数值( imes)他出现的次数。那么如何求他出现的次数呢？？
把问题转换成把(i)个球放在(j)个盒子里的方案数，每个盒子里球的数量就是我的(a_i),确定一个(x)，剩下的位置求方案数，就是他的方案数。
对于(1 ightarrow n)的所有数，他都可以出现(0 ightarrow k)次:
-
0次说明他对答案没贡献
-
对于出现次数多次(k)的情况，因为在(k-1)次的时候计算过一遍了，所以每次只需要加上方案数( imes {x}^m)
一些细节:
-
(i)个球放在(j)个盒子里的方案数：(f_{i,j} = f_{i,j-1}+f_{i-j,j})，如果我有至少一个空盒子，把空盒子设为我新加的盒子，就可以从(f_{i,j-1})转移，如果没有空盒子，在(j)个盒子里每个盒子先放上1个球，剩下的球再放在(j)个盒子里，就可以有空盒子了，可以从(f_{i-j,j})转移
-
因为(a_i)都为正整数，所以不允许有空盒子，和1的处理方式一样，现在每个盒子里都放上一个球，再求方案数
code
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-')x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 4e3+10,mod = 998244353;
int ans;
int n,k,m;
int qpow(int a,int kk){
int res = 1;a = a%mod;
while (kk){
if (kk&1) res = res*a%mod;
a = a*a%mod;
kk>>=1;
}
return res;
}
int f[maxn][maxn],fac[maxn];
signed main(){
n = read(),k = read(),m = read();
for (int i = 0;i <= k;i++) f[0][i] = 1;
for (int i = 1;i <= n;i++){
for (int j = 1;j <= k;j++){
(f[i][j] = f[i][j-1])%=mod;
if (i-j >= 0) (f[i][j] += f[i-j][j])%=mod;
}
}
for (int i = 1;i <= n;i++) fac[i] = qpow(i,m);
for (int i = 1;i <= n;i++){
for (int j = 1;j <= k;j++){
int res = 0;
if (n-j*i-k+j >= 0) (res += f[n-j*i-k+j][k-j])%=mod;
(ans += res*fac[i])%=mod;
}
}
printf("%lld
",ans);
return 0;
}
T3
solution
枚举点集，再枚举边，看是否与被删的点有关系，统计答案，暴力30
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int maxn = 3005,mod = 1e9+7;
int n,m,k;
struct node{
int to,from;
}ed[maxn*2];
int qpow(int a,int kk){
int res = 1;a = a%mod;
while (kk){
if (kk&1) res = res*a%mod;
a = a*a%mod;
kk>>=1;
}
return res%mod;
}
int vis[maxn][maxn],ans,ins[maxn];
signed main(){
freopen("cubes.in","r",stdin);
freopen("cubes.out","w",stdout);
int ans = 0;
n = read(),m = read(),k = read();
for (int i = 1;i <= m;i++){
ed[i].from = read(),ed[i].to = read();
}
for (int i = 0;i < (1<<(n+1));i++){
int res = m;
for (int j = 1;j <= m;j++){
if (((1<<ed[j].from)&i)||((1<<ed[j].to)&i)) res--;
}
ans += qpow(res,k);
}
printf("%lld
",ans/2);
return 0;
}
T4
solution
猜的结论，当(m=1)的情况，答案为({left(frac{n imes (n-1)}{2} ight)}^k)，得分10
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define int long long
using namespace std;
int read(){
int x = 1,a = 0;char ch = getchar();
while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();}
while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();}
return x*a;
}
const int mod = 998244353;
int n,m,k;
int qpow(int a,int kk){
int res = 1;a = a%mod;
while (kk){
if (kk&1) res = res*a%mod;
a = a*a%mod;
kk>>=1;
}
return res%mod;
}
signed main(){
freopen("box.in","r",stdin);
freopen("box.out","w",stdout);
n = read(),m = read(),k = read();
if (m==1) printf("%lld
",qpow(n*(n-1)/2,k)%mod);
}