Educational Codeforces Round 83 Div2

A.Two Regular Polygons
$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        puts(n%m?"NO":"YES");
    }
}

B.Bogosort
$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int main(){
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int>v(n,0);
        for(int i=0;i<n;i++)cin>>v[i];
        sort(v.begin(),v.end());
        for(int i=n-1;~i;i--)cout<<v[i]<<" ";O("");
    }
}

C.Adding Powers
$K$ 进制下每一位必须是 $0,1$ ，计算为 $1$ 的位是否大于1。

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int n,k;
int main(){
    int t;cin>>t;
    while(t--){
        sc("%d%d",&n,&k);
        int b[65]={0};bool f=1;
        for(int i=1;i<=n;i++){
            ll x;
            sc("%lld",&x);
            if(x==0)continue;
            int ans=0;
            while(x){
                if(x%k==0)ans++,x/=k;
                else if(x%k==1)b[ans++]++,x/=k;
                else {f=0;break;}
            }
        }
        for(int i=0;i<65&&f;i++)if(b[i]>1)f=0;
        puts(f?"YES":"NO");
    }
}

D.Count the Arrays
因为要求必须有一对数相同，所以先从 $m$ 个数里选 $n-1$ 个数， $C_{m}^{n-1}$ 。

选择一个数使得有一对数相同，首先不能和最大值相同所以只能从 $n-2$ 个数里选一个。

最后除了一对相同的数和最大值，其他 $n-3$ 个数可以选择放在最大值一边排好序，所以有 $2^{n-3}$ 种。

最后答案就是 $C_{m}^{n-1}\cdot (n-2)\cdot 2^{n-3}$

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.in","r",stdin);
#define OUT freopen("out.out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=998244353;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';puts("");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
template<const int N_,int M>
struct Cr{
    ll fac[N_],inv[N_];
    Cr(){
        fac[0]=1;
        for(int i=1;i<N_;i++)fac[i]=fac[i-1]*i%M;
        inv[N_-1]=::ksm(fac[N_-1],M-2,M);
        for(int i=N_-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%M;
    }
    ll operator()(int a,int b){
        if(a<b || a<0)return 0;
        return fac[a]*inv[a-b]%M*inv[b]%M;
    }
};
int main(){
    Cr<200005,mod> C;
    int n,m;
    cin>>n>>m;
    if(n==2)return O(0);
    return O(C(m,n-1)*(n-2)%mod*ksm(2,n-3,mod)%mod);
}

E.Array Shrinking
首先可以利用栈巧妙的算出区间 $[l,r]$ 内合并后剩余的数字个数，然后就是区间dp的模板。

$Code$

#include<bits/stdc++.h>
using namespace std;
int n;
int a[505],dp[505][505];
int t=0,s[505];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),dp[i][i]=1;
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;t=0;
            for(int k=l;k<=r;k++){
                int v=a[k];
                while(t&&s[t]==v)t--,v++;
                s[++t]=v;
            }
            dp[l][r]=t;
            for(int k=l;k<r;k++)dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
        }
    }
    printf("%d\n",dp[1][n]);
}