J'ai senti que j'étais capable de garder la performance à 4 chiffres et d'avoir la force même si je ne me consacrais pas à la compétition, mais je ne peux pas aller plus loin si je ne me consacre plus. Je ferai plus de dévotion.
Cette fois, j'ai pu résoudre jusqu'à D, mais il a fallu beaucoup de temps entre le moment où j'ai élaboré la politique et le moment où j'ai fini de la résoudre. C'était un modèle que je n'avais jamais vu pour $ _nC_r $, donc j'ai trouvé un article de Kencho-san et je l'ai remarqué, mais au début j'essayais de le trouver par une autre méthode TLE, donc je le regrette.
Quand j'ai résolu E après le concours, ce n'était pas difficile si j'y pensais calmement. Que faisiez-vous? Seulement environ 2% du cerveau peut être utilisé.
Notez que le classement interne et le classement d'affichage sont différents.
A.py
n,r=map(int,input().split())
if n>=10:
print(r)
else:
print(r+100*(10-n))
Pensez au nombre de fois que vous pouvez diviser par k en tournant l'instruction while. Il se termine lorsque n devient 0.
B.py
ans=0
n,k=map(int,input().split())
while True:
n=n//k
ans+=1
if n==0:
break
print(ans)
Considérez P de la plus petite coordonnée x à la plus grande coordonnée x dans l'ordre, et trouvez la somme totale de la force physique minimale parmi elles.
C.py
n=int(input())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(x[0],x[-1]+1):
su=0
for j in range(n):
su+=((x[j]-i)**2)
y.append(su)
print(min(y))
Cette question est facile à penser dans la politique elle-même. Parce que
C'est parce que cela ressort clairement du théorème binomial.
Cependant, comme n vaut environ 10 ^ 9 lors du calcul de la combinaison, comment créer d'abord un tableau pour calculer la combinaison (ABC042D ), ABC066D, ABC151E est O (n), donc TLE Ce sera.
Revenons donc à l'essentiel ici. $ _N C _k = \ frac {n} {1} \ times \ frac {n-1} {2} \ times… \ times \ frac {n-k + 1} Puisqu'il est {k}
answerD.cc
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
using namespace std;
typedef long long ll;
const ll MAX = 200000;
const ll MOD=1000000007;
//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define INF 1000000000000
#define PB push_back
#define MP make_pair
#define F first
#define S second
template<ll mod> class modint{
public:
ll val=0;
//constructeur
constexpr modint(ll x=0):val(x%mod){while(x<0)x+=mod;}
//Opérateur arithmétique
constexpr modint operator +(const modint &r){return modint(*this)+=r;}
constexpr modint operator -(const modint &r){return modint(*this)-=r;}
constexpr modint operator *(const modint &r){return modint(*this)*=r;}
constexpr modint operator /(const modint &r){return modint(*this)/=r;}
//Opérateur d'assignation
constexpr modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
constexpr modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
constexpr modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
constexpr modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Opérateur de comparaison d'équivalence
constexpr bool operator ==(const modint& r){return this->val==r.val;}
constexpr bool operator <(const modint& r){return this->val<r.val;}
constexpr bool operator !=(const modint& r){return this->val!=r.val;}
//Flux d'E / S
friend constexpr istream &operator >>(istream &is,const modint<mod>& x){
ll t;is >> t;
x=modint<mod>(t);
return (is);
}
friend constexpr ostream &operator <<(ostream &os,const modint<mod>& x){
return os<<x.val;
}
//Puissance
friend constexpr modint<mod> modpow(const modint<mod> &a,ll n){
if(n==0)return 1;
modint<mod> t=modpow(a,n/2);
t=t*t;
if(n&1)t=t*a;
return t;
}
};
using mint = modint<MOD>;
signed main(){
ll n,a,b;cin >> n >> a >> b;
const mint x=2;
mint ans=modpow(x,n);
ans-=1;
vector<mint> com(b+1);
FOR(i,1,b){
if(i==1){
com[i]=n;
}else{
com[i]=com[i-1];
com[i]*=(n-i+1);
com[i]/=i;
}
}
ans=ans-com[a]-com[b];
cout << ans << endl;
}
Le concours était terminé si j'avais ** mal compris ** que plusieurs personnes pouvaient déménager en un seul mouvement ... Je dois bien regarder l'échantillon ... De plus, quand je l'ai résolu à nouveau après le concours, j'ai réalisé que ce n'était pas si difficile. Premièrement, lorsque vous ** faites attention à chaque pièce **, vous pouvez voir que lorsqu'il n'y a aucun résident dans cette pièce, les personnes dans cette pièce ont déménagé dans une autre pièce. Par conséquent, lorsque vous déménagez k fois, vous pouvez penser qu'il y aura k chambres avec 0 résidents. De plus, à ce moment, le modèle dans lequel 0 à k-1 pièces deviennent 0 personnes peut également être exprimé parce que c'est ** juste pour ajouter du mouvement supplémentaire ** (pour plus de détails, [Explication](https: //). Veuillez vous référer à img.atcoder.jp/abc156/editorial.pdf).). Par conséquent, vous pouvez voir que vous devez compter chacun des cas où il y a 0 à k chambres pour ** 0 personnes ** (notez cependant que k <= n-1). .. De plus, quand il y a i chambres pour 0 personnes, la façon de choisir une chambre pour 0 personnes est $ _n C _i $ rue, et il y a 2 chambres avec 1 personne ou plus et le nombre total de personnes est n, comme suit En y réfléchissant, la combinaison du nombre de personnes est $ _ {n-1} C _ {ni-1} $, et la combinaison du nombre de personnes dans la salle quand il y a i chambres pour 0 personne est $ _n C _i \ fois Il devient _ {n-1} C _ {n-i-1} $.
Par conséquent, si vous écrivez le programme en faisant attention à la quantité excessive de MOD ($ = 10 ^ 9 + 7 $), ce sera comme suit.
answerE.cc
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable
using namespace std;
typedef long long ll;
//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX = 200001;
ll fac[MAX], finv[MAX], inv[MAX];
//Prétraitement pour faire une table
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (ll i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
//Calcul du coefficient binaire
ll COM(ll n,ll k){
if (n == 1) return 1;
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
signed main(){
COMinit();
ll n,k;cin >> n >> k;
if(k>=n)k=n-1;
ll ans=0;
REP(i,k+1){
ans+=(COM(n,i)*COM(n-1,n-i-1));
ans%=MOD;
}
cout << ans << endl;
}
Je ne pense pas que ce soit encore adapté au niveau, je vais donc l'ignorer cette fois.
Recommended Posts