Language: C++


考虑后面的求和部分。它显然分成三段。形式分别是∑Mi=0CiM；∑ki=0CkM；∑ki=tCkM
如果我们知道M=i-1时的总和，要推到M=i时的总和。根据杨辉三角公式，第一种情况直接乘2，第二种是乘2再减掉Cki−1，第三种是乘2减掉Cki−1和Ct−1i−1


复杂度是线性的

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=9e5+5,mo=1e9+7;

typedef long long LL;

int n,m,K,ans,Fac[N],Inv[N],p[N];

int C(int n,int m)
{
    return (LL)Fac[n]*Inv[m]%mo*Inv[n-m]%mo;
}

int main()
{
    p[0]=Fac[0]=Inv[0]=Fac[1]=Inv[1]=1; p[1]=3;
    for (int i=2;i<N;i++) Inv[i]=(LL)Inv[mo%i]*(mo-mo/i)%mo;
    for (int i=2;i<N;i++)
    {
        p[i]=p[i-1]*3ll%mo; Fac[i]=(LL)Fac[i-1]*i%mo; Inv[i]=(LL)Inv[i-1]*Inv[i]%mo;
    }
    scanf("%d%d%d",&n,&m,&K); n--;
    if (m<K) swap(m,K);
    for (int i=0,j=1;i<=m+K;i++)
    {
        ans=(ans+(LL)C(n+i,n)*p[m+K-i]%mo*j)%mo;
        if (i<K) j=j*2%mo;
        else if (i>=m) j=(j*2ll-C(i,K)-C(i,i-m))%mo;
        else j=(j*2ll-C(i,K))%mo;
    }
    if (ans<0) ans+=mo;
    printf("%d\n",ans);
    return 0;
}

Compiler output:
a.cc:2:1: error: extended character 。 is not valid in an identifier
    2 | 考虑后面的求和部分。它显然分成三段。形式分别是∑Mi=0CiM；∑ki=0CkM；∑ki=tCkM
      | ^
a.cc:2:1: error: extended character 。 is not valid in an identifier
a.cc:2:1: error: extended character ∑ is not valid in an identifier
a.cc:2:51: error: extended character ∑ is not valid in an identifier
    2 | 考虑后面的求和部分。它显然分成三段。形式分别是∑Mi=0CiM；∑ki=0CkM；∑ki=tCkM
      |                                                   ^
a.cc:2:61: error: extended character ∑ is not valid in an identifier
    2 | 考虑后面的求和部分。它显然分成三段。形式分别是∑Mi=0CiM；∑ki=0CkM；∑ki=tCkM
      |                                                             ^
a.cc:3:36: error: extended character 。 is not valid in an identifier
    3 | 如果我们知道M=i-1时的总和，要推到M=i时的总和。根据杨辉三角公式，第一种情况直接乘2，第二种是乘2再减掉Cki−1，第三种是乘2减掉Cki−1和Ct−1i−1
      |                                    ^
a.cc:3:36: error: extended character − is not valid in an identifier
a.cc:3:36: error: extended character − is not valid in an identifier
a.cc:3:36: error: extended character − is not valid in an identifier
a.cc:3:36: error: extended character − is not valid in an identifier
a.cc:2:1: error: '\U00008003\U00008651\U0000540e\U00009762\U00007684\U00006c42\U0000548c\U000090e8\U00005206\U00003002\U00005b83\U0000663e\U00007136\U00005206\U00006210\U00004e09\U00006bb5\U00003002\U00005f62\U00005f0f\U00005206\U0000522b\U0000662f\U00002211Mi' does not name a type
    2 | 考虑后面的求和部分。它显然分成三段。形式分别是∑Mi=0CiM；∑ki=0CkM；∑ki=tCkM
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:62,
                 from /usr/include/c++/14/algorithm:60,
                 from a.cc:10:
/usr/include/c++/14/ext/type_traits.h:164:35: error: 'constexpr const bool __gnu_cxx::__is_null_pointer' redeclared as different kind of entity
  164 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/14/ext/type_traits.h:159:5: note: previous declaration 'template<class _Type> constexpr bool __gnu_cxx::__is_null_pointer(_Type)'
  159 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/14/ext/type_traits.h:164:26: error: 'nullptr_t' is not a member of 'std'
  164 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/14/bits/stl_pair.h:60,
                 from /usr/include/c++/14/bits/stl_algobase.h:64:
/usr/include/c++/14/type_traits:666:33: error: 'nullptr_t' is not a member of 'std'
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                 ^~~~~~~~~
/usr/include/c++/14/type_traits:666:42: error: template argument 1 is invalid
  666 |     struct is_null_pointer<std::nullptr_t>
      |                                          ^
/usr/include/c++/14/type_traits:670:48: error: template argument 1 is invalid
  670 |     struct is_null_pointer<const std::nullptr_t>
      |                                                ^
/usr/include/c++/14/type_traits:674:51: error: template argument 1 is invalid
  674 |     struct is_null_pointer<volatile std::nullptr_t>
      |                                                   ^
/usr/include/c++/14/type_traits:678:57: error: template argument 1 is invalid
  678 |     struct is_null_pointer<const volatile std::nullptr_t>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                     ^~~~~~
In file included from /usr/include/stdio.h:34,
                 from /usr/include/c++/14/cstdio:42,
                 from a.cc:8:
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1429:57: error: template argument 1 is invalid
 1429 |     : public integral_constant<std::size_t, alignof(_Tp)>
      |                                                         ^
/usr/include/c++/14/type_traits:1429:57: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1438:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1438:46: error: template argument 1 is invalid
 1438 |     : public integral_constant<std::size_t, 0> { };
      |                                              ^
/usr/include/c++/14/type_traits:1438:46: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1440:26: error: 'std::size_t' has not been declared
 1440 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:1441:21: error: '_Size' was not declared in this scope
 1441 |     struct rank<_Tp[_Size]>
      |                     ^~~~~
/usr/include/c++/14/type_traits:1441:27: error: template argument 1 is invalid
 1441 |     struct rank<_Tp[_Size]>
      |                           ^
/usr/include/c++/14/type_traits:1442:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1442:65: error: template argument 1 is invalid
 1442 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1442:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:1446:37: error: 'size_t' is not a member of 'std'; did you mean 'size_t'?
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                     ^~~~~~
/usr/lib/gcc/x86_64-linux-gnu/14/include/stddef.h:214:23: note: 'size_t' declared here
  214 | typedef __SIZE_TYPE__ size_t;
      |                       ^~~~~~
/usr/include/c++/14/type_traits:1446:65: error: template argument 1 is invalid
 1446 |     : public integral_constant<std::size_t, 1 + rank<_Tp>::value> { };
      |                                                                 ^
/usr/include/c++/14/type_traits:1446:65: note: invalid template non-type parameter
/usr/include/c++/14/type_traits:2086:26: error: 'std::size_t' has not been declared
 2086 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2087:30: error: '_Size' was not declared in this scope
 2087 |     struct remove_extent<_Tp[_Size]>
      |                              ^~~~~
/usr/include/c++/14/type_traits:2087:36: error: template argument 1 is invalid
 2087 |     struct remove_extent<_Tp[_Size]>
      |                                    ^
/usr/include/c++/14/type_traits:2099:26: error: 'std::size_t' has not been declared
 2099 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/14/type_traits:2100:35: error: '_Size' was not declared in this scope
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                   ^~~~~
/usr/include/c++/14/type_traits:2100:41: error: template argument 1 is invalid
 2100 |     struct remove_all_extents<_Tp[_Size]>
      |                                         ^
/usr/include/c++/14/type_traits:2171:12: error: 'std::size_t' has not been declared
 2171 |   template<std::size_t _Len>
      |            ^~~
/usr/include/c++/14/type_traits:2176:30: error: '_Len' was not declared in this scope
 2176 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2194:12: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |            ^~~
/usr/include/c++/14/type_traits:2194:30: error: 'std::size_t' has not been declared
 2194 |   template<std::size_t _Len, std::size_t _Align =
      |                              ^~~
/usr/include/c++/14/type_traits:2195:55: error: '_Len' was not declared in this scope
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                       ^~~~
/usr/include/c++/14/type_traits:2195:59: error: template argument 1 is invalid
 2195 |            __alignof__(typename __aligned_storage_msa<_Len>::__type)>
      |                                                           ^
/usr/include/c++/14/type_traits:2202:30: error: '_Len' was not declared in this scope
 2202 |         unsigned char __data[_Len];
      |                              ^~~~
/usr/include/c++/14/type_traits:2203:44: error: '_Align' was not declared in this scope
 2203 |         struct __attribute__((__aligned__((_Align)))) { } __align;
      |                                            ^~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:65:
/usr/include/c++/14/bits/stl_iterator_base_types.h:125:67: error: 'ptrdiff_t' does not name a type
  125 |   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
      |                                                                   ^~~~~~~~~
/usr/include/c++/14/bits/stl_iterator_base_types.h:1:1: note: 'ptrdiff_t' is defined in header '<cstddef>'; this is probably fixable by adding '#include <cstddef>'
  +++ |+#include <cstddef>
    1 | // T