Warning: session_start(): open(/tmp/sess_e5584893d33a859abf7fb1d72b1a4cba, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2020牛客暑期多校训练营（第七场） ====== [[https://ac.nowcoder.com/acm/contest/5672|比赛网址]] ===== 训练结果 ===== * 时间:‘’2020-08-01 12:00~17:00’’ * rank:‘’196/1090’’ * 完成情况：‘’3/3/10’’ ===== 题解 ===== ===== B.Mask Allocation ===== === 题意 === 有 $n \times m$ 个物品，让你给一个划分方案，使得既能分成 $n$ 组 $m$ 个又能分成 $m$ 组 $n$ 个 === 题解 === 发现最优划分类似于 gcd 的做法，若 $n


#include
#include
#include
#include
#define ll long long
using namespace std;
int read()
{
    int k=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
int T,n,m,tot,ans[100055];
void solve(int x,int y)
{
    if(x>y) swap(x,y);
    if(!x) return;
    int res=y/x*x;
    for(int i=1;i<=res;i++)
        ans[++tot]=x;
    solve(y%x,x);
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    for(T=read();T;T--)
    {
        n=read();m=read();
        tot=0;solve(n,m);
        sort(ans+1,ans+1+tot,cmp);
        printf("%d\n",tot);
        for(int i=1;i<=tot;i++)
            printf("%d ",ans[i]);
        puts("");
    }
    return 0;
}

===== D.Fake News ===== === 题意 === 问平方和是否为完全平方数 === 题解 === 开始用python写高精度结果T了（人家用cin都T了更何况py），打了个表发现就只有1和24满足 ===== H.Dividing ===== === 题意 === 一下数对是合法的 1、$(1,k)$是合法的 2、如果$(n,k)$合法，那么$(n+k,k)$合法 3、如果$(n,k)$合法，那么$(nk,k)$合法给定范围$n,k \leq 10^{12}$，求范围内所有合法的数对 === 题解 === 容易发现$k$是不变的，那么只需对每个$k$求出$n$的个数容易发现所有$(1+tk,k)$都是合法的除此之外所有合法的必然是$k$的倍数，而且$k$的倍数一定能被凑出来因此合法的只有$(tk,k)$和$(1+tk,k)$其中$t$为非负整数只需要整除分块即可记得特判$n,k$分别为$1$的情况= =


#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair(a,b)
#define cp pair
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f,P = 1000000007;
inline LL read(){
    LL out = 0,flag = 1; char c = getchar();
    while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
    while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
    return flag ? out : -out;
}
LL N,K,ans = 0;
int main(){
    cin >> N >> K;
    if (K == 1){cout << N % P << endl; return 0;}
    if (N == 1){cout << K % P << endl; return 0;}
    ans = (N + N + K - 2) % P;
    for (LL i = 3,nxt; i <= K && i <= N; i = nxt + 1){
        nxt = N / (N / i);
        if (nxt > K) nxt = K;
        ans = (ans + 1ll * (N / i) % P * ((nxt - i + 1) % P) % P) % P;
    }
    N--;
    for (LL i = 3,nxt; i <= K && i <= N; i = nxt + 1){
        nxt = N / (N / i);
        if (nxt > K) nxt = K;
        ans = (ans + 1ll * (N / i) % P * ((nxt - i + 1) % P) % P) % P;
    }
    N++;
    ans = (ans % P + P) % P;
    cout << ans << endl;
    return 0;
}

===== I.Valuable Forests ===== === 题意 === 定义一个无根树的权值为所有点的度数的平方的和，求有标号的$n$个点形成的所有森林的权值的和。 === 题解 === 设$f[i]$表示$i$个带标号的节点有多少种不同的森林，递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献，递推式子为：$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$ 那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$


#include
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair PII;
#define X first
#define Y second
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=5010;
int T;
LL MOD,c[maxn][maxn],w[maxn],f[maxn],ans[maxn];
LL quickpow(LL a,int N)
{
    if(N<=0)return 1; 
    LL res=1,tmp=a;
    while(N)
    {
        if(N&1)res=(res*tmp)%MOD;
        tmp=(tmp*tmp)%MOD;
        N>>=1;
    }
    return res;
} 
int main()
{
    T=read();MOD=read();
    for(int i=0;i<=5000;i++)c[i][0]=1;
    for(int i=1;i<=5000;i++)
        for(int j=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD; 
    for(int i=3;i<=5000;i++)
    {
        w[i]=i;
        for(int d=1;d<=(i-1);d++)w[i]=(w[i]*d*d%MOD*c[i-2][d-1]%MOD*quickpow(i-1,i-1-d))%MOD;
    }
    printf("here");
    f[0]=1;f[1]=1;f[2]=2;
    for(int i=3;i<=5000;i++)
        for(int j=1;j<=i;j++)
            f[i]=(f[i]+c[i][j]*f[i-j]%MOD*quickpow(j,j-2)%MOD)%MOD;
    ans[1]=0;ans[2]=2;
    for(int i=3;i<=5000;i++)
        for(int j=1;j<=i;j++)
            ans[i]=(ans[i]+c[i][j]*(quickpow(j,j-2)*ans[i-j]%MOD+f[i-j]*w[j]%MOD)%MOD)%MOD;
    while(T--)printf("%lld\n",ans[read()]);
    return 0;
}

===== 训练实况 ===== 0~1:40 过三题之后垃圾时间 ===== 训练总结 ===== wxg: 这场发挥很差，c一直执着于一个错误算法。 hxm:菜是原罪，$H$调了很久才调出来特判没判，$A$是模拟退火而却不能正确写对 fyh:J是真的读不懂题，第一英语差，第二额是本身对指针，对象之类的玩意不熟悉。以后帮队友调题的时候要注意几点：特殊情况（n=1等等是否取模！！）