“科大讯飞杯”第十七届同济大学程序设计预选赛

A
根据更相减损术可得，gcd(x,y)=gcd(x,x-y)=gcd(x+y,x)
而题意中从集合选取的数字正好满足这个意思。
所以刚开始两个人取得数字就是x，y算出来的gcd(x,y)，就是等差数列的公差，
那么算出来等差数列的项数，判断奇偶即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        int n,a,b;cin>>n>>a>>b;
        int gcd=__gcd(a,b);
        int num=n/gcd;
        if(num&1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

B
直接字符串模拟即可。

#include<bits/stdc++.h>
using namespace std;
int a[5005];
char s[5005][5005];
int main(){
    int num=1;
    char c;
    while(c=getchar()){
        if(c=='\n') break;
        if(c=='+'){
            num++;
            continue;
        }
        s[num][++a[num]]=c;
    }
    long long  ans=0;
    for(int i=1;i<=num;i++){
        long long d=0,f=0;
        int flag=0;
        for(int j=1;j<=a[i];j++){
            if(s[i][j]=='d'){
                flag=1;
                continue;
            }
            if(!flag){
               d=d*10+s[i][j]-'0';
            }
            else f=f*10+s[i][j]-'0';
        }
        //cout<<i<<" "<<d<<" "<<f<<endl;
        if(flag){
            ans+=d*(1+f)*5;
        }
        else ans+=d*10;
    }
    if(ans%10==5){
        cout<<ans/10<<".5";
    }
    else cout<<ans/10;

    return 0;
}

C
考虑一下，对于一段区间[l,r]肯定是先走完最优，那么有个问题就是说终点是在l，还是在r。
所以用三维dp。
dp[i][j][0/1]表示走完区间i到j这一段，终点在左(0)/右(1)的最少时间是多少。
那么容易得到有四个转移方程。
对于区间l到r，可能是由[l+1,r]过来，也可能由[l,r-1]过来，而且还有终点位置是在左边和右边的区别。
转移时候注意当前所用时间不大于给定到达该点的时间限制才能转移。
最后min(dp[1][n][0],dp[1][n][1])就是答案。

#include<bits/stdc++.h>
using namespace std;
int dp[1005][1005][2];
int a[1005],b[1005];
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    int q;
    for(int i=1;i<=n;i++){
        cin>>b[i];
        if(!b[i]) q=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            dp[i][j][0]=dp[i][j][1]=1e9;
        }
    }
    dp[q][q][0]=dp[q][q][1]=0;
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            int t=dp[l+1][r][0]+a[l+1]-a[l];
            if(t<=b[l]) dp[l][r][0]=min(dp[l][r][0],t);
            t=dp[l+1][r][1]+a[r]-a[l];
            if(t<=b[l]) dp[l][r][0]=min(dp[l][r][0],t);

            t=dp[l][r-1][0]+a[r]-a[l];
            if(t<=b[r]) dp[l][r][1]=min(dp[l][r][1],t);
            t=dp[l][r-1][1]+a[r]-a[r-1];
            if(t<=b[r]) dp[l][r][1]=min(dp[l][r][1],t);

        }
    }
    int ans=min(dp[1][n][0],dp[1][n][1]);
    if(ans==1e9) ans=-1;
    cout<<ans;
    return 0;
}

D
数据范围很小。直接dfs即可。
对于每层dfs，用时间来区分每一层。每一层选择任意一辆车的任意一个方向即可。
最多有4辆车，每辆车有4个方向可以走，复杂度为O(16^k)

#include<bits/stdc++.h>
using namespace std;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
vector<pair<int,int>> v;
int w,h,k,flag;
int qqq;
char mp[15][15];
bool check(int x,int y){

    if(x<0 || x>=h || y<0 || y>=w || mp[x][y]=='X' || mp[x][y]=='R') return 0;
    return 1;
}
void dfs(int now){
    if(flag || now>k) return ;
    for(int i=0;i<v.size();i++){
        for(int j=0;j<4;j++){
            pair<int,int> t=v[i];
            int x=v[i].first,y=v[i].second;
            qqq++;
            while(check(x+dx[j],y+dy[j])) x+=dx[j],y+=dy[j];
            if(mp[x][y]=='D'){
                flag=1;return ;
            }
            swap(mp[x][y],mp[v[i].first][v[i].second]);
            v[i]={x,y};
            dfs(now+1);
            if(flag) return ;
            v[i]=t;
            swap(mp[x][y],mp[v[i].first][v[i].second]);
        }
    }
}
int main(){
    cin>>w>>h>>k;
    for(int i=0;i<h;i++){
        cin>>mp[i];
        for(int j=0;j<w;j++){
            if(mp[i][j]=='R'){
                v.push_back({i,j});
            }
        }
    }
    dfs(1);
    cout<<qqq<<endl;
    puts(flag?"YES":"NO");
    return 0;
}

E
所有的选择方案数有
什么意思呢？就是每次选择两个点去配对。分子很容易得到是这样。但是考虑一下这样是有重复的。
比如
开始选择第一个点和第三个点配对 最后选择第二个点和第四个点配对 与
开始选择第二个点和第四个点配对 最后选择第一个点和第三个点配对
这是属于同一种方案。
那么其实应该除以一个n的阶乘，表示与这n次的选择的顺序无关
至于可行的方案数，这其实就是卡特兰数的经典应用之一。
可以参考下面博客学习下
https://www.cnblogs.com/ibilllee/p/9552148.html
卡特兰数为
两式相比化简可以得到答案为

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
int main(){
    int n;cin>>n;
    ll ans=1;
    for(int i=1;i<=n+1;i++){
        ans=ans*i%mod;
    }
    cout<<qpow(2,n)*qpow(ans,mod-2)%mod;
    return 0;
}

F
对每个区间差分后进行一个前缀和。对于出现次数多的位置给的数越大，结果自然越大。
排序后计算即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[1<<18];
int main(){
    int n,m;cin>>n>>m;
    while(m--){
        int l,r;cin>>l>>r;
        a[l]++,a[r+1]--;
    }
    for(int i=1;i<=n;i++) a[i]+=a[i-1];
    sort(a+1,a+1+n,greater<ll>());
    ll ans=0;
    for(int i=1,j=n;i<=n;i++){
        if(a[i]) ans+=a[i]*j,j--;
    }
    cout<<ans;
    return 0;
}

J
上个BM板子把前几项塞进去即可

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i(a);i<=(b);++i)
#define FOL(i,a,b) for(int i(a);i>=(b);--i)
#define SZ(x) ((long long)(x).size())
#define REW(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const ll Mod (998244353) ;

ll powEx(ll base,ll n,ll Mod = ::Mod )
{
    ll ret(1);
    while(n){
        if(n&1) ret = ret*base%Mod ;
        base = base * base %Mod ;
        n >>= 1 ;
    }
    return ret % Mod ;
}

class Linear_Seq
{
using VI = vector<ll> ;
public:
    static const int N=10010;
    ll res[N],base[N],c[N],md[N];
    vector<int> Md;
    inline void mulEx(ll *a,ll *b,int k) {
        for(int i(0);i<k+k;++i) c[i]=0;
        for(int i(0);i<k;++i)if(a[i])for(int j(0);j<k;++j)
            c[i+j]=(c[i+j]+a[i]*b[j])%Mod;
        for (int i(k+k-1);i>=k;--i) if (c[i])for(int j(0);j<Md.size();++j)
            c[i-k+Md[j]]=(c[i-k+Md[j]]-c[i]*md[Md[j]])%Mod;
        copy(c,c+k,a) ;
    }
    int solve(ll n,VI a,VI b) { // a 系数 b 初值 b[n+1]=a[0]*b[n]+...
        ll ans(0),cnt(0);
        int k(a.size());
        for(int i(0);i<k;++i) md[k-1-i]=-a[i];
        md[k]=1 ;  Md.clear() ;
        for(int i(0);i<k;++i) if (md[i]) Md.push_back(i);
        for(int i(0);i<k;++i) res[i] = base[i] = 0;
        res[0]=1;
        while ((1LL<<cnt)<=n) ++ cnt;
        for (int p(cnt);~p;-- p) {
            mulEx(res,res,k);
            if ((n>>p)&1) {
                for (int i(k-1);~i;--i) res[i+1]=res[i];res[0]=0;
                for(int j(0);j<Md.size();++j)
                    res[Md[j]]=(res[Md[j]]-res[k]*md[Md[j]])%Mod;
            }
        }
        for(int i(0);i<k;++i) ans=(ans+res[i]*b[i])%Mod;
        return ans+(ans<0?Mod:0);
    }
    VI BM(VI s) {
        VI ret(1,1),B(1,1);
        int L(0),m(1),b(1);
        for(int n(0);n<s.size();++n) {
            ll d(0);
            for(int i(0);i<=L;++i)
                d=(d+(ll)ret[i]*s[n-i])%Mod;
            if (!d) ++m;
            else if (2*L<=n) {
                VI T=ret;
                ll c(Mod-d*powEx(b,Mod-2)%Mod);
                while (ret.size()<B.size()+m) ret.push_back(0);
                for (int i(0);i<B.size();++i)
                    ret[i+m]=(ret[i+m]+c*B[i])%Mod;
                L=n+1-L; B=T; b=d; m=1;
            } else {
                ll c(Mod-d*powEx(b,Mod-2)%Mod);
                while (ret.size()<B.size()+m) ret.push_back(0);
                for(int i(0);i<B.size();++i)
                    ret[i+m]=(ret[i+m]+c*B[i])%Mod;
                ++m;
            }
        }
        return ret;
    }
    inline static void extand(VI &a, size_t d, ll value = 0) {
        if (d <= a.size()) return;
        a.resize(d, value);
    }

    inline static ll gcdEx(ll a, ll b, ll&x, ll& y)
    {
        if(!b) {x=1;y=0;return a;}
        ll d = gcdEx(b,a%b,y,x);
        y -= (a/b)*x;
        return d;
    }


    static ll CRT(const VI &c, const VI &m) {
        int n(c.size());
        ll M(1), ans(0);
        for (int i = 0; i < n; ++i) M *= m[i];
        for (int i = 0; i < n; ++i) {
            ll x,y,tM(M / m[i]);
            gcdEx(tM, m[i], x, y);
            ans = (ans + tM * x * c[i] % M) % M;
        }
        return (ans + M) % M;
    }

    static VI ReedsSloane(const VI &s, ll Mod) {
        auto Inv = [](ll a, ll Mod) {
            ll x, y;
            return gcdEx(a, Mod, x, y)==1?(x%Mod+Mod)%Mod:-1;
        };
        auto L = [](const VI &a, const VI &b) {
            int da = (a.size()>1||(a.size()== 1&&a[0]))?a.size()-1:-1000;
            int db = (b.size()>1||(b.size()== 1&&b[0]))?b.size()-1:-1000;
            return max(da, db + 1);
        };
        auto prime_power = [&](const VI &s, ll Mod, ll p, ll e) {
            // linear feedback shift register Mod p^e, p is prime
            vector<VI> a(e), b(e), an(e), bn(e), ao(e), bo(e);
            VI t(e), u(e), r(e), to(e, 1), uo(e), pw(e + 1);;
            pw[0] = 1;
            for (int i(pw[0] = 1); i <= e; ++i) pw[i] = pw[i - 1] * p;
            for (ll i(0); i < e; ++i) {
                a[i] = {pw[i]}; an[i] = {pw[i]};
                b[i] = {0}; bn[i] = {s[0] * pw[i] % Mod};
                t[i] = s[0] * pw[i] % Mod;
                if (!t[i]) {t[i] = 1; u[i] = e;}
                else for (u[i] = 0; t[i] % p == 0; t[i] /= p, ++u[i]);
            }
            for (size_t k(1);k < s.size(); ++k) {
                for (int g(0); g < e; ++g) {
                    if (L(an[g], bn[g]) > L(a[g], b[g])) {
                        ao[g] = a[e-1-u[g]];
                        bo[g] = b[e-1-u[g]];
                        to[g] = t[e-1-u[g]];
                        uo[g] = u[e-1-u[g]];
                        r[g] = k - 1;
                    }
                }
                a = an; b = bn;
                for (int o(0); o < e; ++o) {
                    ll d(0);
                    for (size_t i(0); i < a[o].size() && i <= k; ++i)
                        d = (d + a[o][i] * s[k - i]) % Mod;
                    if (d == 0) {t[o] = 1;u[o] = e;}
                    else {
                        for (u[o]=0, t[o]=d;!(t[o]%p);t[o]/=p ,++u[o]);
                        int g (e-1-u[o]);
                        if (!L(a[g], b[g])) {
                            extand(bn[o], k + 1);
                            bn[o][k] = (bn[o][k] + d) % Mod;
                        } else {
                            ll coef = t[o]*Inv(to[g],Mod)%Mod*pw[u[o]-uo[g]]%Mod;
                            int m(k-r[g]);
                            extand(an[o],ao[g].size()+m);
                            extand(bn[o],bo[g].size()+m);
                            for (size_t i(0);i < ao[g].size(); ++i) {
                                an[o][i+m] -= coef*ao[g][i]%Mod;
                                if (an[o][i + m]<0) an[o][i+m] += Mod;
                            }
                            while (an[o].size() && !an[o].back()) an[o].pop_back();
                            for (size_t i(0); i < bo[g].size(); ++i) {
                                bn[o][i+m] -= coef*bo[g][i]%Mod;
                                if (bn[o][i + m] < 0) bn[o][i + m] -= Mod;
                            }
                            while (bn[o].size()&& !bn[o].back()) bn[o].pop_back();
                        }
                    }
                }
            }
            return make_pair(an[0], bn[0]);
        };
        vector<tuple<ll, ll, int> > fac;
        for (ll i(2); i*i <= Mod; ++i)
            if (!(Mod % i)) {
                ll cnt(0),pw(1);
                while (!(Mod % i)) {Mod /= i; ++cnt; pw *= i;}
                fac.emplace_back(pw, i, cnt);
            }
        if (Mod > 1) fac.emplace_back(Mod, Mod, 1);
        vector<VI> as;
        size_t n = 0;
        for (auto &&x: fac) {
            ll Mod, p, e;
            VI a, b;
            std::tie(Mod, p, e) = x;
            auto ss = s;
            for (auto &&x: ss) x %= Mod;
            std::tie(a, b) = prime_power(ss, Mod, p, e);
            as.emplace_back(a);
            n = max(n, a.size());
        }
        VI a(n),c(as.size()),m(as.size());
        for (size_t i(0); i < n; ++i) {
            for (size_t j(0); j < as.size(); ++j) {
                m[j] = std::get<0>(fac[j]);
                c[j] = i < as[j].size() ? as[j][i] : 0;
            }
            a[i] = CRT(c, m);
        }
        return a;
    }
    ll solve(VI a,ll n,ll Mod,bool prime=true) {
        VI c;
        //if(prime)
           c = BM(a);
        //else c = ReedsSloane(a,Mod);
        c.erase(c.begin());
        for(int i(0);i<c.size();++i) c[i] = (Mod-c[i])%Mod;
        return solve(n,c,VI(a.begin(),a.begin()+c.size()));
    }
}BM;
typedef long long ll;
ll f[300005];
ll sum;
ll a[1005];
int main()
{
    ll n,k;cin>>n>>k;
    f[1]=f[2]=1;
    vector<ll> v;
    for(int i=3;i<=500;i++) f[i]=(f[i-1]+f[i-2])%Mod;

    for(int i=1;i<=500;i++){
        sum=(sum+powEx(i,k,Mod)*f[i]%Mod)%Mod;
        v.push_back(sum);
    }
    printf("%lld\n",BM.solve(v,n-1,Mod,false));

    return 0;
}