支付功能网站建设,公司网站修改怎么做,基于html5的购物网站开发,设计研发网站我们把一个数称为有趣的#xff0c;当且仅当#xff1a;
它的数字只包含 0,1,2,3#xff0c;且这四个数字都出现过至少一次。 所有的 0 都出现在所有的 1 之前#xff0c;而所有的 2 都出现在所有的 3 之前。 最高位数字不为 0。 因此#xff0c;符合我们定义的最小的有趣…我们把一个数称为有趣的当且仅当
它的数字只包含 0,1,2,3且这四个数字都出现过至少一次。 所有的 0 都出现在所有的 1 之前而所有的 2 都出现在所有的 3 之前。 最高位数字不为 0。 因此符合我们定义的最小的有趣的数是 2013。
除此以外4 位的有趣的数还有两个2031 和 2301。
请计算恰好有 n 位的有趣的数的个数。
由于答案可能非常大只需要输出答案除以 1097 的余数。
输入格式 输入只有一行包括恰好一个正整数 n。
输出格式 输出只有一行包括恰好 n 位的整数中有趣的数的个数除以 1097 的余数。
数据范围 4≤n≤1000 输入样例 4 输出样例 3
代码如下
#include iostream
using namespace std;
const int N 1010;
int c[N][N];
const int MOD 1e97;
typedef long long LL;
int main()
{int n;cinn;for (int i 0;iN;i)for (int j 0;ji;j){if (!j) c[i][j] 1;else c[i][j] (c[i-1][j]c[i-1][j-1])%MOD;}int res 0;for (int k 2;kn-2;k){res (res(LL)c[n-1][k]*(k-1)%MOD*(n-k-1))%MOD;}coutresendl;
}
