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;
}

萌萌题，我打 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;
}

对于 Newton Expansion，式子本身的证明其实无甚可翻新的花样，但是题还是很有意思的。比如 codeforces - 1332E Height All the Same 这个。

首先给出几个性质：每个 cell 上的数字奇偶性才是需要关注的；如果 $n\times m$ 为奇数，永远有解；如果 $n\times m$ 为偶数，当 $\sum\sum a_{i,j}\bmod2$ 为偶数时有解。应该都不需要证明。

奇数的答案不赘，我们可以写出偶数的答案式子：$\displaystyle\sum_{i=0}^{\lfloor\frac{nm}{2}\rfloor}a^{2i}b^{nm-2i}\binom{nm}{2i}$，$a,b$ 分别是 $[l,r]$ 中偶 / 奇的数量。然后你注意这个式子长得很像 Newton Expansion 的形式，容易构造出答案为 $\frac{(a+b)^{nm}+(a+b)^{nm}}{2}$。

我们来看几个一般的组合恒等式。

1. $\displaystyle\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$；
2. $\displaystyle\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$；
3. $\displaystyle\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}$；
4. $\displaystyle\sum_{k=0}^{n}k^2\binom{n}{k}=n(n+1)2^{n-2}$；
5. $\displaystyle\sum_{l=0}^n\binom{l}{k}=\binom{n+1}{k+1}\Longrightarrow\sum_{k=0}^n\binom{r+k}{k}=\binom{r+n+1}{r+1}=\binom{r+n+1}{n}$；
6. $\displaystyle\binom{n}{k}=(-1)^k\binom{k-n-1}{k}$；
7. $\displaystyle\sum_{k=0}^m(-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}$；
8. $\displaystyle\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}$；
9. $\displaystyle\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r}$；（Vandermonde Convolution）

我们一个一个的来看。

1. 这个我无法找到除了代数解释以外的方法来诠释它的含义；
2. 经典的 Pascal's Formula，组合意义即钦定一个物品不选。适用场景很多，经常反过来用；
3. 带权变下项求和，考虑这样的组合意义：在 $n$ 个物品中选出 $k$ 个，再从这 $k$ 个物品中选出一个组成 1-tuples 的方案数。对应到 r.h.s.，反过来钦定 1-tuples，然后计算系数。
4. 同理，组合意义即在 $n$ 个物品中选出 $k$ 个，再从这 $k$ 个物品中可重地选出两个物品组成无序 2-tuples 的方案数。对应到 r.h.s.，反过来钦定 2-tuples，再考虑系数。需要分类讨论，当选出的物品不相同，为 $n(n-1)2^{n-2}$，当相同时，为 $n^22^{n-1}$，加在一起即 $n(3n-1)2^{n-2}$。
5. 变上项求和，考虑 $n+1$ 个物品，每次钦定第 $1,2,\dots,n+1$ 个不选，左右两式即相等，例题 codechef - CSEQ Count Sequences。
6. 这个式子我理解不能，但是运算有封闭性，再算一次可以变回去。
7. 用式 6，得 $\displaystyle \sum_{k=0}^m(-1)^k\binom{n}{k}=\sum_{k=0}^m\binom{k-n-1}{k}=\sum_{k=0}^m\binom{k-n-1}{}$ 🕊。
8. 组合意义：$\{a_{n}\}$ 的 $r$-subsets 的 $k$-subsets 数，r.h.s. 即在 $\{a_n\}$ 中选出 $k$-subsets，再在 ${a_n}\setminus k\text{-subsets}$ 中选 $r-k$-subsets。
9. l.h.s. 和 r.h.s. 的意义都是 $\{a_{m+n}\}$ 的 $r$-subsets 数。

来看一些题。

• 「acmhdu - 5794」A Simple Chess link：首先注意到这个走路的方式就是象棋马走日，然后做一个像 codeforces - 559C Gerald and Giant Chess 一样的 dp，有些细节需要注意。
• 「codeforces - 839D」Winter is here link：数数日门题。考虑反过来算每种 $\gcd$ 的贡献次数。

link。

原问题即：请你给出不同的序列 $\{a_n\}$ 的数量，满足 $0\leqslant a_i<i$，且 $\sum a_i=k$。

那么写出 ${a_n}$ 的 ogf，可得答案为：$\displaystyle [x^k]\left(G(x)=\sum_{i=0}^{n-1} x^i=\frac{1-x^n}{1-x}\right)=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}=\left(\prod_{i=1}^n(1-x^i)\right)\left(\sum_{i=0}^n\binom{n-1+i}{i} x^i\right)$。

前面那个括号是有组合意义的，即有 $n$ 个物品，其第 $i$ 个体积为 $i$，有个容量 $k$ 的背包，求恰好填满背包的方案数，这个方案数还要乘一个系数 $(-1)^m$，$m$ 为选的物品的个数。

后面那个你就直接算，前面的可以 dp。考虑这样一个构造过程：

一开始什么数都没有。对已有的数，我们有两种操作，一种是全部加 $1$，一种是全部加 $1$ 然后再加入一个值为 $1$ 的数。这样执行若干次操作之后构造出来的数列一定满足条件。

https://blog.csdn.net/a_crazy_czy/article/details/72862151

然后就设 $f(i,j)$ 为选了 $i$ 个数，目前的和为 $j$ 的方案数，转移很简单，依照两种操作模拟即可。

太神仙了，我脑子不够用。然后第一维的规模是根号，所以能过了。

#include <bits/stdc++.h>

constexpr int kMod = 1e9 + 7;
constexpr int kN = 1e5, kSqrt = 500;
int n, k, f[kSqrt + 5][kN + 5], fac[kN * 2 + 5], ifac[kN * 2 + 5];

inline void addeq(int& u, const int v) { (u += v) >= kMod && (u -= kMod); }
inline void muleq(int& u, const int v) { u = static_cast<long long>(u) * v % kMod; }
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += kMod); }
inline int add(int u, const int v) { return (u += v) < kMod ? u : u - kMod; }
inline int mul(const int u, const int v) { return static_cast<long long>(u) * v % kMod; }
inline int mpow(int x, int y) {
    int res = 1;
    for (; y; y >>= 1, muleq(x, x))
        if (y & 1) muleq(res, x);
    return res;
}

template <typename... Args>
inline int mul(const int u, const int v, const Args... args) { return mul(u, mul(v, args...)); }

inline void init(const int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
    ifac[n] = mpow(fac[n], kMod - 2);
    for (int i = n - 1; ~i; --i) ifac[i] = mul(ifac[i + 1], i + 1);
}
inline int com(const int x, const int y) { return mul(fac[x], ifac[x - y], ifac[y]); }

signed main() {
    init(2 * kN);
    
    std::cin >> n >> k;
    f[0][0] = 1;
    const int kS = std::trunc(std::sqrt(k * 2) + 1);
    for (int i = 1; i <= kS; ++i)
        for (int j = 0; j <= k; ++j) {
            if (j >= i) f[i][j] = add(f[i - 1][j - i], f[i][j - i]);
            if (j >= n + 1) subeq(f[i][j], f[i - 1][j - n - 1]);
        }
    
    int res = 0;
    for (int i = 0; i <= kS; ++i)
        for (int j = 0; j <= k; ++j) addeq(res, mul((i & 1) ? kMod - 1 : 1, f[i][j], com(k - j + n - 1, k - j)));
    
    std::cout << res << "\n";
    return 0;
}

「codeforces - 340E」Iahub and Permutations

link。

把 $1,\dots,n$ 中剩下没被固定的数的数量记作 $s$，再把这其中不担心有会填到自己身上去的情况的数字的数量记作 $h$，则总方案为 $s!$，考虑容斥把重叠方案去除，设容斥系数为 $f$。

则可以写出答案式：$\displaystyle \sum_{i=0}^{s-h}f_i\binom{s-h}{i}(s-i)!$。然后你考虑这个过程就是“所有数随便摆的方案数减去至少一个数冲突加上至少两个数冲突...”，所以 $f_i=(-1)^i$。

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n,a[2100],fac[2100],ifac[2100],vis[2100],bin[2100][2100];
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  fac[0]=1;
  for(int i=1; i<=2000; ++i) fac[i]=1ll*fac[i-1]*i%kMod;
  std::cin>>n;
  std::vector<int> vec;
  for(int i=1; i<=n; ++i) {
    std::cin>>a[i];
    if(~a[i]) vis[a[i]]=1;
  }
  bin[0][0]=1;
  for(int i=1; i<=n; ++i) {
    bin[i][0]=1;
    for(int j=1; j<=i; ++j) bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%kMod;
  }
  int s=0,h=0;
  for(int i=1; i<=n; ++i) {
    if(a[i]==-1) s++;
    if(vis[i]==0 && a[i]!=-1) h++;
  }
  int res=0;
  for(int i=0; i<=s-h; ++i) (res+=1ll*((i&1)?-1:1)*bin[s-h][i]*fac[s-i]%kMod)%=kMod;
  std::cout<<(res+kMod)%kMod<<"\n";
  return 0;
}

「codeforces - 520E」Pluses everywhere

link。

考虑每一个数位的贡献，这个取决于它右边第一个加号的位置，这个定了，它的系数就定了，即 $10^{s}$，其中 $s$ 为这个数位到右边第一个加号的距离减一，然后再乘一个二项式系数，当然如果这个加号在数字的最后要特殊处理。这个题是不是就做完了？

写下式子：$\displaystyle\sum_{i=0}^{n-1}\left(\left(d_i\sum_{x=0}^{n-2-i}\cdot\binom{n-x-2}{k-1}\cdot10^{x}\right)+d_i\cdot\binom{i}{k}\cdot10^{n-i-1}\right)$，然后交换求和顺序 $\displaystyle\left(\sum_{x=0}^{n-2}10^x\cdot\binom{n-x-2}{k-1}\cdot\sum_{i=0}^{n-x-2}d_i\right)+\left(\sum_{i=0}^{n-1}d_i\cdot\binom{i}{k}\cdot10^{n-i-1} \right)$。

前缀和后 $O(n)$ 算就好了。

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n,k,dig[100100],fac[100100],ifac[100100],pw[100100],prs[100100];
int Binpw(int x,int y) {
  int res=1;
  for(; y; y>>=1,x=1ll*x*x%kMod)
    if(y&1) res=1ll*res*x%kMod;
  return res;
}
int Bin(const int x,const int y) {
  if(x<y) return 0;
  return 1ll*fac[x]*ifac[x-y]%kMod*ifac[y]%kMod;
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  fac[0]=pw[0]=1;
  for(int i=1; i<=100000; ++i) fac[i]=1ll*fac[i-1]*i%kMod;
  for(int i=1; i<=100000; ++i) pw[i]=1ll*pw[i-1]*10%kMod;
  ifac[100000]=Binpw(fac[100000],kMod-2);
  for(int i=99999; ~i; --i) ifac[i]=1ll*ifac[i+1]*(i+1)%kMod;
  std::cin>>n>>k;
  char *grid=new char[n];
  std::cin>>grid;
  for(int i=0; i<n; ++i) dig[i]=grid[i]-'0';
  prs[0]=dig[0];
  for(int i=1; i<n; ++i) prs[i]=(prs[i-1]+dig[i])%kMod;
  int res=0;
  for(int i=0; i<=n-2; ++i) (res+=1ll*pw[i]*Bin(n-i-2,k-1)%kMod*prs[n-i-2]%kMod)%=kMod;
  for(int i=0; i<n; ++i) (res+=1ll*dig[i]*pw[n-i-1]%kMod*Bin(i,k)%kMod)%=kMod;
  std::cout<<res<<"\n";
  return 0;
}

「codeforces - 451E」Devu and Flowers

link。

你写出这个东西的 ogf：$\displaystyle G(x)=\prod_{i=1}^n\sum_{j=0}^{f_i}x^j=\frac{\prod_{i=1}^n1-x^{f_i+1}}{(1-x)^n}=\left(\prod_{i=1}^n1-x^{f_i+1}\right)\sum_{i=0}^{\infty}\binom{n+i-1}{n-1}x^i$。

然后发现不会了，于是考虑容斥！！.。》？

然后你发现你会了！！！。。1.！0

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n;
long long f[30],s;
int Binpw(int x,int y) {
  int res=1;
  for(; y; y>>=1,x=1ll*x*x%kMod)
    if(y&1) res=1ll*res*x%kMod;
  return res;
}
int Bin(long long n,const long long k) {
  if(n<k) return 0;
  if(n==k) return 1;
  n%=kMod;
  int resx=1,resy=1;
  for(int i=0; i<k; ++i) {
    resx=1ll*resx*(n-i)%kMod;
    resy=1ll*resy*(i+1)%kMod; 
  }
  return static_cast<int>(1ll*resx*Binpw(resy,kMod-2)%kMod);
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  std::cin>>n>>s;
  for(int i=0; i<n; ++i) std::cin>>f[i];
  const int kEntire=(1<<n);
  int res=0;
  for(int mask=0; mask<kEntire; ++mask) {
    long long tp=s;
    for(int j=0; j<n; ++j) {
      if(mask&(1<<j)) tp-=(f[j]+1);
    }
    (res+=((__builtin_popcount(mask)&1)?-1ll:1ll)*Bin(tp+n-1,n-1)%kMod)%=kMod;
  }
  std::cout<<(res+kMod)%kMod<<"\n";
  return 0;
}

感谢教练布置任务让我有动力写东西！。21）

其实有些非显性异类混了进去，但是你看得出来。

「codeforces - 340E」Iahub and Permutations

link。

把 $1,\dots,n$ 中剩下没被固定的数的数量记作 $s$，再把这其中不担心有会填到自己身上去的情况的数字的数量记作 $h$，则总方案为 $s!$，考虑容斥把重叠方案去除，设容斥系数为 $f$。

则可以写出答案式：$\displaystyle \sum_{i=0}^{s-h}f_i\binom{s-h}{i}(s-i)!$。然后你考虑这个过程就是“所有数随便摆的方案数减去至少一个数冲突加上至少两个数冲突...”，所以 $f_i=(-1)^i$。

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n,a[2100],fac[2100],ifac[2100],vis[2100],bin[2100][2100];
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  fac[0]=1;
  for(int i=1; i<=2000; ++i) fac[i]=1ll*fac[i-1]*i%kMod;
  std::cin>>n;
  std::vector<int> vec;
  for(int i=1; i<=n; ++i) {
    std::cin>>a[i];
    if(~a[i]) vis[a[i]]=1;
  }
  bin[0][0]=1;
  for(int i=1; i<=n; ++i) {
    bin[i][0]=1;
    for(int j=1; j<=i; ++j) bin[i][j]=(bin[i-1][j]+bin[i-1][j-1])%kMod;
  }
  int s=0,h=0;
  for(int i=1; i<=n; ++i) {
    if(a[i]==-1) s++;
    if(vis[i]==0 && a[i]!=-1) h++;
  }
  int res=0;
  for(int i=0; i<=s-h; ++i) (res+=1ll*((i&1)?-1:1)*bin[s-h][i]*fac[s-i]%kMod)%=kMod;
  std::cout<<(res+kMod)%kMod<<"\n";
  return 0;
}

「codeforces - 520E」Pluses everywhere

link。

考虑每一个数位的贡献，这个取决于它右边第一个加号的位置，这个定了，它的系数就定了，即 $10^{s}$，其中 $s$ 为这个数位到右边第一个加号的距离减一，然后再乘一个二项式系数，当然如果这个加号在数字的最后要特殊处理。这个题是不是就做完了？

写下式子：$\displaystyle\sum_{i=0}^{n-1}\left(\left(d_i\sum_{x=0}^{n-2-i}\cdot\binom{n-x-2}{k-1}\cdot10^{x}\right)+d_i\cdot\binom{i}{k}\cdot10^{n-i-1}\right)$，然后交换求和顺序 $\displaystyle\left(\sum_{x=0}^{n-2}10^x\cdot\binom{n-x-2}{k-1}\cdot\sum_{i=0}^{n-x-2}d_i\right)+\left(\sum_{i=0}^{n-1}d_i\cdot\binom{i}{k}\cdot10^{n-i-1} \right)$。

前缀和后 $O(n)$ 算就好了。

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n,k,dig[100100],fac[100100],ifac[100100],pw[100100],prs[100100];
int Binpw(int x,int y) {
  int res=1;
  for(; y; y>>=1,x=1ll*x*x%kMod)
    if(y&1) res=1ll*res*x%kMod;
  return res;
}
int Bin(const int x,const int y) {
  if(x<y) return 0;
  return 1ll*fac[x]*ifac[x-y]%kMod*ifac[y]%kMod;
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  fac[0]=pw[0]=1;
  for(int i=1; i<=100000; ++i) fac[i]=1ll*fac[i-1]*i%kMod;
  for(int i=1; i<=100000; ++i) pw[i]=1ll*pw[i-1]*10%kMod;
  ifac[100000]=Binpw(fac[100000],kMod-2);
  for(int i=99999; ~i; --i) ifac[i]=1ll*ifac[i+1]*(i+1)%kMod;
  std::cin>>n>>k;
  char *grid=new char[n];
  std::cin>>grid;
  for(int i=0; i<n; ++i) dig[i]=grid[i]-'0';
  prs[0]=dig[0];
  for(int i=1; i<n; ++i) prs[i]=(prs[i-1]+dig[i])%kMod;
  int res=0;
  for(int i=0; i<=n-2; ++i) (res+=1ll*pw[i]*Bin(n-i-2,k-1)%kMod*prs[n-i-2]%kMod)%=kMod;
  for(int i=0; i<n; ++i) (res+=1ll*dig[i]*pw[n-i-1]%kMod*Bin(i,k)%kMod)%=kMod;
  std::cout<<res<<"\n";
  return 0;
}

「codeforces - 451E」Devu and Flowers

link。

你写出这个东西的 ogf：$\displaystyle G(x)=\prod_{i=1}^n\sum_{j=0}^{f_i}x^j=\frac{\prod_{i=1}^n1-x^{f_i+1}}{(1-x)^n}=\left(\prod_{i=1}^n1-x^{f_i+1}\right)\sum_{i=0}^{\infty}\binom{n+i-1}{n-1}x^i$。

然后发现不会了，于是考虑容斥！！.。》？

然后你发现你会了！！！。。1.！0

#include<bits/stdc++.h>
constexpr int kMod=1e9+7;
int n;
long long f[30],s;
int Binpw(int x,int y) {
  int res=1;
  for(; y; y>>=1,x=1ll*x*x%kMod)
    if(y&1) res=1ll*res*x%kMod;
  return res;
}
int Bin(long long n,const long long k) {
  if(n<k) return 0;
  if(n==k) return 1;
  n%=kMod;
  int resx=1,resy=1;
  for(int i=0; i<k; ++i) {
    resx=1ll*resx*(n-i)%kMod;
    resy=1ll*resy*(i+1)%kMod; 
  }
  return static_cast<int>(1ll*resx*Binpw(resy,kMod-2)%kMod);
}
signed main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr),std::cout.tie(nullptr);
  std::cin>>n>>s;
  for(int i=0; i<n; ++i) std::cin>>f[i];
  const int kEntire=(1<<n);
  int res=0;
  for(int mask=0; mask<kEntire; ++mask) {
    long long tp=s;
    for(int j=0; j<n; ++j) {
      if(mask&(1<<j)) tp-=(f[j]+1);
    }
    (res+=((__builtin_popcount(mask)&1)?-1ll:1ll)*Bin(tp+n-1,n-1)%kMod)%=kMod;
  }
  std::cout<<(res+kMod)%kMod<<"\n";
  return 0;
}