代码保存板块

P2401 不等数列

#include<iostream>
using namespace std;
const int MAXN=1e3+10;
const int mod=2015;
int f[MAXN][MAXN];
int n,k;
int main(){
	cin>>n>>k;
	f[1][0]=1;
	for(int i=2;i<=n;i++){
		f[i][0]=1;
		for(int j=1;j<=k;j++){
			f[i][j]=(f[i-1][j-1]*(i-j)%mod+f[i-1][j]*(j+1)%mod)%mod;
		}
	}
	cout<<f[n][k]<<"\n";
	return 0;
}

CF510D Fox And Jumping

#include<bits/stdc++.h>
#include<map>
using namespace std;
const int MAXN=305;
int l[MAXN],c[MAXN];
map<int,int>mp;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>l[i];
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		for(pair<int,int> x:mp){
			int cnt=__gcd(l[i],x.first),v=x.second+c[i];
            if(mp[cnt]==0) mp[cnt]=v; else mp[cnt]=min(mp[cnt],v);
		}
	    if(mp[l[i]]==0)mp[l[i]]=c[i];
        else mp[l[i]]=min(mp[l[i]],c[i]);
	}
	if(mp[1]==0)cout<<-1<<"\n";
    else cout<<mp[1]<<"\n";
	return 0;
}

CF687B Remainders Game

#include<iostream>
using namespace std;
#define ll long long
const ll MAXN=1e6+10;
ll n,k;
ll gcd(int a,int b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}
int main(){
	cin>>n>>k;
//	for(ll i=1;i<=n;i++)cin>>a[i];
	ll x=1,y;
	for(ll i=1;i<=n;i++){
		scanf("%lld",&y);
		x=lcm(x,y)%k;
	}
	if(x%k==0)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

P3052 [USACO12MAR] Cows in a

#include <iostream>
#include <string.h>
using namespace std;
int n, m, c[19], tot(0), ans(0), v[19];
bool dfs(int x, int num){
    for (int i = 1; i <= x && i <= num; ++i){
            if (v[i] + c[x] <= m){
            v[i] += c[x];
            if (x == n){
                return 1;
            }
            if (dfs(x + 1, num)){
                return 1;
            }
            v[i] -= c[x];
        }
    }

    return 0;
}
int main(){
    cin>>n>>m;
    for (int i = 1; i <= n; i++)cin>>c[i];
    for (int i = 1; i <= n; i++){
        memset(v, 0,sizeof(v));
        if (dfs(1, i)){
            cout<<i<<"\n";
            break;
        }
    }
    return 0;
}

P5520 [yLOI2019] 青原樱

#include<iostream>
using namespace std;
int a,b,c,d;
int main(){
  cin>>a>>b>>c>>d;
  b=b-c+1; 
  int ans=1;
  for (int i=b-c+1;i<=b;i++){
    ans=1ll*ans*i%d;
  }
  cout<<ans<<"\n";
  return 0;
}

P1641 [SCOI2010] 生成字符串

#include<iostream>
using namespace std;
#define ll long long
const int mod=20100403;
ll n,m,ret,dv;
void tim(ll &bes,ll x){
	bes=(bes*x)%mod;
}
ll pow(ll bes,ll x){
	ll ans=1;
	for(;x;x>>=1){
		if(x&1)tim(ans,bes);
		tim(bes,bes);
	}
	return ans;
}
void c(){
	for(int i=n+1;i<=n+m;i++){
		tim(ret,i);
	}for(int i=1;i<=m;i++)tim(dv,i);
}
int main(){
	cin>>n>>m;
	dv=n+1;
	ret=dv-m;
	c();	
	ret=(ret*pow(dv,mod-2))%mod;
	cout<<ret<<"\n";
	return 0;
}

P3390 【模板】矩阵快速幂

#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const ll mod=1000000007;
int n;
struct Matrix{
    ll a[105][105];
    Matrix operator * (const Matrix &xi)const{
        Matrix res;
        for (int i=1;i<=n;i++){
        	for (int j=1;j<=n;j++){
                res.a[i][j]=0;
                for (int ke=1;ke<=n;ke++)
                    res.a[i][j]=(res.a[i][j]+a[i][ke]*xi.a[ke][j])%mod;
            }
		}
        return res;
    }
}xi,ans;
int main(){
    ll ke;
    cin>>n>>ke;
    if(n==3&&ke==0){
    	printf("1 0 0\n0 1 0\n0 0 1");
    	return 0;
	}
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=n;j++){
        	scanf("%d",&xi.a[i][j]);
		}
	}    
    ans=xi,ke--;
    while (ke){
        while((ke&1ll)==0) xi=xi*xi,ke>>=1ll;
        ans=ans*xi;
        ke>>=1ll,xi=xi*xi;
    }
    for (int i=1;i<=n;i++){
        printf("%d",ans.a[i][1]);
        for (int j=2;j<=n;j++)printf(" %d",ans.a[i][j]);
        printf("\n");
    }
    return 0;
}

P1611 循环的数字

#include<iostream>
using namespace std;
long long ans;
int k[7]={1,10,100,1000,10000,100000,1000000};
int a,b,s,v;
int main(){
    cin>>a;
    cin>>b;
    v=a;
    while(v)v/=10,s++;
    for(int i=a,n,m;i<b;i++){
        n=i;
        m=(n%10)*k[s-1]+n/10;
        while(n!=m){
            if(n<m&&m<=b)ans++;
            m=(m%10)*k[s-1]+m/10;
        }
    }
	cout<<ans;
	return 0;
}