A bzoj - 3260 跳。
简单且狗儿题，最多算根号次，不取模差不多得了。
//how to get this one????
#include<bits/stdc++.h>
const int mod=1e9+7;
long long n,m;
long long qpow(long long bas,int times)
{
long long res=1;
for(; times; times>>=1,bas=bas*bas%mod)
{
if(times&1) res=res*bas%mod;
}
return res;
}
long long com(long long one,long long ano)
{
long long resx=1,resy=1;
for(int i=0; i<ano; ++i)
{
resx=resx*((one-i+mod)%mod)%mod;
resy=resy*((i+1)%mod)%mod;
}
return resx*qpow(resy,mod-2)%mod;
}
signed main()
{
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
scanf("%lld%lld",&n,&m);
if(n>m) n^=m^=n^=m;
printf("%lld\n",(com(n+m+1,n)+m)%mod);
fprintf(stderr,"%lld %lld",n,m);
return 0;
}
B haoi - 2010 计数
其实就是康托展开，把字符串中的 \(\texttt{0}\) 全部放到开头算全排列，然后答案即 \(\displaystyle\prod_{i=0}^{9}\binom{m-\sum_{0\leqslant j<i}c_j}{c_i}\)，\(c\) 是桶。
#include<bits/stdc++.h>
using namespace std;
int val[100],cnt[20],n;
long long arrcom[2100][2100],ans;
long long com(int one,int ano)
{
if(arrcom[one][ano]) return arrcom[one][ano];
else if(one<ano) return arrcom[one][ano]=0;
else if(ano==0 || one==ano) return 1;
return arrcom[one][ano]=com(one-1,ano-1)+com(one-1,ano);
}
signed main()
{
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
string fuck;
cin>>fuck;
for(int i=0; i<int(fuck.size()); ++i) val[++n]=fuck[i]-'0';
for(int i=1; i<=n; ++i) cnt[val[i]]++;
for(int i=1; i<=n; ++i)
{
for(int j=0; j<val[i]; ++j)
{
if(cnt[j])
{
cnt[j]--;
long long tmp=1;
int up=n-i;
for(int k=0; k<10; ++k)
{
if(cnt[k])
{
tmp*=com(up,cnt[k]);
up-=cnt[k];
}
}
ans+=tmp;
cnt[j]++;
}
}
cnt[val[i]]--;
}
printf("%lld\n",ans);
return 0;
}
C acmhdu - 6397 Character Encoding
我也不知道我为什么就是推错了，可能是我没长脑子吧。你看着这个题是不是很想求 \(f(z)\) 表示至少 \(z\) 个超限的方案数，然后答案就是 \(\displaystyle\sum_{i=0}^{\lfloor\frac{k}{n}\rfloor}(-1)^if(i)\)。\(f(i)\) 表示出来就是 \(\binom{m}{i}\binom{k-n\times i+m-1}{m-1}\)。
//i'm the shabbiest one ever
#include<bits/stdc++.h>
template <int P>
struct Z {
int x;
Z(const int a = 0) : x(norm(a)) {}
static int norm(const int& t) {
if (t < 0) return t + P;
if (t >= P) return t - P;
return t;
}
Z inv() const { return assert(x), power(x, P - 2); }
static Z power(Z x, long long y) {
Z res = 1;
for (; y; y >>= 1, x *= x)
if (y & 1) res *= x;
return res;
}
int val() const { return x; }
Z operator-() { return norm(-x); }
friend Z operator+(const Z& a, const Z& b) { return Z(norm(a.val() + b.val())); }
friend Z operator-(const Z& a, const Z& b) { return Z(norm(a.val() - b.val())); }
friend Z operator*(const Z& a, const Z& b) { return Z(static_cast<long long>(a.val()) * b.val() % P); }
friend Z operator/(const Z& a, const Z& b) { return a * b.inv(); }
Z &operator+=(const Z& t) { return (*this) = (*this) + t; }
Z &operator-=(const Z& t) { return (*this) = (*this) - t; }
Z &operator*=(const Z& t) { return (*this) = (*this) * t; }
Z &operator/=(const Z& t) { return (*this) = (*this) / t; }
static int mod() { return P; }
};
using mint=Z<998244353 >;
struct Simple {
std::vector<mint> fac, ifac;
Simple() : fac(1, 1), ifac(1, 1) {}
mint gfac(int n) { return check(n), fac[n]; }
mint gifac(int n) { return check(n), ifac[n]; }
void check(int n) {
int pn = fac.size();
for (int i = pn; i <= n; ++i) fac.emplace_back(fac.back() * i);
for (int i = pn; i <= n; ++i) ifac.emplace_back(fac[i].inv());
}
mint binom(int n, int k) {
assert(n >= k), check(n);
return fac[n] * ifac[n - k] * ifac[k];
}
} simp;
mint C(int x,int y){return simp.binom(x,y);
}
signed main()
{
freopen("encoding.in","r",stdin);
freopen("encoding.out","w",stdout);
int T,n,m,k;
scanf("%d",&T);
for(; T--;)
{
scanf("%d%d%d",&n,&m,&k);
if(k/m>n-1) {puts("0");continue;}
mint ans=0;
for(int i=0;i<=k/n;i++)
{
if(i&1)ans=(ans-(C(m,i)*C(k-n*i+m-1,m-1)));
else ans=(ans+(C(m,i)*C(k-n*i+m-1,m-1)));
}
printf("%d\n",ans.val());
}
return 0;
}
D Non-Resource
萌萌题，我打 std::vector 螺旋升天。
就嗯上容斥，std::map 维护即可。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int a[5];
void get(int x,int y,int z,int w,int h)
{
int cur=0;
for(int i:{x,y,z,w,h}) a[cur++]=i;
}
int& operator[](const int i)
{
return a[i];
}
friend bool operator<(node one,node ano)
{
for(int i=0; i<5; ++i)
{
if(one[i]<ano[i]) return true;
else if(one[i]>ano[i]) return false;
}
return false;
}
}emp;
map<node,int> mp[6];
int n;
long long ans;
signed main()
{
freopen("against.in","r",stdin);
freopen("against.out","w",stdout);
scanf("%d",&n);
for(int i=1,b[5]; i<=n; ++i)
{
for(int i=0; i<5; ++i) scanf("%d",&b[i]);
sort(b,b+5);
for(int S=1; S<(1<<5); ++S)
{
int tot=0;
node tmp=emp;
for(int j=0; j<5; ++j)
{
if(S&(1<<j)) tmp[tot++]=b[j];
}
mp[tot][tmp]++;
}
}
ans=1ll*n*n;
for(int i=1; i<6; ++i)
{
for(auto it=mp[i].begin(); it!=mp[i].end(); ++it) ans+=((i&1)?-1ll:1ll)*(it->second)*(it->second);
}
printf("%lld\n",ans/2);
return 0;
}