9小时前
#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 20, mod = 1e9 + 7;

LL A[N];

int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}

int C(LL a, LL b)
{
if(a < b)return 0;
int up = 1, down = 1;
for(LL i = a; i > a - b; i --)up = i % mod * up % mod;
for(int i = 1; i <= b; i ++)down = (LL)down * i % mod;

return (LL)up * qmi(down, mod - 2) % mod;
}

int main()
{
LL n, m;
cin >> n >> m;
for(int i = 0; i < n; i ++)cin >> A[i];
int res = 0;
for(int i = 0; i < 1 << n; i ++)
{
int sign = 1;
LL a = n + m - 1, b = n - 1;
for(int j = 0; j < n; j ++)
if(i >> j & 1)
{
sign = sign * -1;
a -= A[j] + 1;
}
res = (res + C(a, b) * sign) % mod;
}
cout << (res + mod) % mod << endl;
return 0;
}


2天前
#include <iostream>

using namespace std;
const int mod = 1e6 + 3;
typedef long long LL;

int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}

int C(int a, int b)
{
if (a < b) return 0;

int down = 1, up = 1;
for (int i = a, j = 1; j <= b; i --, j ++ )
{
up = (LL)up * i % mod;
down = (LL)down * j % mod;
}

return (LL)up * qmi(down, mod - 2) % mod;
}

int Lucas(int a, int b)
{
if(a < mod && b < mod)return C(a, b);
return (LL)C(a % mod, b % mod) * Lucas(a / mod, b / mod) % mod;
}

int main()
{
int T;
cin >> T;
while(T --){
int n, l, r;
cin >> n >> l >> r;

cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + mod ) % mod << endl;
}
return 0;
}


2天前
#include <iostream>

using namespace std;
const int mod = 1e6 + 3;
typedef long long LL;

int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = (LL)res * a % mod;
a = (LL)a * a % mod;
b >>= 1;
}
return res;
}

int C(int a, int b)
{
if (a < b) return 0;

int down = 1, up = 1;
for (int i = a, j = 1; j <= b; i --, j ++ )
{
up = (LL)up * i % mod;
up = (LL)up * qmi(j, mod - 2) % mod;//放在里面会超时
}

return up;
}
/*
int C(int a, int b)
{
if (a < b) return 0;

int down = 1, up = 1;
for (int i = a, j = 1; j <= b; i --, j ++ )
{
up = (LL)up * i % p;
down = (LL)down * j % p;
}

return (LL)up * qmi(down, p - 2) % p;
}
*/
int Lucas(int a, int b)
{
if(a < mod && b < mod)return C(a, b);
return (LL)C(a % mod, b % mod) * Lucas(a / mod, b / mod) % mod;
}

int main()
{
int T;
cin >> T;
while(T --){
int n, l, r;
cin >> n >> l >> r;

cout << (Lucas(r - l + n + 1, r - l + 1) - 1 + mod ) % mod << endl;
}
return 0;
}


2天前
#include <iostream>

using namespace std;
typedef long long LL;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}

LL C(int a, int b)
{
return (LL)a * (a - 1) * (a - 2) / 6;
}

int main()
{
int n, m;
cin >> n >> m;
n ++, m ++;
LL res = C(m * n, 3) - n * C(m, 3) - m * C(n, 3);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
res -= 2ll * (gcd(i, j) - 1) * (n - i) * (m - j);
cout << res << endl;
return 0;
}


2天前
#include <iostream>

using namespace std;
typedef long long LL;
const int mode = 100003;

int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = (LL)res * a % mode;
a = (LL) a * a % mode;
b >>= 1;
}
return res;
}

int fact(int x)
{
int res = 1;
for(int i = 1; i <= x; i ++)
res = (LL)res * i % mode;
return res;
}

int infact(int x)
{
int res = 1;
for(int i = 1; i <= x; i ++)
res = (LL)res * qmi(i, mode - 2) % mode;
return res;
}

int C(int a, int b)
{
if(a < b)return 0;
return (LL)fact(a) * infact(a - b) % mode * infact(b) % mode;
}

int A(int a, int b)
{
if(a < b)return 0;
return (LL)fact(a) * infact(a - b) % mode;
}

int main()
{
int a, b, c, d, k;
cin >> a >> b >> c >> d >> k;

int res = 0;

for(int i = 0; i <= k; i ++)
{
res = (res + (LL)C(b, i) * A(a, i) % mode * (LL)C(d, k - i)% mode * A(a + c - i, k - i) % mode) % mode;

}
cout << res << endl;
return 0;
}


3天前
#include <iostream>

using namespace std;

const int N = 150;
int f[1000][100][N];

int qmi(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1)res = (long long )res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}

void add(int c[], int a[], int b[])
{
int t = 0;
for(int i = 0; i < N; i ++)
{
t += a[i] + b[i];
c[i] = t % 10;
t /= 10;
}
}

int main()
{
int k, x;
cin >> k >> x;
int n = qmi(x % 1000, x, 1000);

for(int i = 0; i < n; i ++)
for(int j = 0; j <= i && j < k; j ++)
if(!j)f[i][j][0] = 1;
else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);
int *g = f[n - 1][k - 1];
k = N - 1;
while(!g[k])k --;
for(; k >= 0; k --)cout << g[k];
return 0;
}


3天前
#include <iostream>

using namespace std;
const int N = 1e5 + 10, mod = 5000011;
int f[N], s[N];

int main()
{
int n, m;
cin >> n >> m;
f[0] = s[0] = 1;
for(int i = 1; i <= n; i ++)
{
f[i] = s[max(i - m - 1, 0)];
s[i] = (s[i - 1] + f[i]) % mod;
}
cout << s[n] << endl;
return 0;
}


4天前

## 菜逼一枚，看了一下午推导，最后果然死在了最后一步，不等为啥，会的大佬帮忙call我，谢谢！

4天前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 5;
typedef long long LL;
int n, m;

void mul(int f[], int a[][N])
{
int temp[N] = {0};
for(int i = 0; i < N; i ++)
for(int j = 0; j < N; j ++)
temp[i] = (temp[i] + (LL)f[j] * a[j][i]) % m;
memcpy(f, temp, sizeof temp);
}

void mul(int a[][N])
{
int temp[N][N] = {0};
for(int i = 0; i < N; i ++)
for(int j = 0; j < N; j ++)
for(int k = 0; k < N; k ++)
temp[i][j] = (temp[i][j] + (LL)a[i][k] * a[k][j]) % m;
memcpy(a, temp, sizeof temp);
}

int main()
{
cin >> n >> m;
int f[N] = {0, 1, 0, 1, 0};
int a[N][N] = {
{0, 1, 0, 2, 0},
{1, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 0, 1, 1, 1},
{0, 0, 0, 0, 1},
};

while(n)
{
if(n & 1)mul(f, a);
mul(a);
n >>= 1;
}

cout << f[4] << endl;
return 0;
}


4天前

### 记录一下踩的坑

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 3;
int n, m;

void mul(int f[], int a[][N])
{
int temp[N] = {0};
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
temp[i] = (temp[i] + (LL)f[j] * a[j][i]) % m;
memcpy(f, temp, sizeof temp); // 一定要是sizeof(temp)不能是f因为f传进来的是个指针大小就是指针的大小。
}

void mul(int a[][N], int b[][N])
{
int temp[N][N] = {0};
for(int i = 0; i < 3; i ++)
for(int j = 0; j < 3; j ++)
for(int k = 0; k < 3; k ++)
temp[i][j] = (temp[i][j] + (LL)a[i][k] * b[k][j]) % m;
memcpy(a, temp, sizeof temp);//一定要是sizeof(temp),不能上f因为f传进来的是指针大小就是指针的大小。
}

int main()
{
cin >> n >> m;
int f[N] = {0, 1, 0};
int a[N][N] = {
{0, 1, 0},
{1, 1, 1},
{0, 0, 1},
};
while(n)
{
if(n & 1)mul(f, a);
mul(a, a);
n >>= 1;
}
cout << f[2] << endl;
return 0;
}